Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexity

We sincerely thank the reviewer for a thorough examination of our paper and for giving critical and valuable feedback! Prior to addressing the reviewer's comments, we would like to note that, due to the revision, reference/equation/theorem numbers may differ. To maintain consistency with the reviewers' comments, our responses will refer to the original version's reference/equation/theorem numbers unless explicitly specified otherwise. Additionally, based on the insightful suggestion of Reviewer RSEz, we changed the term 'regularized robust MDP' to 'soft robust MDP'.

We now address the reviewer's questions and concerns as follows:

Weakness:

• 'The authors fail to explicitly differentiate between stationary and non-stationary policies, as well as between stochastic and deterministic policies. While Equations (1) and (2) suggest that the authors are considering a robust MDP with a non-stationary and deterministic policy, Equations (7) and (8) indicate a stationary and stochastic policy for the risk-sensitive MDP. A similar inconsistency is observed in the transition kernel: while the robust MDP seems to consider the worst-case transition kernel for each time horizon (as evidenced by the decision variables in the infimum problem of Equations (1) and (2)), the risk-sensitive MDP presumes the existence of a transition kernel that is independent of time.'

We sincerely apologize for the confusion. However, we would like to clarify that our definitions and derivations are technically correct. For the sake of generality, in Eq (1),(2) and (3) of the definition of robust MDP, we allow the policy as well as the transition kernel to be non-stationary. However, Theorem 2 points out that the sup-inf solution of equation (1)(2)(3) can be obtained by stationary policies and stationary transition kernels (Eq (11),(12)). Thus it is sufficient to restrict the later discussions to stationary policies and transition kernels, which is why our definition of value functions (e.g. Eq (4) and (7)) are only defined for stationary policies. Regarding the reviewers' concern about the differentiation between deterministic policies and stochastic policies, we apologize for our inaccurate notations which caused this confusion. The optimal value function is actually defined as the supremum over all possible policies which can be potentially stochastic, non-stationary and non-Markovian. However, the optimal solution can be obtained by a deterministic stationary Markov policy. We have updated our definition of equation (1)(2)(3) and added the above discussion as a footnote in the revised paper (highlighted in blue).

We would also like to note that our definition and analysis resemble the standard argument for risk-neutral MDP counterparts, where the original definition of the optimal value function considers taking the supremum over all possible non-stationary, even non-Markovian policies, yet it is shown that the optimal policy can be obtained by a stationary deterministic Markov policy. We hope that the above discussion clarifies the reviewer's confusion and we are open to further discussions if there are any follow-up questions from the reviewer.

Questions:

• 'Within the framework of risk-sensitive MDP, the value function for a given policy $\pi$, denoted as $\widetilde{V}^\pi(s)$, is defined by equation (7). The optimal value function, $\widetilde{V}^\star$ , is defined as $\max_\pi \widetilde{V}^\pi(s)$. Could the authors elucidate how $\widetilde{V}^\star$ satisfies the equation (9)?'

Thank you for reading carefully into the technical details in the paper! We would like to clarify that the definition of the optimal value function $\widetilde{V}^\star$ is actually initially defined as Eq (9) and then in Theorem 2, we show that $\widetilde{V}^\star(s) = \max_{\pi} \widetilde{V}^\pi(s)$, i.e. the optimal value function can be achieved by a Markov policy, which is proved in Appendix E at the beginning of page 24, where it shows that there exists a $\pi^\star$, such that $\widetilde{V}^\star = \widetilde{V}^{\pi^\star}$.

We sincerely thank the reviewer for appreciating the contribution of our work! Prior to addressing the reviewer's comments, we would like to note that, due to the revision, reference/equation/theorem numbers may differ. To maintain consistency with the reviewers' comments, our responses will refer to the original version's reference/equation/theorem numbers, unless explicitly specified otherwise. Additionally, based on the insightful suggestion of Reviewer RSEz, we changed the term 'regularized robust MDP' to 'soft robust MDP'.

We now address the reviewer's questions as follows:

• 'Could the authors provide some examples where theorem 2 is applied to establish the equivalence between some popular regularized RMDPs and risk-sensitve MDPs?'

One example of the soft RMDPs and risk-sensitive MDPs is the soft-KL RMDP, which is equivalent to the risk-sensitive MDP with entropy regularizer. This example is discussed in more detail in Section 5 of the paper.

Another example can be the risk-sensitive MDP with Conditional value at risk (CVaR, see Example 2 in the original version). Leveraging Theorem 2, it is equivalent to the RMDP with uncertainty set $\frac{\widehat{P}(s'|s,a)}{P(s'|s,a)}\le {\alpha^{-1}}, \forall ~s',s\in\mathcal{S}, a\in\mathcal{A}$

• 'In section 2, the authors introduce convex risk measures, where there is only one input in the measure $\sigma$ in (5) and (6), while there are two in examples 1 and 2. Could the authors explain what is the difference between these two $\sigma$'s?'

Thank you for the question! In the paper, we provide an explanation after Theorem 1 that clarifies the two inputs in the risk measure $\sigma$ as well as the penalty function $D$, which we quote as follows: 'In most cases, the convex risk measure $\sigma(V)$ can be interpreted as the risk associated with a random variable that takes on values $V(s)$ where $s$ is drawn from some distribution $s\sim\mu$. Consequently, most commonly used risk measures are typically associated with an underlying probability distribution $\mu\in\Delta^{|\mathcal S|}$ (e.g., Examples 1 and 2). This paper focuses on this type of risk measures and thus we use $\sigma(\mu,\cdot)$ to denote the risk measure, where the additional variable $\mu$ indicates the associated probability distribution.
Correspondingly, we denote the penalty term $D(\hat{\mu})$ of $\sigma(\mu,\cdot)$ in the dual representation theorem as $D(\hat{\mu},\mu)$.' We hope that this answers the reviewer's question and we are happy to further discuss if there are any parts that remain ambiguous.

• 'What is "direct parameterization"?' and 'About the feasible region $\mathcal X$ of $\theta$ : why it is of dimension $SA$ ? And why each subvector $\theta_s$ should be in the probability simplex?'

Direct parameterization is one of the most commonly considered approaches to parameterize a policy in theoretical RL (c.f. [2]). As we have stated before Corollary 1, 'for direct parameterization, the parameter $\theta_{s,a}$ directly represents the probability of choosing action $a$ at state $s$, i.e., $\theta_{s,a} = \pi_\theta(a|s)$.' We have also added some standard references for direct parameterization in the same paragraph.

Given this definition of direct parameterization, $\theta$ is of dimension $SA$ because for each $s$ and $a$, there's a corresponding entry $\theta_{s,a}$ that represents $\theta_{s,a} = \pi_\theta(a|s)$. Further, the subvect $\theta_{s}$ represents $\theta_s = \pi_\theta(\cdot|s)$ which lies in the probability simplex. We hope that the above response answers the reviewer's question!

'Is the right-hand side of (15) independent of the initial distribution $\rho$?'

Thank you for reading into the technical details. The right-hand side of (15) is actually dependent on the initial distribution $\rho$ because the discounted state visitation distribution $d^{\pi_\theta, \widehat P^\theta}$ (defined in Section 2) is dependent on $\rho$.

• 'Assumption 1, typo in the first sentence.'

Thank you for pointing out the typo! We have corrected it in the revised paper.

• 'Assumption 3, what is the norm with subscript "$2,\mu$"'?

Thank you very much for the question! We recognized that we didn't give a formal definition of $||\cdot||_{2,\mu}$. We have added the definition to Section 2 in the revised paper, which is stated as below: for any function $f:\mathcal{S}\times\mathcal{A}\to \mathbb{R}$, state-action distribution $\mu\in\Delta(\mathcal{S}\times\mathcal{A})$, the $\mu$-weighted 2-norm of $f$ is defined as

$||f||{2,\mu} =(E_{s,a\sim\mu}f(s, a)^2)^{1/2}$.

We have added the above definition to the preliminary section of the paper (highlighted in blue). We sincerely appreciate your contribution in highlighting this particular omission.

In conclusion, we express our sincere gratitude to the reviewer for the constructive comments and feedback. We are happy to have further discussions if there are any other questions!

[Novelty of Results] The reviewer pointed out that some of the results in this paper follow closely from existing work. Here we respectfully reference the comments from the reviewer and aim to address these observations by clarifying our contributions and novelty in comparison to prior studies.

• 'Theorem 1 comes from [27]. The equivalence between soft robust optimization and convex risk measure is already established in Ben-Tal et al. (2010). It is therefore no surprise that the result in Theorem 2 would hold.'

We would like to first clarify that the dual representation theorem (Theorem 1) is not claimed to be a contribution of our work; instead, we reference this theorem from classical literature, as it forms the foundation for the subsequent content of our paper. Regarding the significance of Theorem 2, we agree with the reviewer that the proof intuition follows from Theorem 1 and it might not be surprising for readers who are familiar with both dynamic programming and risk measures. However, we would like to note that it is not a direct or trivial generalization of Theorem 1, as it considers the MDP setting, which has a sequential structure that is more complicated than the static setting considered in Theorem 1. The proof (detailed in Appendix E) also requires a careful combination of dynamic programming with the dual representation theorem. As far as we know, although there are many works that discuss the relationship between robustness and risk-sensitivity (see Appendix A in our paper for more detail), there's no result that explicitly states the exact equivalence between (soft) RMPD and risk-sensitive MDP. We believe that Theorem 2, therefore, remains a distinctive and interesting contribution with its own merits.

• 'Theorem 3, Lemma 2, and Theorem 4 extend the result of [85] from robust MDP to the slightly more general regularized/soft robust MDP.'

Thank you for the comment and for directing us to the most related literature [85]. Here we briefly list the major differences between our paper and [85]. Firstly, we obtain an explicit analytical form of the policy gradient in Theorem 3, whereas in [85], they consider the Moreau envelope of the value function and it is implicitly computed through a double-loop manner. This immediately leads to the next two differences--different algorithm designs and different theoretical bounds. [85] needs to consider a modified policy gradient with a double-loop, whereas our algorithm removes the double-loop and studies policy gradient without modification. Given the simpler algorithm design, our iteration complexity also has a better dependency on the size of the state and action spaces $|\mathcal{S}|,|\mathcal{A}|$ as well as the distributional shift factor $M$ (denoted as $D$ in [85]). However, we also acknowledge that [85] has considered settings more general than our paper, e.g. it also takes the $s$-rectangularity setting into consideration. It would be an interesting next step to see if we could combine insights from both works to have more general and improved results.

• 'Section 5 proposes an algorithm that resembles the approach presented in [24] although I am not aware of a sample complexity result for that class of algorithm.'

We express our gratitude to the reviewer for recognizing the novelty of our sample complexity result. We would like to first clarify that the objective function considered in [24], namely the exponential utility, differs from our objective function (see more elaboration in the third paragraph in 'Other related works' in Appendix A). Additionally, the learning settings as well as the algorithms are different. [24] considers online learning in the tabular setting and the algorithm is based on Q-learning, whereas we consider offline learning with function approximation and the algorithm resembles policy iteration type of algorithms.

[Proof to verify] The reviewer suggests a more detailed verification of equation (25) on page 34. We have already added more details for (25) to the revised paper (highlighted in blue on page 31 in the revised version). However, we find that equation (25) is on page 27 instead of page 34, so we are uncertain if we've tackled the right equation that the reviewer questioned. We would be happy to discuss the technical proofs if there are still equations that are unclear.

We sincerely thank the reviewer for carefully reading our paper, acknowledging our contributions, and giving insightful and critical feedback! Prior to addressing the reviewer's comments, we would like to note that, due to the revision, reference/equation/remark numbers may differ. To maintain consistency with the reviewers' comments, our responses will refer to the original version's reference/equation/theorem numbers unless explicitly specified otherwise. We now address the concerns raised by the reviewer in the 'Weakness' section as follows:

[Term of 'regularized robust MDP'] The reviewer pointed out that the term 'regularized robust MDP' might be misleading. We sincerely thank the reviewer for presenting more accurate alternatives and providing related references. After reading the references, we fully agree with the reviewer that 'soft robust MDP' indeed encapsulates the intended concept more accurately. We have changed the name of the term to `soft RMDP' and added related references in our revised paper. We will use soft RMDP in the response as well.

[Limitation of Theorem 2] The reviewer has pointed out several limitations of Theorem 2, which we summarize below: 1. The equivalence only holds for convex risk measures (referred to as 'quasi-concave/mixture quasi-concave' by the reviewer) and does not generalize to other risk metrics such as mean (semi-)deviation and mean (semi-)moment measures in Delage et al. (2019) ; 2. The equivalence would fail if policy regularization is added to the objective function, in which case the optimal policy might be stochastic. 3. The risk-sensitive MDP underestimates the risk caused by the stochasticity generated by the policy.

We now address the reviewer's comments point by point:

For point 1, we agree with the reviewer that the equivalence no longer holds if we consider other risk metrics other than convex risk measures. However, we would like to note that the convex risk measure is an important risk metric and is commonly used in finance and operations research. Consequently, our findings establish a meaningful foundation for exploring risk-sensitive sequential decision-making, albeit within the confines of convex risk measures. An intriguing avenue for future research would involve investigating reinforcement learning or sequential decision-making in the context of diverse risk metrics. However, given the distinct properties of risk metrics like semi-deviation and semi-moments in comparison to convex risk measures, different theoretical tools may be necessary, which poses challenges to the analysis, and unfortunately falls outside the current scope of this paper.

For point 2, we would like to clarify that this is actually not the case: the equivalence between the value functions of risk-sensitive MDPs $\widetilde V^\pi$ and soft RMDPs $\overline V^\pi$ will still hold under most classical policy regularization methods (e.g. entropy regularization). Note that Theorem 2 holds not just for deterministic policies, but also for stochastic policies. For a policy $\pi$, adding regularization only requires changing the reward function $r(s,a)$ to be $r^\pi(s,a) = r(s,a) + \mathcal{R}(\pi(\cdot|s))$, where $\mathcal{R}$ is the policy regularizer. In this setting, the proof of Theorem 2 can still carry through naturally. We have added the above discussion as a footnote in the revised paper (highlighted in blue).

For point 3, we would like to first thank the reviewer for the insightful comment! The reviewer is correct that the proposed risk-sensitive MDP focuses on the risk induced by the uncertainty set but does not consider the risk caused by the stochastic policy. However, we would like to emphasize that this different definition of risk has its advantages. Although the formulation of risk-sensitive MDP differs from the standard definition of dynamic risk (Pichlet et al. 2021), which we believe is the same definition as the Markov risk measure [67], they both yield identical optimal values and optimal policies (see Remark 2 and Appendix C for more detail). Further, this different formulation results in a cleaner equivalence with (soft) RMDPs and better convergence property compared with directly optimizing the Markov risk measure, which is known to be possibly non-gradient dominant (c.f. [36]) Consequently, our results provide an alternative approach for the efficient optimization of the Markov risk measure, despite modeling risk in a different manner. However, we also agree with the reviewer that optimizing the Markov risk measure with policy regularization would potentially result in a different optimal solution compared with the solution of our risk-sensitive MDP with policy regularization.

[In Response to 'Authors falsely claim that all convex risk measure are mixture quasiconcave'] We sincerely thank the reviewer for providing detailed clarifications to help resolve misunderstandings and miscommunications. We now have a better understanding of the source of the misunderstanding. We concur with the reviewer that for the statement 'the optimal solution of Markov risk measure and risk-sensitive MDP is the same' to be accurate, apart from showing that the optimal solution of risk-sensitive MDP is deterministic (which is proved in Theorem 2), we must also ensure that the optimal solution of the Markov risk measure is deterministic, which requires further assumption of mixture quasiconcavity. We have made revisions in Remark 2 as well as Appendix C. Here we quote the sentences from the revised Appendix C: 'Additionally, when the risk-measure $\sigma$ is mixture quasiconcave (c.f. Delage et al.), it can be shown that the optimal policy $\pi$ for the Markov risk measure can also be chosen as a deterministic policy; thus under this case the Markov risk measure and the risk-sensitive MDP obtain the same optimal value, i.e. $V_{MRM}^\star = \widetilde V^\star$. However, we would also like to emphasize that when adding policy regularization or that the risk measure $\sigma$ is not a mixture quasiconcave (e.g. mean semi-deviation), the optimal policy might no longer be a deterministic policy. In this setting, the optimal policy and optimal value of the Markov risk measure and the risk-sensitive MDP may not be the same.'

Moreover, in case there is still unclearness or miscommunication since there are several ``equivalence'' being discussed, we would like to summarize a few points here, 1) The main equivalence theorem, Theorem 2, focuses on the equivalence of soft robust MDP and risk-sensitive MDP proposed in the paper. This theorem is accurate and it does not discuss the relationship of the optimal solution of Markov risk measure and risk-sensitive MDP. 2) Remark 2 and Appendix C discuss the relationship between the risk-sensitive MDP and Markov risk measure. We have revised the remark and appendix based on the discussion.

Again, we would like to express our regards and gratitude for the reviewer's time and effort in keeping the discussion and clarifying the confusion. We remain at the reviewer's disposal for any points requiring further discussion.

[In Response to 'Further comments on limitation 2 and 3 of Theorem 2'] We apologize for misunderstanding the reviewer's comments. Previously, we interpreted the $\rho$ in $\rho(\sum_t^T\gamma^t r(s_t,a_t))$ in the reviewer's comment to be any type of coherent risk measures. After reading the reviewer's clarification, we agree with the reviewer that when $\rho_{0,T}$ is a time-consistent dynamic risk measure, it can be written as, $\rho_{0,T}(r_1, r_2, \ldots, r_T) = r_0(s_0, a_0) + \rho_0(\gamma r_1(s_1,a_1) + \dots + \rho_{T-1}(\gamma^T r_T(s_T, a_T)))=\rho_0(\rho_1(\ldots \rho_T(\sum_{t=0}^T \gamma^t r(s_t,a_t))\ldots))$, where $\rho_t, t=0,\ldots, T$ are one-step conditional risk measures as defined in [71] and satisfy the properties listed in the bottom of p.241. Since we consider a different risk measure, it can no longer be written in this formulation. We have added a footnote in Remark 2 (highlighted in blue) to emphasize that our definition is different from the usual interpretation of the dynamic risk measures formulation of the risk-averse MDP problems.

We would like to thank the reviewer again for the timely replies and active discussions. We hope that our paper revision as well as response clarifies the miscommunication and addresses the reviewer's questions and concerns. We are more than happy to engage in further discussion if there are any additional questions or concerns from the reviewer.

We first sincerely thank the reviewer for carefully reading our paper and appreciating our contributions! We greatly appreciate the constructive suggestions and valuable questions from the reviewer. Prior to addressing the reviewer's comments, we would like to note that, due to the revision, reference/equation/remark numbers may differ. To maintain consistency with the reviewers' comments, our responses will refer to the original version's reference/equation/theorem numbers unless explicitly specified otherwise. Additionally, based on the insightful suggestion of Reviewer RSEz, we changed the term 'regularized robust MDP' to 'soft robust MDP'. We now address the questions and concerns raised by the reviewer as follows:

Response to the reviewer's concerns in the 'Weakness' section:

[Comparison with [18] and [32]] The reviewer raised the question of how our regularized MDP compares with the regularization term in [18]. We would like to first apologize for our misleading use of the term 'regularized robust MDP' (which is also pointed out by the third comment in the 'weakness' section of Reviewer RSEz). As is also pointed out by Reviewer RSEz, the regularization in [18] and ours are different in the sense that the 'regularized MDP' in [18] considers regularization on the policy whereas in our setting the regularization is on the transition probability matrices. To avoid confusion, as suggested by Reviewer RSEz, we have changed 'regularized robust MDP' to 'soft robust MDP' in the revised version of the paper. Thank you for raising this valuable question!

The reviewer also asked whether the same convex formulation in [32] applies to the regularized RMDPs (soft RMDPs). We are also interested in the same question and we actually had a brief discussion with one of the authors in [32]. Based on the discussion and our preliminary attempt, it might not be a trivial combination, and it is an interesting future direction to study how to leverage our formulation to get simplified convex formulations for (soft) RMDPs. In response to the reviewer's question of whether the gradient domination property is ensured by the above convex formulation, our current proof leverages the performance difference lemma and the key technique is inspired by the proof of gradient domination in standard MDP [2]. It would be an interesting research topic to study if the gradient domination property can be proved from the convex formulation perspective, but currently, it is unclear to us whether the convex formulation is directly related to the gradient domination property.

[Application of techniques in [101]] The reviewer asked whether we could apply similar techniques in [101] (which we believe is the same reference as [44] in the original paper, we have updated the publisher info of [44] in the revised paper) by explicitly deriving the worst transition model $\widehat{P}^\pi$. We agree with the reviewer that in certain cases the worst-case probability transition model can indeed obtain an explicit/analytical form that can simplify the problem to a certain extent (e.g. entropy risk measure $\widehat{P}^\pi$ takes the form $\widehat{P}^\pi(s'|s,a)\propto P(s'|s,a)\exp(-\beta V^\pi(s'))$). We believe that in this case we could leverage techniques such as importance sampling or rejection sampling to make gradient estimation more amenable. However, based on our own calculation, the sample complexity analysis is more technically involved, which is one of the main reasons why we considered the RFZI algorithm instead of policy gradient algorithm for the sample-based learning setting and we left it as the next step of our research to study the performance of sample-based policy gradient for risk-sensitive MDPs and (soft) RMDPs.