Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper focuses on robust RL, especially developing a efficient algorithm for computing the Bellman operator for S-rectangular robust MDP (RMDP) with $L_{\infty}$-constrained rectangular ambiguity sets. To achieve that goal, a homotopy continuation method combined with a bisection method is introduced. Besides, theoretical analysis is made to prove the correctness of the proposed method. Experimental results on inventory management problem, riverswim domain, and machine replacement domain are provided, comparing with "Gurobi LP" method.
main_review: - Originality: although this work extends the previous research on SA-rectangular RMDP, it is still novel to combine the homotopy method with bisection method, in order to solve RMDP with S-rectangular ambiguity sets. 

- Significance: robust RL is of great importance to RL community. This work focus on the aspect of computing an optimal policy for the worst plausible realization of the transition probabilities.

- The relationships with the literature on computing the worst-case realization of transition probabilities are correctly reported; the theoretical analysis is detailed and sound; the empirical evaluation is demonstrated to support its claim on improving the efficiency.


-------------------------------------------------------------------
Updates:
I have read the author's response and other reviews. My concerns have been addressed by the rebuttal, therefore I am inclined to maintain my original score.
limitations_and_societal_impact: - Notations and definitions should be clear. For exmaple, there is no definition for $\xi$ in Eq.(3). Also, the subscript of $B$ in $\mathcal{R},\mathcal{D},\mathcal{N},\mathcal{T}$ in line 149 should denote the basis, but there is no definition.

- "Fig" and "Figure" are both used, but it should be consistent to use either one only.

- In line 135, it is reported that "an arbitrarily small value" will be added to the elements of $z$ to "ensure that they are all distinct". It's better to elaborate this a little bit in the appendix.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes to solve robust Markov decision processes, which are building blocks of robust reinforcement learning. The article derives new properties of S- and SA-rectangular Bellman operators. Based on these properties, the proposed algorithms for S- and SA-rectangular Bellman operators are exact and efficient in practice. Moreover, they compare favorably with the state-of-the-art, the best linear program solvers on the market. 
main_review: ** Originality 

To the best of my knowledge, the contributions of the paper are original. The authors identify new structural properties in the SA-rectangular Bellman operator, show how the homology algorithm can exploit them, and then extend the approach to the case of the S-rectangular  Bellman operator. That is quite a remarkable technical work. Furthermore, the complexity analysis of the algorithm proves a significant reduction compared to state-of-the-art, and the empirical evaluation confirms it. 

** Quality 

I did not find any false notes in the derivations. However, I did not do a detailed reading of the evidence. The empirical analysis was restricted to the performance evaluation of the Bellman operators. That is already good. For a better assessment of the contribution, performances as soon as the operators are integrated into the algorithms for solving robust Markov processes would have been welcome.  

** Clarity 

The paper is very well written and structured. Furthermore, the preliminaries of the paper allow the reader not familiar with the subject to have a good understanding of the problem attacked in this paper. 

Example 3.1 deserves a little more elaboration. I failed to interpret Figure 2 correctly. 

Line 139 - "one actions" -> one action? 



** Significance 

The work is essential to the robust reinforcement learning community and may also interest the broader NeurIPS community. The impact is on the efficiency of solving the Bellman S- and SA-rectangular operator. 

The significance would have been even greater if the authors had demonstrated the impact of the developed operators into algorithms for solving robust Markov decision processes. 

limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper presents a fast algorithm for robust MDPs, specificially S-rectangular rmdps with L_inf constrained rectangular ambiguity sets. The main method proposed is to use homotopy and bisection. The authors compare their algorithm with Gurobi a leading LP solver on "inventory management" domain. 
main_review: First, let me tell you that I was not familiar with robust MDPs before reading this paper. 
The paper is well written and it introduces the concepts used by referring to the appendix and / or other papers. Probably due to lack of my background knowledge, I had a very hard time following and understanding the paper. I carefully followed the definitions and equations at first, but understanding it fully required me to read other papers, and some chapters from the books. At some point, I gave up on completely understanding the concepts and read the paper without being able to verify the low-level details. In my opinion, a paper can be written in a way that makes it easy for people not familiar with the exact concept that the authors are building upon, but this is my personal opinion and I'm not an expert on robust MDPs, so I will leave this judgement to other reviewers.

Despite my lack of knowledge, at the very high level, the paper appears to be sound and well written. Three very high level questions that I had were:
 - What is an example application of robust MDPs? The authors improve the speed upon LP solvers, but what kind of real world (or RL benchmark) problems we would be able to solve with this additional efficiency?
 - If the proposed algorithm is "up to 800 times faster" than LPs, would it be possible for the authors to apply it to problems with more than 30 states? Wouldn't that show the real strength of the algorithm?
 - Maybe I missed this information, but what stops this algorithm from working with RMDPs ambiguity sets such as L2 norm or KL divergeance?
limitations_and_societal_impact: The paper does not comment on the potentials societal impact. It contains some information about technical limitations of the work as a future work (such as not handling RMDPs with more complex ambiguity sets).
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper proposes a novel algorithm for computing the Bellman operator in robust MDPs with S-rectangular ambiguity sets on transition probabilities constrained by L-infinity norm. The algorithm is based on homotopy continuations and a bisection method, and results in orders of magnitude faster computation than existing algorithms based on linear programming, as verified empirically on problems with hundreds of states. This is a very impressive speed-up that allows significant increase in the size of robust MDPs that can be solved exactly. 
main_review: The proposed solution based on homotopy continuations and bisection is very original and completely different from the existing method based on linear programming. Related work is adequately cited. 

The quality of the paper is high. Theoretical analysis is sound, and the empirical evaluation is fair. The authors are comparing their method against the baseline linear programming method implemented using a fast commercial linear programming solver. The presented method is a complete piece of work. 

The empirical demonstration demonstrates a spectacular speed-up with respect to the baseline method based on LP, but I am not so sure about the authors' claim that the proposed method has quasi-linear complexity in the size of the state space. The line graph for the computational time of the homotopy method in Fig. 5 looks very much like a straight line to me, which implies polynomial complexity. Furthermore, if I understand correctly, what is plotted in this graph is the ratio wrt the time it would take to do a Bellman back-up for a single state in regular, non-robust MDP, and if done directly, this operation is quadratic in the size of the state space for this inventory management example, where the number of actions is equal to the number of states. Wouldn't that make the absolute computational time of the homotopy algorithm scale not quasi-linearly with the size of the state space, but polynomially, with a rather high degree? I am not questioning the excellent computational performance of the algorithm, which alone looks sufficient for the acceptance of the paper to me, but perhaps the claim about its quasi-linear complexity should be explained a bit better.

The paper is very clearly written and organized. A minor typo, on line 139: "one actions" -> "one action". The results are very important, and of very high practical significance. The major computational speed-up provided by this algorithm allows solving of robust MDPs of sizes approaching industrial interest. The method does not appear to be very hard to implement, either. It is very likely that this method will be adopted by practitioners in the field of operations research.   

Update: I am happy with the clarification the authors provided about the complexity of the algorithm, and trust it will find its way in the final version. I also realized that my rating was a bit of an outlier, so I revised to be more in line with the other ratings.

limitations_and_societal_impact: I do not see any potential negative societal impacts of this work.
review_title: null

Meta-review: This appears to be a solid paper with the most confident reviewers having the most favorable opinions. There reviewers had some minor quibbles that should be easily addressed in the final version.

Decision: Accept (Poster)