Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
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. 
questions: However, there are several concerns as stated below.
1.	The 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 
[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.
See Equation (8) in the paper above. 
How is the proposed algorithm in this paper different from the schemes described in these papers? 
2.	It 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 
[b] Marbach, P., & Tsitsiklis, J. N. (2001). Simulation-based optimization of Markov reward processes. IEEE Transactions on Automatic Control, 46(2), 191-209.
3.	In 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. 
4.	In Algorithm 1, why don’t the authors consider a decreasing $\epsilon$? Does constant $\epsilon$ guarantee convergence to the optimal solution?
5.	The 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. 
6.	The 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.

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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
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.

# Strengths:
The 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. 

# Weaknesses:
1. 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.
2. While being important, the theorems are minor, hence they do not compensate lack of experiments

# Minor Comments:
The last part of section 6 seems like it addressed to the reviewers (lines 220-221). Rephrase.
questions: 1. Would you be able to run experiments in more complex domains? 
2. 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.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.

In 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). 

The 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.

in 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.
strengths_and_weaknesses: ## Strengths
- The paper is well-presented and easy to follow. I appreciate the clarity of the presentation and idea.
- The simplified expression of the actor derivative (expected reward derivative) is new.
- Thorough evaluations and experiments

--------
## Weaknesses
- The novelty is incremental. The main contribution is based on the use of threshold policy and simplification of the policy gradient.
- The MDPs and RMABs domains are similar with no major differences.
- The threshold policy considered in the paper can only handle one single scalar, which limits the applicability of the threshold policy.
- [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.
questions: ## Comments
- I think there is a missing integral over $\lambda'$ in the definition of Q function in Equation (1).

## Questions
- 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?
- 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?


References:
[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.
[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.


limitations: ## Limitations
- [Stated by the authors] The algorithm is only applicable to MDPs that admit a threshold policy.
- The proposed algorithm only works with threshold policy with a single scalar value.

## Negative societal impact
N/A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: Originality
To the best of my knowledge the results are novel.

Quality
The theoretical results do not seem very surprising, but I did find them interesting and useful. 

Clarity
The paper is written very clearly. 
The 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?)

Significance
Threshold 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.
questions: The paper is pretty straight-forward and clear. I have no questions or suggestions.
limitations: The paper has no potential negative societal impact.
review_title: null

Meta-review: metareview: The paper considers 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 parameterizations, the results show that their method, DeepTOP, performs better than the compared methods in all the experiments.

The paper is well written and the claims are correct.  The performance of DeepTOP compared to the other methods is impressive.  All four reviewers were on the positive side for acceptance.

confidence: Certain
Decision: Accept