EWoK: Tackling Robust Markov Decision Processes via Estimating Worst Kernel

We extend our gratitude for your valuable and constructive feedback. It is truly encouraging to see the recognition of our efforts in large-scale experiments. Below, we address the comments and questions and are happy to engage in further discussions.

Question 1 (Q1): “The optimal policy”, “The worst-case transition probabilities”: some there are multiple optimal policies/worst-case kernels, I think that the authors should be more careful with the phrasing. I also don’t know what it means to “train” a transition kernel (last sentence of the paragraph after Eq. (7)), and I don’t know what is a “perfect value function” (paragraph before Eq. (14)). I list other inaccurate statements below.

Response 1 (R1): Thank you for pointing out the inaccuracies in our phrasing. In the updated version, we have rectified these to 'An optimal policy' and 'A worst-case kernel'. Concerning 'train a transition kernel', our intent was to refer to the process of learning a parameterized transition model. As for 'perfect robust value function', we aimed to convey that we do not have the true robust value function beforehand in practice. These imprecise statements have been addressed in the updated version.

Q2: The Theoretical results are very weak. Nothing new in Appendix A.1 (proof of Theorem 3.2), it is already in [A].

R2: We agree that Theorem 3.2 is not difficult to derive. We present its proof for the sake of completeness. Our primary contribution lies in two key aspects:

• Conceptually, we show how to use Theorem 3.2 for sampling the worst kernel using the nominal kernel.
• The core theoretical contribution is Theorem 3.5, which is the heart of our algorithm. The update rule in Equation 14 is coupled, i.e., we update the transition kernel $P_{n+1}$ using the value function w.r.t. the kernel $P_n$. Hence, showing its convergence is non-trivial, necessitating a detailed and technical proof in Appendix A.1. We believe this proof does not reside in [A] but rather constitutes our core results.

Thus, we respectfully disagree with the reviewer's assessment of our theoretical contribution as weak.

Q3: Can the EWOK be modified to cope with other uncertainty sets than KL-based uncertainty?

R3: Yes, we believe the high-level idea of EWoK, approximating a worst transition kernel, can be applied in other uncertainty sets than the KL-based one. The key step is to build the connection between a worst transition kernel and the nominal one, and use such connection to obtain samples approximately distributed according to the worst transition probability.

Q4: For completeness, can you recall how to tune $\beta_{sa}$ the uncertainty radius, or give a precise reference for this?

R4: $\beta_{sa}$ is more of a parameter for modeling purposes. In our experiments, we do not tune $\beta_{sa}$ but set $\omega$ and $\kappa$ instead.

Q5: Paragraph after Eq. (7): it is now well-recognized that the minimization problem from Eq. (7) is also an MDP, see for instance Section 3 in [1] or Section 4 in [2]. Can we use gradient-based method in this adversarial MDP to learn the worst-case transition probabilities?

R5: This is a good point. Thank you! We concur that the worst kernel can be computed using gradient descent, as described in Algorithm 2 in [A]. However, the convergene of Algorithm 2 to the worst kernel, has the iteration complexity of $O(\frac{S^3A}{(1-\gamma)^6\epsilon^2})$ (as guaranteed by their Theorem 4.4). In comparison, our method (update rule in our Eqn. 14) has the iteration complexity of $O(\log(\frac{1}{\epsilon}))$. We thank the reviewer for pointing out this direction and we have included the above discussion in the updated version.

[A] Qiuhao Wang,Chin Pang Ho, Marek Petrik. Policy Gradient in Robust MDPs with Global Convergence Guarantee

Thanks for your quick response. I do not agree with some of your statements, as I describe below.

• Difference between nominal MDPs and robust MDPs. I agree with you that RMDPs and nominal MDPs are different and that in some new settings it is important to reprove properties that may seem obvious for nominal MDPs. However, the setting chosen in this paper is sa-rectangular RMDPs with KL-based uncertainty sets, which has been considered in many other papers. It is thus not necessary to reprove Lemma A.5 (monotonicity of the robust evaluation operator) and the other results from Appendix A.3, it suffices to cite the appropriate references.

• Lemma A.4 is not policy iteration. I argue that the update (25), which is the focus of Lemma A.4, is exactly policy iteration, for the adversarial MDP, i.e., for the MDP played by the adversary choosing the transition probabilities $P$. The notion of adversarial MDP is introduced in [1,2,3]. In [3] the authors use policy iteration in the adversarial MDP, see Eq. (7) in [3]. This is exactly the update (25) in your paper.

• Analogy with the seminal papers. The results in Iyengar and Nilim El Ghaoui are non-trivial because these authors work with a max-min optimization problem. In the Appendix A.5 of your paper, only the minimization problem is considered, so that this problem falls in the classical MDP theory (though the action set is compact, but this has been studied in prior work as I explain above).

• Other uncertainty sets. Thanks for the detailed response.

[1] Vineet Goyal and Julien Grand-Clement. Robust Markov decision processes: Beyond rectangularity. Mathematics of Operations Research, 2022.

[2] Chin Pang Ho, Marek Petrik, and Wolfram Wiesemann. Partial policy iteration for l1-robust Markov decision processes. The Journal of Machine Learning Research, 22(1):12612–12657, 2021

[3] GOH, Joel, BAYATI, Mohsen, ZENIOS, Stefanos A., et al. Data uncertainty in Markov chains: Application to cost-effectiveness analyses of medical innovations. Operations Research, 2018, vol. 66, no 3, p. 697-715.

Thank you for your helpful and valuable comments and feedback. We are thrilled to hear that you find the idea of our method to be novel and that our experiments are well-organized and convincing. Below, we address the comments and questions.

Question 1 (Q1): About the Weakness 1 I mentioned, I would appreciate it if the authors could explain more about the empirical choice of the unknown parameter $\omega_{sa}$ (since the empirical average over the samples $s_i'$ from $\bar{P}(\cdot|s,a)$ forms an overestimation of $\omega_{sa}$ as suggested by Proposition 3.4).

Response 1 (R1): Thank you for this thoughtful question. The empirical approximation of $\omega_{sa}$ is mainly motivated by implementation considerations that we only have access to samples from the nominal transition kernel. In the future, we will explore more clever ways to approximate it to mitigate overestimation.

Q2: Some typos and notation clarity: (i) in Eq (12) it should be $\sum^N_{i=1} v(s_i')$; (ii) the notion of $\omega_n$ and $\kappa_n$ is not pre-defined (even with subscript $s,a$). I suggest explicitly giving them a definition (as the parameter associated with the worst-case transition kernel when the target function is $v_{P_n}^\pi$).

R2: Thank you for pinpointing those typos and notation issues! We have fixed them in the newest version.

Thank you very much for your valuable feedback. As the discussion period is nearing its end, we kindly ask if you have any additional questions or concerns. Should all the raised issues be satisfactorily addressed, we hope you might consider adjusting the score accordingly. We look forward to your input and insights!

We express our gratitude for your valuable suggestions and insightful feedback. It is encouraging to to learn of your appreciation for the clarity of our paper and the effectiveness of our EWoK method. Below, we address the questions and comments.

Question 1 (Q1): One reason for not giving a higher score at this point is that it seems to me that all the results in this particular paper are rather intuitive or expected. ... In particular, Theorem 3.5 is a standard result in the analysis of RMDPs, which seems this paper has limited theoretical contributions.

Response 1 (R1): To the best of our knowledge, Theorem 3.5 is novel and not straightforward to prove. It establishes the worst kernel can be found iteratively, while each iteration can be estimated via sampling in a model-free setting. We would like to clarify the convergence in Theorem 3.5 is different from the standard convergence analysis of (s,a)-rectangular RMDP. If the reviewer is aware of any existing results akin to Theorem 3.5, we kindly request a reference and will include it to enhance the accuracy of our paper.

Q2: Another aspect that seems to be lacking is a discussion on how the radius $\beta_{sa}$ of the ambiguity set affects the algorithm's performance, although it would be transferred to new parameters $\omega_{sa}$ and $\kappa_{sa}$. I do expect that the parameter selection procedure could be discussed more.

R2: Thank you for highlighting this point. We would like to clarify that $\beta_{sa}$ is more of a parameter for modeling purposes. In practice, we do not set it directly. In principle, a higher $\beta_{sa}$ means a larger uncertainty set, thus a more conservative policy. However, as all non-tabular experiments never have truly rectangular or KL-constrained uncertainty sets, the influence on practical performance might vary.

Q3: The literature review is not comprehensive. A recent paper [1] also studied RMDPs with global optimality, and it would be helpful if the author discussed it.

R3: Thank you for pointing out this related work. Similar to our work, it also iteratively computes the worst kernel (appearing in its Algorithm 2). However, their method is gradient-based with iteration complexity of $O(\frac{S^3A}{(1-\gamma)^6\epsilon^2})$ (Theorem 4.4 in [1]). In comparison, our method (update rule in our Equation 14) has the iteration complexity of $O(\log(\frac{1}{\epsilon}))$ as stated in our Theorem 3.5. We have included it in the updated version.

Q4: The official definition of the robust Bellman operator should be added in Section 2.3 for completeness.

R4: Thank you for your suggestion. We have addressed it in the new version.

Q5: While we consider a practical problem lying in the KL-based $(s,a)$-rectangular ambiguity set, the only parameter that the agent can choose is $\beta_{sa}$; however, the other two parameters $\omega_{sa}$ and $\kappa_{sa}$ would be settled directly. Could you explain more about the relationship between $\beta_{sa}$ and the other two parameters $\omega_{sa}$ and $\kappa_{sa}$ , or how can the agent reach the latter when setting the former?

R5: Thank you for raising the question. We apologize for the unclarity in our presentation. $\beta_{sa}$ is more of a parameter for modeling purposes, not something chosen by the agent. The connection between $\beta_{sa}$ and the other parameters $\omega_{sa}$ and $\kappa_{sa}$ are described in Eqn.(10) and Proposition 3.3. $\omega_{sa}$ and $\kappa_{sa}$ are the solutions of Eqn.(10), though we can't obtain a closed form for them. In our experiments, we consider $\kappa_{sa}$ as a hyperparameter, and setting it essentially decides a $\beta_{sa}$ for modeling the problem.

Thank you very much for your valuable feedback. As the discussion period is nearing its end, we kindly ask if you have any additional questions or concerns. Should all the raised issues be satisfactorily addressed, we hope you might consider adjusting the score accordingly. We look forward to your input and insights!

We extend our gratitude for your insightful and constructive feedback. We are happy to see your comment that the idea of EWoK is creative. Below, we address the questions.

Question 1 (Q1): I am not convinced yet that EWoK can be applied in a realistic domain as claimed. ... It might be more accurate if the paper reduces the scope to high-dimensional domains.

Response 1 (R1): Thank you for the suggestion. While EWoK shows potential for integration with learned models to get rid of the assumption, we concur that it is more accurate to reduce the current scope to high-dimensional domains. We have revised the paper to embody this change.

Q2: At the end of the experiments section, the paper mentions a larger number of next-state samples does not affect the wall clock time a lot. ... It would be nice to also check a case in robotics, or some other environments taking relatively long time to respond.

R2: Thank you for highlighting this point. We agree that the negligible overhead is due to fast simulation, which may not be available in real-world scenarios. We have revised our paper to reduce the confusion. In real-world cases where sampling next states is time-consuming, it could increase simulation time but we believe that this increase won't be prohibitively expensive in most realistic cases.

Q3: It might be worth checking a more difficult experiment setting, such as the one single trajectory case.

R3: Thank you for the suggestion. Could you provide more details about this specific setting? We would gladly conduct the requested experiments.

Q4: Could the authors provide a learning curve to show how long the method takes to converge? It would be better if the learning curve plot could also include your baselines.

R4: Sure, we have updated the paper and included the learning curves in the appendix (Fig. 13). Thank you for pointing it out.

Thank you very much for your valuable feedback. As the discussion period is nearing its end, we kindly ask if you have any additional questions or concerns. Should all the raised issues be satisfactorily addressed, we hope you might consider adjusting the score accordingly. We look forward to your input and insights!