{'fraction_non_alphanumeric': 0.038908145580589255, 'fraction_numerical': 0.010340843443096477, 'mean_word_length': 4.198348348348349, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 6, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
DeepTOP: Deep Threshold-Optimal Policy for MDPs and RMABs

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.


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 a 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 in the central bank scenario.
An important feature of threshold policies is that their actions are monotone. For example, if a smart home server would turn on the air conditioner at a 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. In order to design an efficient algorithm for learning the optimal threshold policy, we first formally define a 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 a continuous range, which makes it infeasible to directly apply standard tools, such as backward-propagation in neural networks, to perform gradient updates.
A threshold policy is one that defines a threshold function µ : V → mapping each vector state to a real number. The policy then deterministically picks a t = 1(µ(v t ) > λ t ), 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 a 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 λ t be the current electricity price and the vector state v t be the remaining charge and time to deadline of the EV. For this problem, it is natural to consider a threshold policy that defines a threshold µ(v t ) as the highest price the operator is willing to pay to charge the EV under vector state v t . The operator only charges the vehicle, i.e., chooses a t = 1, if λ t < µ(v t ). Example 2. Consider the problem of warehouse management. A 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 λ t be the current inventory and let the vector state v t 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 λ t falls below a threshold µ(v t ) based on the current vector state v t . Example 3. Consider a smart home server that controls the air conditioner. Let λ t be −(current temperature) and v t be the time of the day and the number of people in the house. The server should turn on the air conditioner only if the temperature exceeds some threshold determined by v t , or, equivalently, λ t < µ(v t ).
Given a threshold policy with threshold function µ(·), we can define the corresponding action-value function by Q µ (λ, v, a). Let ρ µ (λ , v , λ, v) be the discounted state distribution when the initial state is (λ, v) under the threshold policy to a visited state (λ , v ). When the initial state is (λ, v), the expected discounted reward under the policy is Let M be a sufficiently large constant such that λ t ∈ [−M, +M] for all t. Our goal is to learn the optimal threshold function µ φ (v) parametrized by a vector φ that maximizes the objective function

Deep Threshold Optimal Policy for MDPs
In this section, we present a deep threshold optimal policy (DeepTOP) for MDPs that finds the optimal φ for maximizing K(µ φ ).

Threshold Policy Gradient Theorem for MDPs
In order to design DeepTOP, we first study the gradient ∇ φ K(µ φ ). At first glance, computing ∇ φ K(µ φ ) looks intractable since it involves an integral over λ ∈ [−M, +M]. However, we establish the following threshold policy gradient theorem that shows the surprising result that ∇ φ K(µ φ ) has a simple expression.
Theorem 1. Given the parameter vector φ, letρ(λ, v) 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, Proof. Letρ t (λ, v) be the distribution that the state at time t is (λ, v) when the initial state is chosen uniformly at random. Clearly, we haveρ( In other words, for any vector state v, the threshold policy would take the same action under all λ ∈ (M n+1 , M n ), and we use π n+1 (v) to denote this action. We then have where the summation-integration swap in the first equation follows the Fubini-Tonelli theorem and the last step follows the Leibniz integral rule. We simplify the first two terms in the last step by Next, we expand the last term in (4).
Using the same techniques in (4) and (5) In the above equation, expanding the last term in time establishes (3).

DeepTOP Algorithm Design for MDPs
Motivated by Theorem 1, we now present DeepTOP-MDP, a model-free, actor-critic Deep RL algorithm. DeepTOP-MDP maintains an actor network with parameters φ that learns a threshold function µ φ (v), and a critic network with parameters θ that learns an action-value function Q θ (λ, v, a). DeepTOP-MDP also maintains a target critic network with parameters θ that is updated slower than the critic parameters θ. The purpose of the target critic network is to improve the learning stability as demonstrated in [8,19]. The objective of the critic network is to find θ that minimizes the loss function where (s t , a t , r t , s t+1 ) is sampled under some policy with s t = (λ t , v t ). The objective of the actor network is to find φ that maximizes In each timestep t, the environment E provides a state s t to the agent. We set an exploration parameter t ∈ [0, 1) that takes a random action with probability t . Otherwise, DeepTOP-MDP calculates µ φ (v t ) based on v t , and chooses a t = 1(µ φ (v t ) > λ t ). E generates a reward r t and a next state s t+1 . A replay memory denoted by M then stores the transition {s t , a t , r t , s t+1 }. After filling the memory with at least B transitions, DeepTOP-MDP updates the parameters φ, θ, θ in every timestep using a sampled minibatch of size B of transitions {s t k , a t k , r t k , s t k +1 }, for 1 ≤ k ≤ B. The critic network uses the sampled transitions to calculate the estimated gradient of L(θ): Similarly, the actor network uses the sampled transitions and Equation (3) to calculate the estimated gradient:∇

Algorithm 1 Deep Threshold Optimal Policy Training for MDPs (DeepTOP-MDP)
Randomly select initial actor network parameters φ and critic network parameters θ. Set target critic network parameters θ ← θ, and initialize replay memory M.
Otherwise, select action a t randomly.
Execute action a t , and observe reward r t and next state s t+1 from E. Store transition {s t , a t , r t , s t+1 } into M. Sample a minibatch of B transitions {s t k , a t k , r t k , s t k +1 }, for 1 ≤ k ≤ B from M. Update critic network parameters θ using the estimated gradient from Equation (7). Update actor network parameters φ using the estimated gradient from Equation (8).

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 a 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 E i , is an MDP with a discrete state space s i,t ∈ S i , and a binary action space a i,t ∈ A := {0, 1}, where a i,t = 1 means that arm i is activated, and a i,t = 0 means that arm i is left passive at time t. Given the state-action pair (s i,t , a i,t ), E i generates a random reward r i,t and a random next state s i,t+1 following some unknown probability distributions based on (s i,t , a i,t ). Here we also user i (s i , a i ) to denote the unknown expected one-step reward that can be obtained for the state-action pair (s i , a i ).
A control policy over all arms takes the states (s 1,t , s 2,t , . . . , s N,t ) as input, and activates V 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 an arm's states using a Whittle index function for each arm W i : S i → . Based on the assigned Whittle indices W 1 (s 1,t ), W 2 (s 2,t ), . . . , W N (s N,t ) , the Whittle index policy activates the V highest-valued arms out of N arms in timestep t, and picks the passive action for the remaining arms.

The Whittle Index Function as The Optimal Threshold Function
To define the Whittle index and relate it to threshold functions, let us first consider an alternative control problem of a single arm i as environment E i with activation cost λ. In this problem, the agent follows a control policy that determines whether the arm is activated or not based on its current state s i,t . If the policy activates the arm, then the agent must pay an activation cost of λ. Hence, the agent's net reward at timestep t is defined as We now consider applying threshold policies for this alternative control problem. A threshold policy defines a threshold function µ i : S i → that maps each state to a real value. It then activates the arm if and only if µ i (s i,t ) > λ, i.e., a i,t = 1(µ i (s i ) > λ). The value of µ i (s i,t ) can therefore be viewed as the largest activation cost that the agent is willing to pay to activate the arm under state s i,t . To characterize the performance of a threshold policy with a threshold function µ i (·), we let ρ µ i ,λ (s i , s i ) be the discounted state distribution, which is the average discounted number of visits of state s i when the initial state is s i under the threshold policy and λ. When the initial state is s i , the expected discounted net reward under the threshold policy is The performance of the threshold policy under a given λ is defined as . The Whittle index of this arm is defined as the function µ i (·) whose corresponding threshold policy maximizes J i,λ (µ i ) for all λ: We note that, for some arms, there does not exist any function µ i (s i ) that satisfies the condition in Definition 1. For such arms, the Whittle index does not exist. We say that an arm is indexable if it has a well-defined Whittle index function. Definition 1 shows that finding the Whittle index is equivalent to finding the optimal µ i (·) that maximizes J i,λ (µ i ) for all λ ∈ (−∞, +∞). Parameterizing a threshold function µ φ i i (·) by parameters φ i and letting M be a sufficiently large number such that for all s i and φ i , we aim to find the optimal φ i for maximizing the objective function

Deep Threshold Optimal Policy for RMABs
To design a DeepTOP variant for RMABs, we first give the gradient of the objective function. Theorem 2. Given the parameter vector φ i , letρ λ (s i ) be the discounted state distribution when the initial state is chosen uniformly at random and the activation cost is λ. If all states s Proof. The proof is similar to that of Theorem 1. 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 φ i that maximizes When the arm is indexable, the resulting threshold function µ φ i i is the Whittle index function. Using the gradient result from Equation (11), we present the algorithm DeepTOP-RMAB for finding the optimal parametrized threshold functions µ φ i 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 λ is an artificial value that only exists in the alternative problem but not in the original RMAB problem. Similar to DeepTOP-MDP, we maintain three network parameters for each arm i: actor φ i , critic θ i , and target-critic θ i . The critic network parametrizes the action-value function, and is optimized by minimizing the loss function with (s i,t , a i,t , r i,t , s i,t+1 ) sampled under some policy. In each timestep t, each arm environment E i provides its current state s i,t to the agent. For each arm i = 1, 2, . . . , N, DeepTOP-RMAB calculates the state value µ φ i i (s i,t ) with the arm's respective actor network parameters φ i . Given an exploration parameter t ∈ [0, 1), DeepTOP-RMAB activates the V arms with the largest µ φ i i (s i,t ) with probability 1 − t , and activates V randomly selected arms with probability t . Based on the executed actions, each arm provides a reward r i,t and the next state s i,t+1 . An arm's transition {s i,t , a i,t , r i,t , s i,t+1 } is then stored in the arm's memory denoted by M i . After filling each arm's memory with at least B transitions, DeepTOP-RMAB updates φ i , θ i , and θ i in every timestep. For each arm i, DeepTOP-RMAB first samples a minibatch of size B of transitions Using the sampled transitions and Equation (11), it estimates the gradient of K i (µ φ i i ) aŝ A gradient update step is taken after calculating the actor and critic networks' gradients. Finally, DeepTOP-RMAB soft updates the target critic parameters θ i using The complete DeepTOP-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 [19] 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://github.com/khalednakhleh/deeptop.

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 [34]. It considers a charging station serving EVs. When an EV arrives at the station, it specifies the amount of charges it needs and a deadline upon which it will leave the station. The electricity price changes over time and we model it by an Ornstein-Uhlenbeck process [30]. In each timestep, the station decides whether to 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. If the station fails to fully charge the EV by the deadline of the EV, then the station suffers from a penalty that is a convex function of the remaining needed charge. A 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-deadline of the current EV. A threshold policy is one that calculates a threshold based on the EV's remaining needed charge and time-to-deadline, and then decides to charge the EV if and only if the current electricity price is below the threshold.
Inventory management problem. We construct an inventory management problem by jointly incorporating a variety of practical challenges, including seasonal fluctuations in demands and lead times in orders, in the literature [28,15,10,27]. We consider a warehouse holding goods. In each timestep, there is a 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 a unit holding cost for each unit of unsold goods. The warehouse manager needs to decide whether to order more goods. When it places an order for goods, there is a lead time of one time step, that is, the goods ordered at timestep t are only available for sale at timestep t + 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 a threshold based on the time of the year and decides to place an order for goods if the current inventory is below the threshold.
Make-to-stock production problem. This problem is considered in [26]. It studies a system that produces m items with W demand classes and buffer size S . Accepting a class v order leads to a reward R v , as long as there is still room in the buffer for the order. The classes of demands are ordered such that R 1 > R 2 > . . . . In this problem, the scalar state is the number of accepted but unfinished 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-MDP against DDPG [19] and TD3 [8], two state-ofthe-art off-policy and model free deep RL algorithms. We use open-source implementations of these two algorithms for [12,7]. We use the same hyper-parameters, including the neural network architecture, learning rates, etc., for all three algorithms. We also evaluate the Structure-Aware Learning for Multiple Thresholds algorithm (SALMUT) [26], a reinforcement learning algorithm that finds the optimal threshold policy. SALMUT requires the vector states to be pre-sorted by their threshold values. Hence, SALMUT can only be applied to the make-to-stock production problem. Details about the training parameters can be found in Appendix D. For the EV charging problem, Yu, Xu, and Tong [34] has found the optimal threshold policy. We call the optimal threshold policy the Deadline Index policy and compare DeepTOP-MDP against it.
Simulations results. Simulation results of the three MDPs are shown in Figure 1. The results are the average of 20 independent runs. Before starting a 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 to 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 to learn the optimal policy for each scalar state independently, and therefore have much worse performance. DeepTOP 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 DeepTOP performs virtually the same as the Deadline Index policy for the EV charging problem in about 2000 timesteps, suggesting that DeepTOP 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. We evaluate two RMABs, namely, the onedimensional bandits from [17] and the recovering bandits from [20].

Simulations for RMABs
One-dimensional bandits. We consider an extension of the RMAB problem evaluated in Killian et al. [17]. Killian et al. [17] considers the case when each arm is a two-state Markov process. We extend it so that each arm is a Markov process with 100 states, numbered as 0, 1, . . . , 99, as shown in Figure 2 where state 99 is the optimal state.
The reward of an arm depends on the distance between its current state and state 99. Suppose the current state of arm i is s i,t , then it generates a reward r i,t = 1 − ( s i,t −99 99 ) 2 . If the arm is activated, then it changes to state s i,t+1 = min{s i,t + 1, 99} with probability p i . If the arm is not activated, then it changes to state s i,t+1 = max{s i,t − 1, 0} with probability q i . In the simulations, we pick the probabilities p i to be evenly spaced depending on the number of arms N from the interval [0.  probabilities q i = p i . 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(z, z max ) , 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, z max } and z max = 100. We also evaluate recovering bandits on three settings of (N, V) = (10, 3), (20,5), and (30,6). More details can be found in Appendix F.
Evaluated policies. We compare DeepTOP-RMAB 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) [1], and neural Whittle index network (NeurWIN) [20]. Simulation results. Simulation results are shown in Figures 3 and 4. It can be observed that DeepTOP achieves the optimal average rewards in all cases. The reason that neural LPQL performs worse than DeepTOP may lie in its reliance on a common Lagrangian. Since the common Lagrangian is calculated based on the Q functions of all arms, an inaccuracy in 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 is not surprising that neural WIBQL performs worse than both neural LPQL and DeepTOP. NeurWIN performs worse than DeepTOP 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 G for the one-dimensional bandits and Appendix H for the recovering bandits.

Related Work
Threshold policies have been analysed for many decision-making problems formed as MDPs. [11] examined the residential energy storage under price fluctuations problem, and proved the existence  of optimal threshold policies for minimizing the cost. [5] 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] to learn a trading policy with price thresholds for intraday electricity markets. [14] considered mean field games in a multi-agent MDP setting, and characterized individual agent strategy with a threshold policy when the mean game admits a threshold policy.
More recently, [31] 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 a distributed threshold-based control policy for graph traversal by assigning a state threshold that determines if the agent stays in or leaves a state. For minimizing the age of information in energy-harvesting sensors, [4] used the finite-difference 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 a 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 multi-threshold structure of the optimal policy with SALMUT implementations in [16] for computing node's overload protection. In contrast to these works, DeepTOP-MDP is 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 a restless arm independently of other arms. However, NeurWIN requires a simulator to train the neural networks. Some recent studies, such as [1,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 DeepTOP: a Deep RL actor-critic algorithm that learns the optimal threshold 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 to compute gradient. Based on the gradient expressions, we design the DeepTOP-MDP and DeepTOP-RMAB algorithm variants and compare them against state-of-the-art 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 is to extend DeepTOP 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.

Appendices For DeepTOP: Deep Threshold-Optimal Policy for MDPs and RMABs A Threshold Optimal Policy Gradient Theorem Proof for RMABs
Proof. Letρ λ t (s i ) be the distribution that the state at time t is s i when the initial state is chosen uniformly at random. We haveρ λ t (s i ) = ∞ t=1 γ t−1ρ t,λ (s i ). Given φ i , we number all states in S i such that In other words, the threshold policy takes the same action under all λ ∈ (M n+1 , M n ), and we use π n+1 (s i ) to denote this policy. We then have where the summation-integration swap in the first equation follows the Fubini-Tonelli theorem and the last step follows the Leibniz integral rule. We simplify the first two terms in the last step by Next, we expand the last term in (15).
Using the same techniques in (15) and (16), we have In the above equation, expanding the last term in time establishes (11). Update arm i's critic network using the estimated gradient in Equation (13). Update arm i's actor network using the estimated gradient in Equation (14). Soft update target critic θ i network parameters: If the agent chooses to charge the vehicle by selecting action a t = 1, the agent then obtains a reward of 1 − λ, and the MDP transitions to the next state v t+1 = (C t − 1, D t − 1). Otherwise for a t = 0, the reward is zero and the MDP transitions to next state v t+1 = (C t , D t − 1).
If the charging spot is empty at the next timestep (i.e. v t+1 = (0, 0)), the environment randomly picks the charge requirement C t+1 and time until deadline D t+1 of the next EV vehicle. For the vehicle occupying the charging station, if it's charge requirement is not met by the deadline, the agent incurs a penalty of F(C t ) = 0.2(C t ) 2 that is subtracted from reward r t . The net reward is then r t − F(C t ).
Inventory management. The warehouse can store a maximum of 1000 items, and is able to purchase new stock in bulks of 500 items. The selling price of a single item is set to 20. The vector state v t is the current market shopping season at time t. The scalar state λ t is the current warehouse inventory count at time t. We set 10 different shopping seasons indexed by b that model the customers' current demand rate. The corresponding demand rates for the seasons are 10 different Poisson distributions with parameters sin(bπ/10) · 300 for 0 ≤ b ≤ 9.
If the agent orders items (i.e. a t = 1), it receives a reward equal to the total items' selling price minus the minimum of remaining inventory count and current demand rate. The next state v t+1 is then the next market season index v t+1 = b + 1 mod 10. Otherwise for a t = 0, the agent holds off on buying new items, and incurs a holding cost from the remaining unsold items. The next state is v t+1 = b + 1 mod 10.
Make-to-stock production. The environment models a queueing system with m servers serving at rate 1/µ and a finite buffer with size S . There are W customer classes each with Poisson mean arrival rate β. The state at timestep t is (λ t , v t ), with the scalar state λ t ∈ {0, 1, . . . , m + S } and the vector state v t ∈ {1, 2, . . . , W}. If the agent picks the passive action a t = 0, then the reward is equal to the holding cost h(λ t ) = −0.1(λ t ) 2 . For action a t = 1, the agent receives total net reward of R v − h(λ t ) if the scalar state λ t = m + S . Otherwise, the reward is the holding cost −h(λ t ).
In the simulations, we set the number of servers m = 50, buffer size S = 50, number of customer classes W = 50, µ = 4, and arrival rate β = 1 for all customer classes. The reward R v is chosen to be evenly spaced between 200 and 10 depending on the number of customer classes W.

D Experiments' Details
For all Deep RL algorithms, we used PyTorch [22] to implement them, with Adam [18] as the optimizer. We used 10 −4 as the learning rate for the actor networks, and a learning rate of 10 −3 for the critic networks. We also set the initial learning rate of action-value function to 0.1 for tabular LPQL and tabular WIBQL. Tabular WIBQL initial learning rate for updating indices is 0.2. The warmup period has 1000 timesteps used for filling the memory M with transitions from random actions. We use a constant t = 0.05 through all timesteps. A discount factor of γ = 0.99 was selected. All neural network layers were initialized using PyTorch's default method. We update parameters using a minibatch size of 64 transitions, with policy updates made at every timestep after the warmup period ends. The neural networks used for results in Section 6 have two hidden layers with sizes [128, 128], with the input layer dimension depending on the state size. Output layer has a dimension of one.
The used code for TD3, tabular LPQL, and tabular WIBQL are licensed under the MIT license. The DDPG code we used is licensed under the Apache license 2.0. All Deep RL algorithms were trained using a computing cluster with 9632 computing cores distributed over 320 nodes. All algorithms were trained using CPU cores.

E Additional MDP Simulation Results Using Different Neural Network Architectures
We provide results here for the considered MDP problems for different neural network architectures. All other hyperparameters were kept the same as described in Appendix D.

F Recovering Bandits' Description
The state s i,t is the waiting time since the arm i was last activated, with the maximum waiting time z max set to 100. If the agent chooses to activate the arm, the arm's state is reset to 1. The arm's reward is provided by the recovering function f (s i,t ), where if the arm is activated, the reward is the function value at s i,t . Otherwise a reward of zero is given if the arm is left passive. The recovering reward function is generated from f (s i,t ) = θ 0 (1 − e −θ 1 ·s i,t ).
We use the same Θ = [θ 0 , θ 1 ] hyperparameters for setting the arms' reward classes as used in [20] and provide them in Table 1.

G Additional One-Dimensional Bandits' Simulation Results Using Different Neural Network Architectures
We provide results here for the considered RMAB problem for different neural network architectures. All other hyperparameters were kept the same as described in Appendix D.