Online Learning in Risk Sensitive constrained MDP

We thank the reviewer for providing thoughtful comments. Please see our responses to your questions below.

For multiple constraints

• As correctly pointed out by the reviewer, the complexity of our approach is affected by the number of constraints. Specifically, extending the method proposed in the paper to multiple constraints requires augmenting the state with multiple budget variables, which leads to an exponential increase in the state space. For $M$ constraints, the size of the augmented state space scales as $(\frac{C}{\epsilon})^M$, where $C$ is the upper bound of the augmented budget $\tau$. We thank the reviewer for highlighting this issue, and we will update the statement in the paper accordingly.

Lack of numerical experiments

• Our main contribution is theoretical in nature. To the best of our knowledge, this is the first work that establishes sublinear regret and constraint violation bounds in the setting where the goal is to maximize the expected cumulative reward subject to an entropic risk constraint on the utility.
• To address this, we leverage the augmented MDP representation of OCE-based risk measures, which includes the entropic risk measure as a special case. This idea originates from [Bäuerle and Ott, 2011], where the authors studied the memory requirements for solving CVAR in the absence of a Bellman equation, and was further developed in [Wang et al., 2024] to reduce OCE problems to standard reinforcement learning.
• Our work is the first to tackle the CMDP setting with an entropic risk constraint, using the augmented MDP framework to address the nonlinearity in optimizing the Lagrangian, and defining a composite value function.
• Note that even though we use an augmented budget, we do not need to augment all the history, rather, we only need to augment the remaining budget from the initial value. Also, since we assume the utilities are deterministic, the transition of the augmented budget is known. Thus, we expect that our approach can be implemented in practice. We will add numerical results in the final version of the paper.

Computational Complexity

• The computational complexity is O(K), i.e. a linear in $K$, and thus, our approach is computationally efficient. In particular, if we discretize $\tau$ with spacing $1/K$, then this will add an additional $H/K$ factor in the regret bound (as the OCE representation for entropic risk measure is 1-Lipschitz) over every episode that results in $O(H)$ regret overall which is independent of $K$. Thus the maximization over $\tau$ can be done in $O(K)$ time, which is linear with $K$, hence, efficient. We have discussed the computational complexity aspect in Section 4 (please see the paragraph just before Section 5). Note that the augmented budget is also considered in the unconstrained entropic risk or CVaR maximization problem [Wang et al.'2023,2024]. They also discretize the augmented budget and the computational complexity is also of the same order as ours.

Lower Bound

• Regarding regret lower bounds for CMDP, there are currently no known results for cumulative reward and utility, making this a largely unexplored area. The presence of an entropic constraint further complicates the analysis due to the absence of strong duality.

Regarding the references

• Thanks for pointing out the references. These are really interesting, and we will include them in the final version. In the following, we recap our contributions to the other works. Note that to the best of our knowledge, this is the first work that achieves sublinear regret ($O(\sqrt{K})$) and sublinear violation bound ($O(K^{3/4})$) for risk-constrained RL problem. Chow et al.'2018 did not consider the regret and violation bound. In order to achieve this, we contribute significantly. We have to use a regularized primal-dual approach, unlike the risk-neutral CMDP setting, as the strong duality does not hold. Further, we cannot apply dynamic programming-based approach to the composite state-action value function because of the non-linearity of the value function with respect to the state-action occupancy measure, and we have to resort to the OCE representation. In the OCE representation, we have to augment the state with a budget, and then we optimize over the budget.
• Some studies also use an LP-based approach to bound the regret and the violation in the risk-neutral setting. They use the state-action-occupancy measure rather than a policy to optimize. However, the state-action occupancy-based measure (and thus, the LP-based approach) will not work for our problem as the value function is not linear in terms of the state-action occupancy measure.

We thank the reviewer for providing thoughtful comments. Please see our responses below.

Lack of numerical results

• Our main contribution is theoretical. To the best of our knowledge, this is the first work that establishes sublinear regret and constraint violation bounds in the setting where the goal is to maximize the expected cumulative reward subject to an entropic risk constraint on the utility.
• To address this, we leverage the augmented MDP representation of OCE-based risk measures, which includes the entropic risk measure as a special case. This idea originates from [Bäuerle and Ott, 2011], where the authors studied the memory requirements for solving CVAR in the absence of a Bellman equation, and was further developed in [Wang et al., 2024] to reduce OCE problems to standard reinforcement learning. The OCE representation is necessary since the standard dynamic-programming-based approach does not apply to the composite state-action value function. We will add numerical results in the final paper in Appendix.

Dual regularization..

• Minimizing the regularized Lagrangian $V_r^{\pi} + \lambda (V_g^{\pi} - b) + \beta \lambda^2$ with respect to $\lambda$ yields $V_r^{\pi} - \frac{1}{4\beta}(V_g^{\pi} - b)^2$ if $V_g^{\pi} - b < 0$, and $V_r^{\pi}$ otherwise. Thus, adding the regularization is similar to minimizing the $\ell_2$ loss of the constraint violation, which facilitates bounding the violation term. In particular, we show that this regularization leads to an $O(K^{3/4})$ bound on the cumulative violation.

Choice of ERM rather than CVaR..

The entropic risk measure prioritizes policies with desirable robustness and performance trade-offs. Specifically:

• Robustness: The entropic risk measure is connected to robustness. It has been shown that maximizing the entropic risk measure with a risk sensitivity parameter $\alpha$ is equivalent to optimizing the worst-case expected return under a distributional ambiguity. More precisely, this corresponds to maximizing the minimum performance over a set of distributions within a KL ball of radius $\alpha$ around the nominal distribution.

• Dynamic Programming: Unlike CVaR or VaR, the entropic risk measure is smooth and satisfies a multiplicative form of the Bellman equation. This makes it particularly amenable to gradient-based optimization algorithms.

• Sensitivity to the Risk Parameter: As the risk factor $\alpha$ approaches infinity, the entropic risk measure increasingly emphasizes adverse outcomes. However, unlike CVaR, which explicitly focuses on tail risk, it still retains sensitivity to the entire distribution of outcomes.

Implications of the regularization term

• The added regularization ensures the boundedness of the violation, which is essential for our analysis and the derivation of both the constraint violation and the regret bounds. As the regularization parameter increases, the algorithm increasingly prioritizes smaller values of $\lambda$, eventually rendering the resulting algorithm ineffective. Therefore, a small choice of $\beta$ is necessary for maintaining good performance. Specifically, as stated in Lemma 5.2, there exists a trade-off between the step-size and the regularization parameter, i.e., $\beta \eta$ must be smaller than 0.5.

Regarding lower bound

• We thank the reviewer for mentioning the work of [Liang and Luo, 24]. Extending the results of [Liang and Luo, 2024] would be quite challenging, but represents an interesting future direction. Specifically, the distributional RL framework for entropic risk follows a similar multiplicative Poisson equation as the one we study and thus encounters similar challenges to those discussed in our paper.
• Regarding regret lower bounds for CMDP, there are currently no known results, making this a largely unexplored area. The presence of an entropic constraint further complicates the analysis due to the absence of strong duality. Nonetheless, one might be able to extend the general ideas from [Liang and Luo, 2024] by adopting an augmented MDP approach instead. We agree this is a promising direction and have added a sentence discussing it in the paper. Our regret bound is the same as that of the risk-neutral CMDP.

Extending other OCE representations

• The main focus of this paper has been to extend the CMDP framework to the entropic risk minimization setting. To tackle this problem, we leverage the augmented MDP representation introduced by [Wang et al., 2023, 2024]. This approach, however, comes at the cost of discretizing the parameter $\tau$, for which we currently do not have a complete solution. We also acknowledge that the proposed framework can be generalized to a broader class of risk measures that admit an OCE representation. This extension can build upon the ideas of [Wang et al., 2024] and our current analysis. However, such a generalization is non-trivial and involves additional technical challenges that constitute future research direction.

Thanks for providing thoughtful comments. Please see our responses below.

Regarding the computational efficiency...

• Even though the augmented budget can take value in real space, the computational complexity is still O(K), i.e. a linear in K. Thus, it is not true that our approach is computationally inefficient. In particular, if we discretize $\tau$ with spacing $1/K$, then this will add $H/K$ factor in the regret bound (as the optimized certainty equivalent (OCE) representation for entropic risk measure is 1-Lipschitz) over every episode that results in $O(H)$ additional regret overall which is independent of $K$. Thus the maximization over $\tau$ can be done in $O(K)$ time which is linear with $K$, hence, efficient. We have discussed the computational complexity aspect in Section 4 (please see the paragraph just above Section 5). Note that the augmented budget is also considered in the unconstrained entropic risk or CVaR maximization problem [Wang et al'23], and the computational complexity is also of the same order as ours.
• While the augmented budget can take real value, the constrained entropic risk-measure problem is inherently challenging. In particular, one cannot apply the dynamic programming-based approach to the Lagrangian or the composite state-action value function, unlike the risk-neutral CMDP approach. Note that unconstrained entropic risk-sensitive RL admits an optimal Bellman equation and one can directly apply the dynamic programming-based approach there without augmentation. However, we cannot extend those approaches here. Hence, we need to resort to the OCE representation of the entropic risk measure. As a result, we augment the state space with the budget and then solve for the optimal budget.

..the novelty of the approach is limited.

In the following, we state the novelty of our proposed approach.

• Our study shows that in the constrained entropic risk-sensitive RL problem one cannot apply the dynamic programming-based approach on the composite state-action value function, unlike the risk-neutral CMDP approach. Hence, we need to resort to the OCE representation of the entropic risk measure. The key here is that we can write the Bellman equation there for the composite state-action value function in the OCE representation. Hence, one can obtain an efficient computation approach.
• The additional challenge comes from the fact that the entropic risk measure is not linear in the state-action occupancy measure even with the augmented state-spaced. Hence, the traditional primal-dual-based approach cannot be applicable to bound the violation, unlike the risk-neutral CMDP setup. We resort to the regularized primal-dual-based approach.
• Further, for the unconstrained augmented MDP problem, one uses the fact that the greedy policy is optimal with respect to the augmented problem to achieve the bound. However, in the constrained setting, the greedy policy with respect to the composite state-action value function (in the augmented state space) might not be feasible and, hence, might not be optimal. Hence, we have to use novel proof techniques.
• Overall, to the best of our knowledge, this is the first result that shows that $O(\sqrt{K})$ (sublinear) regret and the $O(K^{¾})$ (sublinear) violation bound is achievable in the constrained risk-sensitive setting. In order to achieve this, we have to identify and apply tools in a novel manner and this will influence many new approaches in the future.

Other violation metric..

• The violation metric we consider is common in the risk-neutral CMDP literature. Note that even for this violation metric, the traditional primal-dual-based approach that can bound the violation for the risk-neutral setting is not applicable here since the strong duality may not hold. Hence, bounding this violation metric is challenging in our setting.
• We agree with the reviewer that the truncated violation like $\max(0,B-V_g)$ might be a better alternative for online learning. However, how to achieve optimal regret along with the truncated violation in a computationally efficient manner using a primal-dual approach still remains open even in the risk-neutral CMDP. The recent work [A1] achieves $O(\sqrt{K})$ regret and $O(\sqrt{K})$ truncated violation in the risk-neutral CMDP using a double loop technique. However, the computational complexity of the proposed approach is exponential in terms of $H$ and $K$. We can use a similar technique to bound the truncated violation in our setting. However, the computational complexity will still be exponential. We will mention the above in the final version. Because of the above reason, we did not explicitly consider the truncated violation metric. How to develop a computationally efficient approach to bound both the regret and the truncated violation has been left for the future.

[A1]. Ghosh et al. "Towards achieving sub-linear regret and hard constraint violation in model-free rl." AISTATS,2024.