Online Learning in Risk Sensitive constrained MDP
Authors: Arnob Ghosh
Mehrdad Moharrami
Venue: ICML 2025 poster (2025)
Keywords: Augmented State
Constrained MDP
Risk sensitive RL
Robust RL
Primal-Dual algorithm
Primary area: reinforcement_learning
TL;DR: This is the first result that shows sub-linear regret and violation result for risk sensitive constrained MDP

Abstract: We consider a setting in which the agent aims to maximize the expected cumulative reward, subject to a constraint that the entropic risk of the total utility exceeds a given threshold. Unlike the risk-neutral case, standard primal-dual approaches fail to directly yield regret and violation bounds, as value iteration with respect to a combined state-action value function is not applicable in the risk-sensitive setting. To address this, we adopt the Optimized Certainty Equivalent (OCE) representation of the entropic risk measure and reformulate the problem by augmenting the state space with a continuous budget variable. We then propose a primal-dual algorithm tailored to this augmented formulation. In contrast to the standard approach for risk-neutral CMDPs, our method incorporates a truncated dual update to account for the possible absence of strong duality. We show that the proposed algorithm achieves regret of $\tilde{\mathcal{O}}\big(V_{g,\max}K^{3/4} + \sqrt{H^4 S^2 A \log(1/\delta)}K^{3/4}\big)$ and constraint violation of $\tilde{\mathcal{O}}\big(V_{g,\max} \sqrt{ {H^3 S^2 A \log(1/\delta)}}K^{3/4} \big)$ with probability at least $1-\delta$, where $S$ and $A$ denote the cardinalities of the state and action spaces, respectively, $H$ is the episode length, $K$ is the number of episodes, $\alpha < 0$ is the risk-aversion parameter, and $V_{g,\max} = \frac{1}{|\alpha|}(\exp(|\alpha|H) - 1)$.  *To the best of our knowledge, this is the first result establishing sublinear regret and violation bounds for the risk-sensitive CMDP problem.*

Online Learning in Risk Sensitive constrained MDP
Arnob Ghosh
Mehrdad Moharrami
Abstract
cluding human-level performance on classic Atari 2600 games (Mnih et al., 2015), mastering complex board games such as Go and Chess (Silver et al., 2016; 2017), tack- ling challenging robotic manipulation tasks (Levine et al.. 2016; Haarnoja et al., 2018), optimizing control systems for autonomous vehicles (Sallab et al., 2017), advancing drug discovery by designing molecules with desired proper- ties (Popova et al., 2018), and enhancing the capabilities of Large Language Models to achieve human-level decision- making in natural language understanding and generation tasks (Ouyang et al., 2022: Guo al., 2025). These suc- cesses underscore the versatility of RL in high-dimensional, sequential decision-making problems. However, most of these methods focus on maximizing a single reward sig- nal without regard to auxiliary performance or safety con- straints, which are often critical in real-world applications.
We consider a setting in which the agent aims to maximize the expected cumulative reward, sub- ject to a constraint that the entropic risk of the total utility exceeds given threshold. Unlike the risk-neutral case, standard primal-dual ap- proaches fail to directly yield regret and viola- tion bounds, as value iteration with respect to a combined state-action value function not ap- plicable in the sensistns setting. To address this, we adopt the Optimized Certainty Equiv- alent (OCE) representation of the entropic risk measure and reformulate the problem by aug- menting the state space with continuous budget variable. We then propose a primal-dual algo- rithm tailored to this augmented formulation. In contrast to the standard approach for risk-neutral CMDPs, our method incorporates a truncated dual update account for the possible absence of strong duality. We show that the proposed algorithm achieves regret of ((Va + / HH'S log(1 1og(1/8)<3/1) and constraint viola- tion of Ō(V, max / log(1/8) with probability at least 1 - 8, where S and A denote the cardinalities of the state and action spaces, respectively, H the episode length, K is the number of episodes, a parameter, and Vq gmmxx (exp((aa)))) H)) 1). To the best of our knowledge, this is the first result establishing sublinear regret and violation bounds for the risk-sensitive CMDP problem.
Constrained Markov Decision Processes (CMDPs) provide principled way incorporate such additional constraints into the decision decision-making making process (Altman, 1999b). By ex- tending the standard RL objective to include one or more cost functions, CMDPs enable practitioners to balance pri- mary performance goals against other considerations such as safety (Garcıa & Fernández, 2015), resource alloca- tion (Zhao et al., 2022), or fairness (Jabbari et al., 2017). Various techniques have been proposed solve CMDPs. including primal-dual methods (Efroni et al., 2020) and Lagrangian relaxation (Altman, 1999b; Borkar, 2005).
the risk-aversion
More recently, it has been shown that CMDPs has zero du- ality gap under certain conditions (Paternain et al., 2019), and this result has been leveraged in a series of papers to derive regret bounds for model-free CMDPs (Ghosh et al., 2022: Ding et al., 2021). While these methods are effective for constraints that are linear in cost (e.g., requiring that the expected sum of certain costs remains below thresh- old), many real-world tasks demand handling nonlinear, risk-sensitive constraints that capture higher-order statistics or worst-case scenarios (Chow et al., 2018). Such con- straints are paramount in domains where even a single catas- trophic event is unacceptable, such as in healthcare (Gottes- man et al., 2019). However, incorporating risk-sensitive constraints into CMDPs introduces significant challenges, as the resulting problem often becomes highly nonlinear, and the strong duality properties that simplify solution meth- ods for CMDPs may fail to hold. Motivated by this, we are
1. Introduction
Reinforcement Learning (RL) has achieved remarkable breakthroughs across a wide range of domains, in-
'Equal contribution 'Department of Electrical and Com- puter Engineering, New Jersey Institute of Technology, Newark, USA DDepartment of Computer Science, University of Iowa, lowa City, USA. Correspondence to: Arno Ghosh <arnob, Carnob.ghosh@e ccosh@@njt.cduu
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Online Learning in Risk Sensitive constrained MDP
interested in the following question:
1.1. Related Works
Can we achieve provably efficient learning algorithm for CMDP problem with sisk-sensitive constraints?
In this section, we provide a brief overview of the most rele- vant related work. Specifically, we focus risk sisk-sensitive MDPs and constrained MDPs, the use of entropic risk measures in constrained MDPs remains largely unexplored.
In this work, we study a tropic risk-sensitive constraint. In particular, we consider that the agent seeks to maximize the expected cumulative reward subject to the constraint that the risk tisk-sensttive utility associated with policy remains above a prescribed thresh- old in an online learning setup. Solving this problem exactly is notoriously difficult due to its nonlinear nature and the potential failure of strong duality.
CMDP with an en-
The study of risk sensitive RL traces its origins to economic theory, where risk was incorporated into utility functions to better capture decision- der uncertainty (Hardy, 1923; von Neumann & Morgenstern, 1944; Luce & Raiffa, 1957; Arrow, 1965). Risk sensitive Markov decision processes were first introduced in (Howard & Matheson, 1972), where the standard cost function was replaced by an exponential transformation involving a risk sensitive parameter. This framework is closely aligned with the concepts of robustness (Dai Pra et al., 1996; Hernandez- Hernández & Marcus, 1996), as it balances utility maximiza- tion while accounting for the variance of returns (Whittle, 2002). The use of exponential utility functions effectively penalizes variability in outcomes, thereby mitigating risk in decision-making
Risk Sensitive RL:
un-
Our Contributions:
We show that the proposed algorithm, with probability at least 1 - 5, achieves a regret bound of maV,
V S k//(1 and a constraint violation where S and A denote the cardinalities of the state and action spaces, H the episode length, K the number of episodes, < 0 the risk-aversion parameter, and V max 1 (exp(la H) 1). To the best of our knowledge, this is [o]
bound of (VVg.max H/A
Risk sensitivity entered the control and reinforcement learn- ing literature in the early 2000s (Borkar, 2001; Borkar Meyn, 2002; Borkar, 2002). Since then, significant efforts have been made to understand the behavior of exponential risk sensitive reinforcement learning, with notable recent contributions including (Fei et al., 2020; Murthy et al., 2023; Fei et al., 2024; Moharrami et al., 2024). Simultancously. alternative risk measures such as Conditional Value-at-Riis (CVaR) gained traction (Artzner et al., 1999; Rockafellar & Uryasev, 2000; Wang et al., 2023; 2024). CV&R has become particularly valuable in reinforcement learning ap- plications, it focuses optimizing expected rewards in worst case scenarios (Tamar et al., 2015; Zhao et al., 2024). In this work, we focus on solving the problem where the objective is to maximize the cumulative reward subject to the constraint the entropic risk measure associated with the utility value function above a certain threshold. Hence, it is fundamentally different from the above work.
the first result establishing sublinear regret and violation bounds for the risk-sensitive CMDP problem.
The standard primal-dual approach may not apply in this setting, as the exponential Bellman equation for the composite state-action value function is invalid due to the -on-iine of the entropic risk measure where markovian policy is optimal. Moreover, we show that a Markovian policy might be suboptimal unlike the un- constraned entropic risk measure setting. To address this, we introduce an augmented state space by extending the original state-space with a continuous budget vari- able. We show that, in the risk-averse case (a < 0), the entropic risk associated with policy x can be ex- pressed as max, (r + E[u(G(r) - +))), where u(t)= = (exp(at)= - 1) and G(T) denotes the total utility under policy ा. By reformulating the problem the augmented state space, we can apply a seaieiittratoonbaseee approach compute the composite state-action value function.
Constrained RL: Constrained RL is one of the most active fields at the intersection of constraint optimization, MDPs, and RI. The earliest attempts to integrate constraints into MDP formulations date back to the 1970s (Kolesar, 1970), with more rigorous treatments appearing in the 1990s (Ross, 1989; Altman, 1999a). Optimization techniques for solving constraint problems, such as Lagrangian relaxation (Ev- erett, 1963; Shapiro, 1979), and primal-dual (Efroni et al., 2020) approach have been used to address these challenges, often by converting the constrained problem into an uncon- strained one through the use of Lagrange multipliers (Alt- man, 1998; Bertsekas, 2016). This framework was later adapted to RL (Geibel & Wysotzki, 2005; Uchibe & Doya, 2007: Zheng & Ratliff, 2020; Tessler et al., 2019; Ding
We then apply a primal-dual-basee approach. However, since the entropic risk measure is not linear in the state- action occupancy measure, strong duality may not hold. As result, standard techniques used in the nestaal CMDP setting for bounding constraint violation (Ghosh et al., 2022; Efroni et al., 2020; Ding et al., 2021) are not directly applicable. To address this, we introduce a truncation variable ş and show that it is crucial for controlling both regret and constraint violation.
2

---

Online Learning in Risk Sensitive constrained MDP
al., 2020; Ying et al., 2022). Since then, numerous stud- ies have explored different formulations of constrained ob- jectives within the RL framework, including constraints with auxiliary cost/reward functions (Achiam et al., 2017: Tessler et al., 2019; Ghosh et al., 2022), constraints on the quantile and distribution of returns (Jung et al., 2024),
under policy л E MHD, starting from the state-action pair (s,a), i.e.,
27 (s))
- log (Ex ee (w) 3. s. a))
and constraints on risk measures (Borkar & Jain, 2014; Zhang et al., 2024). Compared the risk-neutral constraints, consider risk-sensitive constraints. Furthermore, to the best of our knowledge, this is the first work that provides the sub-linear regret and violation bound for risk-sensitive constraints setup.
Similarly, the risk-sensitive value function for the utility associated with policy π, starting from state 8 is given by
_ log [E E# (ool s] a
V2 (s)
For a Markov policy x, the state-action value function and the utility-based value function satisfy the following dy- namic programming relations:
2. Problem Formulation
We consider the risk-sensitive CMDP within an episodic framework. The CMDP is defined as (S, A, H, r. g), where S ([S] = S) is the finite state space, A (|AA) A) is the finite action space, and H is the fixed episode length. The transition dynamics are governed by set of transition probabilities P- = {P where (s') s, a) represents the probability of transitioning to state s' from state s at time step h. upon taking action a. The reward and utility functions are denoted by h== and g = {gr H respectively, defined for each time step of the episode and assumed to be deterministic and in [0, 1].
(g, = gh a) + _ log (PreaVaati 1 a Vg. (s)(()) log (100)) x(1ss)))
a
Our objective is to solve the following risk-sensitive con- strained problem:
max V (s1); "EllnD
subject to V (31)
( 2 B, (I)
where B E R is the lower bound on acceptable utility. The goal is to ensure that the entropic risk measure associated with the utility value function is above a certain threshold. We consider the setting where a < 0, indicating that the agent is risk-averse. Here, a denotes the agent's risk toler- ance. As a t 0, the agent approaches risk-neutral behavior and seeks policies whose expected cumulative utility is at least B. Conversely, as 4 -o0 the agent becomes increas- ingly risk-averse and favors policies that yield outcomes with lower volatility and a greater certainty of meeting or exceeding the threshold B. Problems of this type are essen- tial in various applications, including autonomous driving, financial investment, and modeling human behavior.
Each episode 2 O starts at a fixed state 81. At each time step h, the agent observes the state St E S and se- lects an action af E A. The agent then receives a re- ward ra (sh, a and utility Ih (sf, ) Finally, the MDP evolves to sh drawn from PA (a at)) The episode terminates at step H + 1. Without loss of generality, we assume that TH+1 = 9H+1 = O. In this paper, we con- sider the challenging scenario where the agent only observes Th (5% a and 9n (5%, aft) at the visited state-action pairs.
The agent's dieeede-de policy space is denoted by
1MN = {TT T= (--(-11)3mm)
Learning Metric: In this setting, we assume the agent does not have access to the transition probabilities and must learn in an online manner. The agent aims to minimize the following performance metrics:
Tu(: 8hs {aw, aw Mi=l) E A(A), vh E }
where ((A) denotes the probability simplex over the action space. We consider a total of K episodes. For each is < K and h < H, let o denote the policy at time step h of episode
Regret (K)
Σ
(iT((s)
VAT (s1) - Vol
k=
K
The reward value function is the expected total reward H+1 V,", = E, E ru(sk, an)ls s). The constraint is based on the risk associated with the utility function. For risk-sensitive RL with the risk factor a, we denote the risk-sensitive sate-action value function for the utility as 07 S A + R. This function represents the expected cumulative utility, assessed using the entropic risk measure,
Violation
Σ (B k=1
9.1 (s1))
where -² E LHD is the policy deployed at episode k, and x* represents the optimal feasible policy. The regret quantifies the sub-optimality gap, while the violation measures the extent of constraint violations.
3

---

Online Learning in Risk Sensitive constrained MDP
3. Solution Methodology
3.1. Certainty- Representation
We begin by highlighting the challenges in solving the risk- sensitive CMDP compared to the standard CMDP. In the standard CMDP, which corresponds to the risk-neutral sce- nario (a 0), the Lagrangian is solved to derive bound on the learning metric (Ghosh et al., 2022):
To address these issues, we leverage the certainty- equivalence representation of the entropic risk mea- sure (Ben-Tal & Teboulle, 2007). Specifically, for func- tion u(-), the Optimized Certainty Equivalent (OCE) as- sociated with a π E IH is defined as OCE, 8)
max, { { E
u E Ih (5h, an) - -7> 81 =
min max V (x) A(V (z) b) X20
In the risk-averse case (a 0), the entropic risk measure can be recovered by setting u(l) _ [eaa - 1). For nota- tional convenience, we use OCE((T) from this point onward, as the function u(-) and the initial state $1 is fixed. Lemma 3.1. For a we have OCE(T) (s)).
Challenge in applying value iteration: In the standard CMDP setting, for a fixed X, the optimal Markov policy be obtained using a standard dynamic programming approach as the problem reduces to an unconstrained MDP with modified per-step reward of + 'g. Hence, a value- based method can be applied to compute the composite value function. This approach is then used to iteratively update both the policy π and the dual variable X.
Unlike the entropic risk measure, the OCE does not ad- mit a dynamic programming formulation. As a result, the optimal policy that maximizes OCE(T) is generally history- dependent. The solution is to consider an augmented MDP that extends the state space by introducing a scalar budget variable, which intuitively tracks the cumulative utility over time. This technique enables reformulation of the prob- lem into a state-based representation that is amenable to dynamic programming. This approach has been employed in the context of CVaR and spectral risk measures, and has more recently extended to the OCE framework (Bäuerle & Ott, 2011; Wang et al., 2024). We build on this formulation and extend our CMDP state-space.
However, in the risk-sensitive setting, expanding the La- grangian yields:
()) + PA V., (o,,) + a2)
X log (PheoVanti ())
which prevents the use of standard dynamic programming to solve for the optimal policy at fixed A. Unlike the risk-neutral case, the Lagrangian here does not reduce to a problem with a simple modified reward r + Äg.
3.2. Augmented CMDP
Consider an augmented CMDP (Smue, A,, Panng H, r. ge by appending a budget variable to the state and modifying the underlying utility function (Bäuerle & Ott, 2011; Wang et al., 2024). More specifically, augment the state space with budget variable at horizon h defined by e = == ghe (Sw where C1 T [0, H] is the initial budget provided by the algorithm, and e₁ denotes the remaining budget at time step h. Note that eΛ E [- H].
Lack of strong duality: For the standard CMDP, it has been shown that strong duality holds if a strict feasible policy (a.k.. Slater's condition) (Paternain et al., 2019) exists. Thus, one can solve in the dual-domain. For stan- dard CMDP problems, (Ghosh et al., 2022) demonstrate that primal-dual based approaches can achieve a O( K) regret and violation using the strong duality result. The key to obtain strong duality result in (Paternain et al., 2019) is that the value function is linear in the state-action occupancy measure. However, the risk-sensitiv tion is not linear with respect to the occupancy measure, and the risk-sensitive CMDPs may not satisfy strong duality. Consequently, traditional hiimal-dual-based algorithms are inadequate for obtaining the desired results.
Σi=il h-1
The budget transition is known and deterministic: Ch+1 = Cp - Ih (8h, az). We define the augmented utility function aug Ih by 9h (s, c, a) 0 for S H, and 9 c, a) u( cc)... where u(t) = _/ (e - 1). The choice of u(t) is dictated by the entropic risk measure. Note that the transi- tion probability for the augmented CMDP problem is given by piue (., c'|ss, c, a) IPa. (-1ss, a) for c' piil (,,d a) = O, otherwise, as gn is deterministic.
fate-action value func-
Ih (s, a), and
Absence of a Markoy Optimal Policy: In contrast to stan- dard CMDPs, the lack of strong duality in the risk-sensitive setting means that one cannot guarantee the existence of a Markov policy that solves the CMDP. The existence of such a policy is crucial for deriving finite-time bounds. In Appendix A, we present an example demonstrating that the optimal policy for CMDP with a entropic risk constraint may not be even Markovian.
The agent focuses on Markov policies defined over the aug- mented state space, denoted by
{ π {m (.m(111)) 1-) TA(- sh shi ck) E A(A).
Vh E [M]] and c C 1-1,111

---

Online Learning in Risk Sensitive constrained MDP
For Markov policy л in the augmented state space, abus- ing the notation, let 4% and yghh denote the augmented state-action value function and the augmented state-value function, respectively. The distinction between the risk- sensitive MDP and the augmented MDP is evident from the difference in the size of their state spaces. By definition,
Assumption 3.2. There exists a Markov policy in the aug- mented state space that solves the augmented CMDP.
Note that a complete history-dependent policy will be com- putationally more challenging, hence, we focus on Marko- vian policy class on the augmented state space.
1 (,
4. Algorithm
H+1
B
Σ
mng Ih
(sN, Cw, (w), = c, a. = a].
Considering Lagrangian relaxation of (3), our goal is to solve the following optimization problem:
h/=h
1+1
9.h. (8h, (n)
E
Σ
Ih. (sW, (wr, = 8, Ch = c]
min max max V (81, + (sI, B). (4) X
Note that the order of maximization in the above formula- tion is interchangeable. Since the augmented value function 9.1 (81, 7) satisfies a linear Bellman equation, the inner maximization, for a fixed T and X 2 0, can be efficiently solved using standard value iteration algorithms. In particu- lar, for a fixed and À 2 0, one can find the optimal policy that maximizes the composite state- action value function.
Note that for a Markov policy π in the augmented state space, the augmented CMDP admits a linear state-action value function with respect to the utility function Ih aug in contrast to the risk-sensitive value functions Q (8, a) and V.T. (s) defined for a Markov policy π in the original state space S. This is achieved by shifting the utility the terminal time step, i.e., Vg. 91 (SH, CH) u(-cH+1). The resulting additive structure is the key property that enables the analysis of Lagrangian relaxation.
The above approach addresses the primary challenge faced by the original risk-sensitive CMDP. However, the absence of strong duality remains a fundamental challenge. Specif- ically, the key issue is determining an appropriate tuning strategy for À to ensure a bounded trade-off between policy regret and constraint violation.
Furthermore, the function (g, is bounded above by Vg,mux = 1 icy æ in the augmented MDP, the functions Q7,1 and 9.4 satisfy standard dynamic programming equations:
|a] (exp((a [ao[ H)) - 1). Finally, for Markov pol-
A natural approach to updating the Lagrange multiplier À 2 0 is to use gradient descent. However, due to the lack of strong duality, the argument from (Ghosh et al., 2022) cannot be directly applied to establish its boundedness. In particular, the value function is still non-convex in terms of the augmented state-action occupancy measure. Hence, one not apply the tool used in (Paternain et al., 2019) prove strong duality. To address this issue, we consider truncated dual update, capped at threshold & to be specified later. This truncation is crucial for achieving both the regret and constraint violation bounds.
2 Ch, ax,) = EE| [Vg (Sh+1, 1 Sh, Ch. an).
(8 9x) Σ x x(a Sh: Cr) Q7, (k. a).
aEA
Note that OCE selects the optimal trade-off between the ini- tial budget and the value function of the augmented CMDP: OCF(TT== = max, (T+V 2.1 (#1, r)) Given this relationship, we present the augmented risk-sensit CMDP formulation, which is equivalent to the original problem (1). Since poli- cies are defined over the augmented state space, we denote the reward value function as V. (81,
We now describe our proposed Al- gorithm 1. The algorithm maintains an empirical estimate of the transition probabilities, which is updated as new data is observed (line 6). At each episode, this estimate is then used to compute an optimistic estimate of the reward state-action value function and the utility state-action value function, using a bonus term for every augmented state-action pair (lines 8-11). This bonus term enforces exploration.
Algorithm Description:
max
V V (81, x
subject to f = arg max + V (ri( (f + g., (51, +)) 2 B.
(Wang et al., 2024) studied an augmented formulation in the unconstrained setting for various risk measures. However, to the best of our knowledge, our work is the first to extend the augmented CMDP framework to the constrained setting. Un- like the unconstrained case, the constrained setting requires controlling both regret and constraint violation. We make the following assumption, which, in the rist-neutral CMDP setting, follows by Slater's 's condition (Paternain et al., 2019). Deriving an analogous condition for the augmented CMDP left for future work.
Next, the policy updated via a greedy algorithm with re- spect to the estimated composite state-action value function given by the Lagrangian relaxation (line 13). We then up- date the reward and utility value functions using standard dynamic programming equations (line 14), which effectively solves the inner maximization of the Lagrangian relaxation for any budget in the discretized budget space and a fixed
5

---

Online Learning in Risk Sensitive constrained MDP
A > O. Subsequently, we obtain the optimal initial budget the using the current estimate of V ($1, f) and V (81, f) to solve the inner maximization of (4) (line 16). Finally, we tune the dual variable via gradient-descent update on A:
VHK1/1 factor arises from the use of discretized aug- mented state space and the introduction of the truncation threshold ç, as strong duality may not hold.
g.1
5.2. Proof Outline
1
= pr (Ax + n(B (fx +
We first derive the regret and constraint violation associated with the problem formulation in the augmented CMDP. We then discuss the relationship between the regret and viola- tion in the augmented state space and those in the original CMDP. Note that the policy π depends on the discretized initial budget fy and the discretized utilities observed:
where Projjo.e] denotes the projection operator onto the interval [0, EJ. In line 19, we execute the updated policy o using the optimized Fx. as the initial budget. We track the cvolution of the budget while executing the policy.
Computational Challenge: One key challenge in optimiz- ing is that the objective function is not concave in 7. To address this, we discretize the budget variable with reso- lution co. where is chosen to ensure polynomial-time complexity while preserving regret and violation guarantees. We denote the resulting discretized set of feasible budget val- ues by C. Note that C _ [-H, H] and that |C| = [[f1/en)
Regret sug (K) E(VT (51, T.) VoT (51, fx)).
(5)
Violation 8 (K) = (B- (fx V (51, fk)l),
where x" is the optimal feasible policy for the original risk-sensitive CMDP, â is given by Algorithm I, and r. arg max, (T + g, ($1, (S), Note that the value of
5. Analysis
5.1. Main Result
c determines the policy n²
We now present our main theoretical contribution, which establishes high-probability sublinear bounds on both regret and constraint violation for Algorithm 1. Our analysis ex- tends existing frameworks in risk-sensitive and constrained reinforcement learning.
Step 1: Let V and VAA denote the optimistic estimates of Vgi and VØ respectively, as computed by Algorithm I on line 12. We begin with the following observation:
Theorem 5.1. With probability 8, Algorithm returns
(z, -V (x. +x))++((BBBB++ (fx V (z. fu)))
(2.
the policies {mr {
=k=1 such that
Regret((K)$ ( (Vomark K//1 /
(V, (2, - v (z, fx))
T
Violation(K) (K) Vg.naxx 3/1 V
Σ (V. (2, -V-i +x))+
where V max =
Jor (exp(la|H) 1), and Ō(-) hides loga- rithmic factors in S, A, H, and K.
Au((T, + 9,1 (I, [T)) -(fu Vola (x, fx)))
This is the first sublinear regret and violation result for the risk-sensitive constrained MDP setting. In the uncon- strained, risk-neutral setting, the best known regret bound is Ó ( (I' log(1/))) (Azar et al., 2017). The addi- tional / S factor in our bound arises from the use of an augmented state space; specifically, we must apply uniform, value-aware concentration bounds over the discretized aug- mented state space. The additional K1/4 factor arises from carefully balaneing the discretization error with the size of the discretized budget set C.
To
+ Σe (A-
An) - (Fr + Vih (2, tw)))
1s
+ A Σ ((Tk + VK (xr,((,()))) - (fx + Veri (c., fe))
Ta
where the inequality follows from the fact that (T. + (x) 2 B. Note that when = O, the above expression
For the unconstrained risk-sensitive MDP setting, the regret bound is O(V, OVVy,max / 52 log(1/5)), which is known to be tight (Fei et al., 2021). In our constrained setting, we achieve a violation bound of ÓVV Alggs
reduces to the regret. This same expression also suffices for bounding the violation, as we explain later.
Step 2: We bound Ts by analyzing the truncated dual update for constraint violation.
The additional
6

---

Online Learning in Risk Sensitive constrained MDP
Algorithm 1 Constraint Risk Sensitive Value Iteration Algorithm
Input: Number of episodes K E Z+, discretized budget space C, confidence level & E (0, 11, risk parameter a < O, utility lower bound B, learning rate 1,, initial policy n², truncation threshold &, and V m,,
|a (exp(la]H)) - 1).
1: A1 <-0 0
2: For all (s, C, a) E x C x A, initialize (), < u(-2) and (,, +
3: For all s, () [M] x x x A, set Q (s, t H. Qun(s, V Va,ax
4: For all h E [H] initialize dataset D/ < 0
5: for episode l 1 to K do
6: For each h [H]. compute counts and empirical transitions: (n(s, t Ex=1 1((s sh+1) - (s, a, 8'},
(s) < max E.' (s, a, s'),, and (s s,a) + (x.a,,))) 7: for step h = to 1 do
Nu(s,a)
8: for all (s,2, E C A do
SIC| log (HSAKICI/O) Bong, a) t 6V VV g.max
SIC| log (HSAKICVV g.max/
9:
(8,,,((844) + 9H
an(s,a)
Na(s,
10:
(,, min E (((sa) Vi (lnn(s Bon n (s. Vg,max
11:
Qna(s,Caa) + min
[h, a) + (Bn (ariaaa)(Viii [Vr ()) Bon,
12:
end for
13:
For all (s, 2) E S x C, set TH. (al 8, c) = -1 for some a E arg mrg. (
14:
For all (s, E S x C, update (s, 2) + (Qr, )) (1,,,))), + ((....)) (.
15:
end for
16:
t = arg maxsec 1 2) + Ax (c (s, E))]-
17:
A = Proiuue (Ax r/BB (fx + V2 +x)) 1 to H do
18:
for step h 1
19: Take action a according to the greedy policy ~ starting from initial augmented state (#1, fx).
20: Insert (sh, a 1) into Dr,
21: end for
22:
end for
Lemma 5.2. For any x E [), we have
respect to the composite state-action value function. As a result, this approach does not apply.
K
X²
n22
g.maz K
Σ (A AB - (fx + vk 9.1 (I, fxe)) -
Instead, we bound (P, a) as) J.h (+,) for {g,r) using the uniform concentration bound from (Jin et al., 2020), and discretization of the budget variable at resolution cp. denoted by C (see Lemma D.1). The size of C appears in the uniform concentration bound and is reflected in the bonus term in line 8 of Algorithm 1. Specifically, given the boundedness of both the reward and utility value functions, we apply a standard e-covering number argument to show that with high probability, at episode kt the compos- ite value function of the optimal policy is bounded above by the optimistic estimate, up to discretization gap of en
2m
2
Step 3: We use optimistic estimates to bound Tz.
Lemma 5.3. With probability at least 1 8.
Σ CVVA (x, V/h (2, ++))+
Aa((T. + V T.)) (+x + Vhh (x. fx))) < <o KG.
Proving the optimism is challenging due to the continuity of the initial budget t. In the augmented MDP for the uncon- strained CVaR problem, (Wang et al., 2023) leverages the fact that the greedy policy is optimal for the reward value function. In the unconstrained setting, one can bound the term (P)) (s, a) - Pr, (s, a)) ViT (,.c sn)l by showing that value function class on the greedy policy has small covering, as the Bellman operator is a contraction under the max operator. However, in the constrained setting consid- ered here, the optimal policy is not necessarily greedy with
The upper bound for Ti is established by leverag- ing the uniform concentration bound, applying Azuma's inequality, and invoking the Elliptical Potential Lemma.
Step 4:
Lemma 5.4. With probability at least 1- 6, 6,
Σ (v (2, fx) V fx))
SMIS/HAKI log log(())))oo) log (HSAK(C1/))

---

Online Learning in Risk Sensitive constrained MDP
Step 5: We bound Ta using similar argument the one used for bounding Tí.
Reward
Dual Varisble
3.0
Va,tes,
Dual Variabre (A)
Empiricaa Reward
Empincal Risk
28-
Lemma S.S.
With probability at least 1 - 6.
26
1.40
2.35
24
7-
1.0
E((t- + Vi (x, (fx + (2, fx)))
2.0
1.20
3000
U0920
33000
1200
10200
13400
3000
30000
13000
S 11V g.mxx. S [ lo (HSA g. 14V, (log(K) KegHelaln
Figure 1. Evolution of the empirical reward V/,1 (81; fx), the pirical risk measure for utility c + Vg.1 (81, fi), and the dual variable across iterations for a = -000001. Here, B 2.2. All values are averaged over the most recent 100 episodes.
policy, by Lemma 3.1, is given by
Note that the learned policy 7 is Markovian with respect to the discretized augmented state space, as it depends on the accumulated discretized utility rather than the exact cumula- tive utility. Consequently, x* is not Markovian with respect to the augmented state space which lies in the continuous space. This discrepancy is captured by the additional term in the upper bound of Lemma 5.5.
max 5
T + (xa(tt)
Ih (sh, an) -T -
H
2 Fr. + (tte
9h (Shh ax) - -Fx $1
= -x + Va 2 (81, fx).
Regret Bound: We derive the regret bound by combin- ing the bounds for Ti. Tz, and Tz. and by setting the pa- rameters as À 0, r K-1/4/V g.g ED K-1/2 and { K1/4__ More specifically, the regret associated with the augmented CMDP is bounded by K3/4
Therefore, have Regret SUE ((F)) (K) Violation(K) S Violation " (()) (K).
Regret(K) and
5H+ A log(1/))
6. Simulation Results
Violation Bound: To bound the violation, combine the bounds for T1, T2. and To for a fixed X, by setting À K2/4,
We simulate our proposed approach on a 5 x 5 Grid-World with two actions: - and 4. In all simulations, we use K 15, 000, & K-1/4, and r) cK-1// 1/1 /V/V where the coefficient is linearly scaled down from 100 to across episodes to improve the convergence rate (i.e., larger 1) in earlier episodes). Further details of the simulation setup, including the reward, utility, and transition probabilities, are provided in Appendix I.
7 K- K-1///V maz, 6o K-1/2, and & = K2/4, In
particular, for any fixed A E [0, we have
E (
(fx v (2, fx))
SV max H35 Alog
Figure illustrates the behavior of the algorithm for a -0.0001 as a function of k. Initially, the policy violates the risk constraint and also underperforms in terms of re- ward. As the number of iterations increases, the empirical risk associated with the cumulative utility rises and even- tually meets the threshold B = 2.2. The dual variable X increases rapidly in the early stages to penalize constraint violations. then grows more slowly once the policy becomes feasible. Additionally, we observe that the optimistic es- timates V (51, +k) and Vt ($1, $91,f fi) are initially inflated due to exploration bonuses. As more data is gathered, these estimates converge to their empirical counterparts, and the gap between the estimated and empirical values gradually narrows.
Note that (V, (z) V (z, kx)) is trivially bounded by HK. Setting A = E = K1/4, the viola- tion associated with the augmented CMDP is bounded by ÖVV / H3 A k311)
From Augmented CMDP to Original CMDP: As noted earlier, the policy n² together with the initial budget fx. can be interpreted as a history-dependent policy in the orig- inal CMDP. This policy depends on the current state and the accumulated discretized utility. To highlight the depen- dence of x² on fx, we denote it by x² (ft). Consequently, the reward associated with the policy x² (fx) is given by V (s1, ix) in both the original and the augmented CMDP.
Table presents the empirical reward values V (s1) and empirical risk values ( for the average policy in- duced by the final 20 episodes after K = 15,000 iterations,
However, the entropic risk measure corresponding to this
8

---

Online Learning in Risk Sensitive constrained MDP
Table 1. Empirical reward and risk from the average policy over the last 20 episodes after = 15,000 iterations for various (a, B) pairs.
(-10 (-10-2220 2.2.2
(-10 (-10-4,.22)
(-10- 2.266)
(-10 (-10-..2.6)
(-10- 2.2.9)
(-10
V (s0)(
1.95
2.80
1.90
2.24
1.92
1.88
(so)
2.76
2.20
2.80
2.57
2.78
2.80
across various choices of a and B. Decreasing B enlarges the feasible set, enabling the algorithm to attain higher re- wards while satisfying the constraint. Conversely, for fixed B, decreasing shrinks the feasible set, resulting in lower achievable rewards. Figure 3 (Appendix I) shows that as a decreases how the policy selects less risky actions compro- mising the reward. When |a| and B are large, the algorithm may fail to find a feasible policy, leading to constraint vi- olations. Moreover, as |a| increases, the value of Vg.max also grows, which may impact both regret and constraint satisfaction. Thus, larger values of |a| may require more episodes (K) for reliable performance evaluation.
and violation bounds, which will scale with the number of constraints. complete characterization of this extended framework is left for future work.
8. Conclusion and Future Work
In this work, we study the problem of maximizing cumula- tive reward subject to the constraint that the entropic risk measure of the utility function remains above a specified threshold. This formulation particularly relevant in safety- critical applications. We consider an online learning setting in which an agent interacts with the environment over K episodes, aiming to minimize both regret and constraint violation. The problem presents significant challenges due to the non-linearity of the entropic risk value, which ren- ders standard primal-dual methods difficult to analyze. To overcome this, we reformulate the problem by augmenting the state space with budget variable. By optimizing over the initial budget, we show that the value function in the augmented formulation exactly recovers the entropic risk measure, allowing us to recast the problem into structure amenable to value-based methods.
7. Extension
As noted, this is the first work to establish theoretical bounds for online learning in a CMDP with a risk-sensitive con- straint. Our analysis naturally extends several related settings, some of which we outline below.
Extension to other risk constraints: In this paper, we consider a constraint requiring the entropic risk measure of the utility value function to exceed a specified thresh- old. Our analysis can be extended to other risk-sensitive constraints, such as Conditional Value at Risk (CVaR) with hard threshold, by adopting similar augmented formu- lation in the unconstrained setting (Wang et al., 2024; Liang& & Luo, 2024). A complete characterization of regret and constraint violation in these cases is left for future work.
Since strong duality may not hold in this setting, we in- troduce truncated dual update. We prove that the result- ing algorithm achieves regret bound of OV mmay K3/4 +
v H A log(1/8) and a constraint violation bound of Ö Ö gmaxx / /H'S A (og(1/)) with probability least 5. To the best of our knowledge, this is the first result establishing theoretical bounds for the entropic risk- constrained MDP problem.
Extension to risk-sensitive objective: In this paper, we fo- cus on the objective of maximizing the expected cumulative reward. However, our analysis can be extended to settings where the goal is to maximize the entropic risk measure of the reward value function. This extension requires aug- menting the state space with two budget variables: т, for the reward and Ty for the utility. The optimization proceeds in two stages: first, for each Tr. we optimize over Ty to evaluate the entropic risk of the utility; then, we optimize over Ty to bound the entropic risk of the reward. A full characterization of this framework is left for future work.
An important direction for future work is determining whether tighter violation bounds, particularly with improved dependence on K, can be achieved. Recent approaches (Jiang & Ye, 2024; Dalal al., 2018) to improve the sam- ple complexity bound for nesk-neutral CMDP setting can be useful in reducing the dependency. Extending the anal- ysis to settings with infinite state spaces remains an open challenge. Another promising avenue is to consider envi- ronments where utilities and rewards are drawn from un- known distributions, introducing additional complexity in both learning and generalization. Another important future direction is to consider a stricter violation bound, such as no cancellation violation bound as considered in neutrall CMDP setting (Ghosh et al., 2024). Empirical evaluations for larger state-space, and for a more practical setup have been left for the future.
Extension to Multiple constraints: Our framework can be extended to accommodate multiple risk-sensitive con- straints. Specifically, we augment the state space with multi- ple budget variables (TI....,,T)) where I denotes the num- ber of constraints. For the resulting augmented state space, we first compute the value functions associated with each budget, and then jointly optimize over the initial budgets (Ti (T Tr). However, this extension influences the regret
9

---

Online Learning in Risk Sensitive constrained MDP
Impact Statement
Borkar, V. S. An actor-critic algorithm for constrained
markov decision processes. Systems & Control Letters, 54(3):207-213, 2005. ISSN 0167-6911.
This paper theoretical nature. The goal this work to advance the safe decision making using RL. We do not foresee any immediate or unique ethical concerns that require specific attention in this context.
Borkar, V. S. and Meyn, S. P. Risk-sensitive optimal control for markov decision processes with monotone cost. Mathematics of Operations Research, 27(1):192- 209, 2002.
References
Achiam, J., Held, D., Tamar, A., and Abbeel, P. Con- strained policy optimization. In Proceedings of the 34th International Conference on Machine Learning- Volume
Bäuerle, N. and Ott, J. Markov decision processes with wverage-value-at-ris criteria. Mathematical Methods of Operations Research, 74(3):361-379, 2011.
70, 17, pp. 22-31. JMLR, 2017.
Chow, Y., Ghavamzadeh, M., Janson, I.., and Pavone, M. Risk-constrained reinforcement learning with percentile risk criteria. Journal of Machine Learning Research, 18 (167):1-51, 2018.
Agarwal, A., Jiang. N., Kakade, S. M., and Sun, W. Reinforcement learning: Theory and algo- weterrbbooo....ubbb.b.... withub.thiiii. ioo rltheozybook AJKS. pdf, 2022.
rithms.
Dai Pra, P., Meneghini, L.,, and Runggaldier, W. J. Con- nections between stochastic control and dynamic games. Mathematics of Control, Signals and Systems, 9:303-
Altman, E. Constrained markov decision processes with total cost criteria: Lagrangian approach and dual linear program. Mathematical methods of operations research, 48:387-417, 1998.
326, 1996.
Dalal, G., Dvijotham, K., Vecerik, M., Hester, T., Paduraru, C., and Tassa, Y. Safe exploration in continuous action spaces, arXiv preprint arXiv: 18Xiv:8001.080 801.07577 2018.
Altman, F. Constrained Markov Decision Processes. Chap- man & Hall/CRC, 1999a.
Altman, E. Constrained Markov Decision Processes, CRC Press, 1999b.
Ding, D., Zhang, K., Basar, T., and Jovanovic, M. Natural policy gradient primal-dual method for constrained markov decision processes. In Larochelle, H., Ran- zato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 8378-8390. Curran Associates, Inc., 2020. URL htttps:://prooceengg...eeee cc http//pprr.illlepppppp////////// 5 $5715Seessedeeabbaacoffllle..ee. pdf.
Arrow, K. J. Aspects of the theory of risk bearing. Yrjo Hahnsson Foundation, 1965.
Artzner, P., Delbaen, F., Eber, J.-M., and Heath, D. Coherent measures of risk. Mathematical Finance, 93):2033-228 1999.
Azar, M. G., Osband, I., and Munos, R. Minimax re- gret bounds for reinforcement learning. In International conference on machine learning, pp. 263-272. PMLR, 2017.
Ding, D., Wei, X., Yang, Z., Wang, Z., and Jovanovic, M. Provably efficient safe exploration via primal-dual policy optimization. In International conference on artificial intelligence and statistics, pp. 3304-3312. PMLR, 2021.
Ben-Tal, A. and Teboulle, M. An old-new concept of con- vex risk measures: The optimized certainty equivalent. Mathematical Finance, 17(3):449-477 476, 2007.
Efroni, Y., Mannor, S. and Pirotta, M. Exploration- exploitation in constrained mdps. arXiv preprint arXiv:2003.021 029889. 2020.
Bertsekas, D. P. Nonlinear Programming. Athena Scientific, 3rd edition, 2016.
Borkar, V. A sensitivity formula for risk-sensitive cost and the actor-critic algorithm. Systems & Control Letters, 44 (5):339-346) 2001. ISSN 0167-6911.
Everett, H. Generalized lagrange multiplier method for solving problems of optimum allocation of resources. Oper. Res., 11(3):399 417, June 1963. ISSN 0030-364X.
Borkar, V. and Jain, R. Risk-constrained markov decision processes. IEEE Transactions on Automatic Control, 59 20:2994-2579, 2014.
Fei, Y., Yang. Z., Chen, Y., Wang. Z., and Xie, Q. Risk-sensitive reinforcement learning: near-optimal risk-sample tradcoff in regret. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN
Borkar, V. S. Q-learning for risk-sensitive control. Mathematics of Operations Research, 27(2):294-311 2002.
10

---

Online Learning in Risk Sensitive constrained MDP
Fei, Y., Yang, Z.,, Chen, Y., and Wang. Z. Exponential bellman equation and improved regret bounds for risk- sensitive reinforcement learning. Advances in neural information processing systems. 14:20436-20446, 2021.
Jabbari, S., Joseph, M., Kearns, M., Morgenstern, J., and Roth, A. Fairness in reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp- 1617-1626. PMLR, Au- gust 2017.
Fei, Y., Yang, Z., Chen, Y., and Wang. Z. Exponen- tial bellman equation and improved regret bounds for risk-sensitive reinforcement learning. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NIPS '21, Red Hook, NY, USA, 2024. Curran Associates Inc.
Jiang, J. and Ye, Y. Achieving o(1/c) sample complexity for constrained markov decision process. arXiv preprint arXiv:2402.16324 2024.
Jin, C., Yang, Z., Wang, Z. and Jordan, M. I. Prov- ably efficient reinforcement learning with linear func- tion approximation. In Abernethy, J. and Agar- wal, S. (eds.), Proceedings of Thirty Third Conference on Learning Theory. volume 125 of Proceedings of Machine Learning Research, pp. 2137-2143. PMLR, 09- 12 Jul 2020.
Garcia, J. and Fernández, F. A comprehensive survey on safe reinforcement learning- Journal of Machine Learning Research, 16(():1437-1480, 2015.
Geibel, P. and Wysotzki, F. Risk-sensitive reinforcement learning applied to control under constraints. J. Artif. Int. Res., 24(1):81-108, July 2005. ISSN 1076-9757.
Jung, W., Cho, M., Park, J., and Sung, Y. Quantile constrained reinforcement learning: reinforcement learning framework constraining outage probability. In Proceedings of the 36th International Conference on Neural Information Processing Systems. NIPS '22, Red Hook, NY, USA, 2024. Curran Associates Inc. ISBN
Ghosh, A., Zhou, X., and Shroff, N. Provably efficient model-free constrained rl with linear function approxima- tion. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS '22, Red Hook, NY, USA, 2022. Curran Associates Inc. ISBN 978171387106
Ghosh, A., Zhou, X., and Shroff, N. Towards achieving sub- linear regret and hard constraint violation in model-free rl. In International Conference on Artificial Intelligence and Statistics, pp. 1054-1062. PMLR, 2024.
Kolesar, P. A markovian model for hospital admission scheduling. Management Science, 16(6))B384-B3%, 1970.
Gottesman, O., Johansson, F., Komorowski, M., Faisal, A., Sontag, D., Doshi-Velez, F., and Celi, L. A. Guidelines for reinforcement learning in healthcare. Nature medicine, 25(1):16-18, 2019.
Levine, S., Finn, C., Darrell, T., and Abbeel, P. End-to-end training of deep visuomotor policies. Journal of Machine Learning Research, 17(1) 2016.
Liang. H. and Luo, Z.-Q. Bridging distributional and risk- sensitive reinforcement learning with provable regret bounds. Journal of Machine Learning Research, 25(221): 1-56, 2024.
Guo, D., Yang. D., Zhang, H., Song, J., Zhang, R., Xu, R., Zhu, Q., Ma, S., Wang, P., Bi, X., et al. Deepseck-rl: In- centivizing reasoning capability in 11ms via reinforcement learning. arXiv preprint arXiv:2501. 122448 2025.
Luce, R. D. and Raiffa, H. Games and decisions: Introduction and critical surveys. Wiley New York, 1957.
Haarnoja, T., Zhou, A., Abbeel, P., and Levine, S. Soft actor-critic: Off- Off-policy maximum entropy deep reinforce- ment learning with a stochastic actor. In Proceedings of the 35th International Conference Machine Learning (ICML), pp. 1861- 2018.
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Ve- ness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., Petersen, S., Beattie, C., Sadik, A., Antonoglou, I., King, H., Kumaran, D., Wier- stra, D., Legg, S., and Hassabis, D. Human-Level control through deep reinforcement learning. Nature, 518(7540):: 529-533, 2015.
Hardy, C. O. Risk and Risk- Risk-bearing, University of Chicago Press, 1923.
Bermandez-Hernnndee D. and Marcus, S. I. Risk sensitive control of markov processes in countable state space. Systems & Control Letters, 29(3):147-155, 1996. ISSN
Moharrami, M., Murthy, Y., Roy, A., and Srikant, R. A pol- icy gradient algorithm for the risk-sensitive exponential cost mdp. Mathematics of Operations Research, 2024.
0167-6911.
Howard, R. A. and Matheson, J. E. Risk-sensitive Markov decision processes. Management Science, 18(7):356- 369, 1972.
Murthy, Y., Moharrami, M., and Srikant, R. Modified pol- icy iteration for exponential cost risk sensitive mdps. Matni, N., Morari, M., and Pappas, G. J. (eds.),

---

Online Learning in Risk Sensitive constrained MDP
Proceedings of The 5th Annual Learning for Dynamics and Control Conference, volume 211 of Proceedings of Machine Learning Research, pp. 395-406. PMLR, 15-16 Jun 2023.
International Conference Development and Learning. pp. 163- 168, 2007.
von Neumann, J. and Morgenstern, O. Theory of Games and Economic Behavior (60th Anniversary Commemorative Edition). Princetonn University Press, 1944.
Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C. L., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., Schulman, J., Hilton, J., Kelton, F., Miller, L., Simens, M., Askell, A., Welinder, P., Christiano, P., Leike, J. and Lowe, R. Training language models to follow instructions with human feedback. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Wang. K., Kallus, N., and Sun, W. Near-minimax optimal risk-sensitive reinforcement learning with evar. In International Conference on Machine Learning, pp. 35864-35907. PMLR, 2023.
Wang, K., Liang, D., Kallus, N., and Sun, W. Risk-sensitive rl with optimized certainty equivalents via reduction to standard rl. arXiv preprint DXXiv:2403.06333 2024.
Paternain, S., Chamon, L.,, Calvo-Fullana, M., and Ribeiro, A. Constrained reinforcement learning has zero dual- ity gap. Advances in Neural Information Processing Systems, 32, 2019.
Whittle, P. Risk sensitivity, strangely pervasive concept. Macroeconomic Dynamics, 6(1):5-18, 2002. doi: 10.
0177$13365000502277225
Popova, M., Isayev, O., and Tropsha, A. Deep reinforcement learning for de novo drug design. Science Advances, 4 (7):eaap7885, 2018
Ying, D., Ding, Y., and Lavaci, J. A dual approach to constrained markov decision processes with entropy reg- ularization. In International Conference on Artificial Intelligence and Statistics, pp. 1887-1909. PMLR, 2022.
Rockafellar, R. T. and Uryasev, S. Optimization of condi- tional value-at-risk. Journal of risk, 2:21 2:21-42, 2000.
Zhang, Q., Leng, S., Ma, X., Liu, Q., Wang. X., Liang. B., Liu, Y., and Yang, J. Cvar-constrained policy optimiza- tion for safe reinforcement learning. IEEE Transactions on Neural Networks and Learning Systems, pp. 1-12, 2024.
Ross, K. W. Randomized and past-dependent policies for markov decision processes with multiple constraints. Operations Research, 37(3):474-477, 1989.
Sallab, A. E., Abdou, M., Perot, E., and Yogamani, S. Deep reinforcement learning framework for autonomous driv- ing. Electronic Imaging, 2017(19):70-76, 2017.
Zhao, X., Song, W., Li, Q. Shi, H., Kang, 7., and Zhang, C. A deep reinforcement learning approach for resource-constrainee project scheduling. In 2022 IEEE Symposium Series on Computational Intelligence (SSCI), pp.
Shapiro, J. F. Mathematical programming: structures and algorithms. Wiley, 1979.
2022.
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., van den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):884 489, 2016.
Zhao, Y., Zhan, W., Hu, X., fung Leung, H., Farnia, F,, Sun, W., and Lee, J. D. Provably efficient CVar RL in low- rank MDPs. In The Twelfth International Conference on Learning Representations, 2024.
Silver, D., Schritwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., et al. Mastering the game of go without human knowledge. Nature, 550(76766:354-359, 2017.
Zheng, I. and Ratliff, L. Constrained upper confidence reinforcement learning. In Bayen, A. M., Jadbabaie, A., Pappas, G., Parrilo, P. A., Recht, B., Tomlin, C., and Zeilinger, M. (eds.), Proceedings of the 2nd Conference on Learning for Dynamics and Control, volume 120 of Proceedings of Machine Learning Research, pp. 620- 629. PMLR, 10-11 Jun 2020.
Tamar, A., Glassner, Y., and Mannor, S. Optimizing the evar via sampling. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 15 pp. 2993-2999, AAAI Press, 2015. ISBN 026251 1290.
Tessler, C., Mankowitz, D. J., and Mannor, S. Reward con- strained policy optimization. In International Conference on Learning Representations, 2019.
Uchibe, E. and Doya, K. Constrained reinforcement learning from intrinsic and extrinsic rewards. In 2007 IEEE 6th
12

---

Online Learning in Risk Sensitive constrained MDP
A. Limitations of Markov Policies under Entropic Risk Constraint
Here, we present a simple example that illustrates the limitations of Markov policies in a CMDP with an entropic risk measure. In particular, the optimal policy in this example does not lie within the class of Markov policies. This demonstrates that Markov policies can be suboptimal, underscoring the need to extend the policy search to history-depende policies in framework.
Consider CMDP (S, H)r,9), where the state space is S = {81, $2, 8/22 83), the action space is A = {a, b). and the horizon is H = 3. The transition probabilities are depicted in Figure 2 and are independent of the actions taken at the states. The reward and utility functions are zero everywhere except at the following state-action pairs:
r(s,, =1 g( 1, r(53, a) 1, g(53, b)
Notice that action maximizes the expected reward, while action b maximizes the entropic risk measure. Let the lower bound on acceptable utility be = in (1). Consider a history- deeeeded policy that selects action b and only if the state at is $1. It is easy to verify that this policy is feasible, and the resulting expected reward
$2
Figure 2. Transition diagram for the CMDP.
Next, we show that any Markow policy is suboptimal. Let ग (mo, Wi, T2) denote a Markov policy. Observe that the only relevant components are (a 82) and (2(b(s)) Define Tz 82). Then we have:
1 V. (81) + P. 2 1
1- aa
1- P
3 p.
V (51) log a
20
a
2
where < 0 is the risk factor, and the last inequality follows by Jensen's 's inequality. Observe that for any p < 2. the resulting policy is suboptimal since (s1) < 1. On the other hand, for any 2 1. we have VT, (s1) < 1, and thus the resulting policy is infeasible.
B. Proof of Lemma 3.1
From the definition, OCE(=) max, (T+E)
|E kh Ih. (5h, an) -))) where uut) [e 1). Note that for << 0, the function v(()) is strictly concave, hence, the unique maximizer can be found using the first order condition:
1
log
E
exp (a
Σ gn (Sh, (n)n)ann)
1=1
The result follows by substituting т. in the definition of OCF(T).
13

---

Online Learning in Risk Sensitive constrained MDP
C. Proof of Lemma 5.2
Note that for [0, [), we have
Ma++ 212 = ( + (B - (fr + (81, fx)))) - Proj(A)
$ > + r/(B (fx + (81, ft)))) 212
- A - Aul² -1y(B- (fx + fx))( A1e) + +n V2
g.maz
where the first inequality follows from the non-expansivennsss of the projection operator, and the second from the fact that
BB (fx + (s,, Px))) S Vg g.max. Summing over &s then yields
0 < - 212 Σ 2m - (fx + (s,1(s,, Ax) Ki g.mar
Since \1 0, it follows that
X2 CA-AA))(B- (fx + (z, fw))) -
+ g.man K
n22
21
D. Proof of Lemma 5.3
Recall that x = { denotes the optimal feasible policy that solves the optimization problem (1). By assumption, there exists corresponding Markovian policy in the augmented state space that solves the optimization problem (3). With slight abuse of notation, we also denote this Markovian policy by x=" {nx,, ) h=1- where each n x [-H, H - A. As noted earlier, the budget variable с₁ in the augmented MDP time h lies in the interval |- H, H)
To improve computational efficiency and address the challenge of optimizing the initial budget i.. we discretize both the initial budget and the utility values received at each state. Consequently, the learned policy x² = { !! depends on the accumulated discretized utility rather than the exact cumulative utility. As a result, T² is not Markovian with respect to the augmented state space, but instead is Markovian with respect to the discretized augmented state space, where all utility values are replaced by their discretized counterparts.
Specifically, the budget variable in the discretized augmented state space is restricted to finite set which is an resouuuuuio discretization of the interval [- H, H). Thus, the cardinality of C is given by
2H
|C|
60
Finer discretization improves the approximation accuracy the cost increased computational complexity. The discretiza- tion operator Φ 1-H,, [1] C projects real-valued budget onto the nearest larger discretized value:
Φ(c) = arg min /č (é-cl cl.
aEC, 22c
For notational consistency, all hatted symbols denote discretized values. In particular, we use (n, a) as shorthand for (g, a)). Lemma D.1. For all (s, x A. H, K, and E {r,g}
()) Ph()),))) T () Bon
with probability at least 1 5, where Bon (s, a) m.ax /siC log (HSAK) (mxc////.///////N Vr,max H,
and V Vg.max= exp([a) H)-
14

---

Online Learning in Risk Sensitive constrained MDP
Lemma D.2. For all (s, S AcE C H, and k K, and (r,g) the following holds with probability at least ò.
(P.(- (Vilet (,c ((((s))) - Vihtti (:,ô- (n(s)a))).
Proof.
- -,) (Pr(. s, a,)))² (P 2htz (:.0- (x(3,))
A (,,(11,,))) V* sh+1 1 (n(s,a))
(Pr(. (e(-(s,aa) V3 (icc- (s 1it (,. (,8- (10- (u(ssa)))
- -Bonf, a) - (P 8, - Pa( Pr(.18,a)) T Vinti (, - On (s)
$ (P%(. s, a)) Vi (:,c- ())(s))) - V (,, - gu(s.a)))
- Bon (s, a) + Bonj
c C with è S c, h S H, and &s S K, the following holds with where the last inequality follows by Lemma D.I.
Lemma D.3. For all (s,a) E probability at least 1 6:
(n,,s, + (g, - (s, - Qg, 50
Proof. We prove the claim by induction. The base case holds trivially for h = H + 1, since (s,,,((,, = (,) 0 and Q (5, u(-c) < u(-ē) +1 a), where the inequality follows from the monotonicity of u(.). For the induction step, assuming the statement holds for horizon h + 1, will verify it for horizon h:
(s, (s,,,,) + - Ax
$ (Phl s,a)) (Viniilic (s) -ghnn())--((sa)))
Vk V, Jn (s.
+ Ax (Pal (Pa(-18,,))) (Vonez (s, gn(s,a)) - Vk giht1 ( -a((
0
where the first inequality follows from Lemma D.2, and the last inequality follows from the induction hypothesis, the assumption that S e, and the inequality 9r a) 2 gn(s, Notice that by the definition of x
V8" (s,c) + Ax Va (s, - (Vi (s, + A gh++ (s,
x (als, (0F (s,,,,
(s, Ae (x0g,,t((s.,,a))
<
A
As an immediate corollary of Lemma D.3, the following inequality holds with probability at least 1 5:
(sI, + d (T. V (81, (81, - V.l (81. (x) - -o (fr + g. (s1, (s2, 7x)) < (s1, + Au (T. + (01,7)))) VA (81, ((T.) to) >u (b((T)) -o Vk (81, -co))
S Apco
where we use the fact that the initial budget at episode ls is given by Åx = arg maxzee [V/S é) + d (e+ Vk (s,,))))) and the inequality ((T.) 6 T. S ((T.). Finally, observe that 2ς g.
15

---

Online Learning in Risk Sensitive constrained MDP
E. Proof of Lemma 5.4 and Lemma 5.5
As noted earlier, the policy x = [ is Markovian with respect to the discretized augmented state space, but history- dependent with respect to the augmented state space. However, note that V v 9.H+1 depends on the cumulative discretized utility. More specifically,
".H++1 depends on the cumulative utility, while
h
( 8h, cb. (aws, aw Oh 14-1 = Th
.1
8/:
(sw, (a))
h==
vk v 9 aw, ow 11)
- p(()) +
Ag (sw, aw1)
hmm1
vxt (1ott aw Oh H =1== = 1
Σ M=1
The (sw, an) (Bw))aa))))
-C
In particular, the value of Vi depends on both the cumulative discretized utility (since the policy x² depends on it) and the cumulative utility (since Vi depends on it). For notational simplicity, we retain only the cumulative discretized utility in the notation and explicitly acknowledge the dependence on the cumulative utility when referring to V 9.H+1 In what follows, we adopt the convention of reserving the "** symbol exclusively for discretized values.
Lemma F.1. The following inequality hold with probability at least 1 - 8:
1h (s, Fx) V. fx) 2
F [Bon (sh, and 81 = =s, = fk, [x]
"
Vk (s, - yat g.1 (x) < 2
E [Bon & 9. (on, an) |8 c: Fxx Hx] + en Hol
Proof. For all s S,CEC, s 11 k s K, and j E {r.g} the following holds with probability at least 1 - 8:
V ()) - -V.) (8)
E
x (a)s, (Qin - ((
aEA
Σ (als,
(Bonš, (-Is a))² T 1 a)( (3,
aEA
Bonfin (Ph - a))) T V - (s(ssa))
E (
nht (als, (Pa(-ls, (V a)) Vith (:, 8--- (n(s)a)))
2 a s.6) Bon (8, a)]++]] + Ex Vin+i(onn (x+1) -
8h 8, cn = c)
where we used the fact that x is Markovian with respect to the discretized augmented state space. Hence, we have
V/i fk)) V (s, 7k) <
B [Bon (sh, an) |s =,,1- fx, Hll.
h=1
H B [Bon i an) 81 = =8,01- = -xk, H6ml
vi (8, Ak) Virl (s, Ax) <
h=1
H
Gne (sw (Sw, awx) ) -ul tx +
H
|ss = s, = - H4
+ Ex k
F
+
> gh (sW, an)
$1
h'=1
h==1
where H4 is the trajectory from episodes 1,2, .... . The result follows from the fact that utt), for E [-H, H]. is Lipschitz function with Lipschitz constant H
16

---

Online Learning in Risk Sensitive constrained MDP
Combining Lemma E.1 with Elliptical Potential Lemma, have
(s, (x. Fx) V,A" (s, Fk)
E E
[Bon i (sh: an) |81 8, Fm] 2/1 / VKK log(1/6)
K
H
SCI log (7SAK(CI/0) (s ax
2
E R
9H
81 8, = fK + 2H V HK log (1/6)
1=
h=1
20HSV HAKIC log(K) log (HSAK C1/0)
Using similar argument,
Vk (8, Fm)) (s, fk) $2 Σ Ey [Bon 9. (5%, (8%, an) 88 =, fxl] KegHelolh + +V y.yamaxx v HK log(1/5)
< 14V g.
g.max SV HAKIC log (HSAK]CIV, maxx + KegHelolH
F. Bounding the Regret and Violation
Bounding the Regret: We bound the regret by combining Lemmas 5.2, 5.3, and 5.4, and by setting À = 0, K KK1///Vg Vymaz. ED- = K-1/2 and & = 1/44
Regrot R0B (MK)) S V2 max K + 1g
log (HSAK(C//8)
= = (( clalH HK (og55
|a|H
Bounding the Violation: We bound the violation by combining Lemmas 5.2, 5.3, 5.4, and 5.5 and by setting = 0, 7 = K KK1/1/1 /V 6g K-122, and & K1/4, Note that for fixed À E [0, E). we have
Σ V (o, (z) Vo5l (z, fx)) + (fu+
+V Vil (z, fw))
I 222 2
K +
+ toKKE 200S HA|C (og())) log (HSAK(CI/0)
g.
21
146V
S
HAKIC log K) log (HSAK]CV /6) + KegHel
Vamaa 3/4 + 3/4 + 60 3/4 S2 S2HHAlog(HH log (HSAK/8)
Vgnaa 33/4
2
42V g.max K. H A (K) log (HSAK/5) (og
② (g.maxk 1 (1/6)).
Trivially bounding E (ViR (x, Fx)) (x, < HK, we have
Σ K
B- (Fx (B- (w) < HK + (V 0 /S (1/6)
Setting À = & = 1/4 and dividing both sides by 1/4 we have
VoT " (z. (2, kw)) sō (clalt -1
Σ (B B (fx (B-
1 Ja|H
/ log (1/6)
k
17

---

Online Learning in Risk Sensitive constrained MDP
G. Proof of Lemma D.1
Consider the value function classes Vj - (V(--) 8 [0, Vj.max]] for j {r.g), where Vy,ax = H and
Vgmax exp([o H) 1 The E-covering numbers of V under the &o norm is bounded by
|
stcl
N(V,, lloo) 5 1
jaax
where S is the state space, S =S], and is the discretized budget space. We provide uniform concentration bound. Fix j E gr.gh. (s.a) E S x A. E C. s H, and k s K. Pick function V E Vy. Applying Azuma- Huema-Hoffddings inequality, we obtain
())
v(,,)) >() s exxp P -((((((ss))Pa(((a.))) - Pr(Hss,))
2V2 J.max
where (s, a) denotes the number of visits to (s, a) at time up episode Hence, with probability at least
(P) o))))s,))) T v(,,) c) < 2V j.n.max 1og(1/6) (s)
Let V C. V, denote an e-covering set. Applying union bound together with standard covering argument, with probability at least 1 - 6/2, for all (8,a) E S A, A,C.C, H, k S K, and V E V/. we have
log (2HSAKCNN(), |l 1lxo)/8)
(P)))))) PM((),,)) V(,
< 2s 2V mmax
(5 a)
SICI log (2HSAKICIC) [C + Vx.max/E) /E)/o)
25 2V jax
(// a)
S|C| log (HSAKCCV, mmxx//8) N (s. a)
S 6V, m
where the last inequality uses 1/K and the fact that N, S K. The final result follows by applying union bound over Vo and V, See (Agarwal et al., 2022)[Lemma 7.2] for similar argument.
H. Auxiliary Lemmas
We adopt the following results from (Wang et al., 2023).
Lemma H.1 (Azuma). Let [Xilvejn) a sequence of random variables supported on [0, 1), adapted to the filtration (Fi)eey) For any 8 (0, 1), we have with probability at least 1
5,
N
N EXXAF = Σ X,
log((//)
(6)
1=1
Lemma H.2 (Elliptical Potential). For any sequence of states and actions {SN,, an. b ME(K)) we have
K
Nu(sh,b,ar.d) a < &SAlog(K),
K
S HSAK log(K).
NN((shk
18

---

Online Learning in Risk Sensitive constrained MDP
Column
Column
3
1.0
1.0
Normalized Action Frequency
0.8
Nomalizel Action Frequency
1-
0.6
2-
pow
0.4
0.2
0.2
0.0
Directional Action Heatmap
Directional Action Heatmap
Figure Frequency of actions for the average policy over the last episodes after 15,000 iterations. Left: -0.01, Right: 0.00001, with B = 2.2.
I. Simulation Environment
The reward function is given in Table utility values in Table 3, and transition probabilities Table 4. Both rewards and utilities depend the state. The transition probability p specifies the chance of successfully moving in the intended direction (e.g., choosing the action attempts to move the agent to the right neighboring cell with probability p). If the intended move is invalid (c.g., outside the grid), an alternative action is executed. Consequently, in the fourth row and column, the choice of action becomes inconsequential. The total horizon is H 9, and a state at position (i,j) is only reachable at time step h = i ++ 1.
The environment presents several interesting features. For instance, the state at position (1, 2) offers high reward. However, is surrounded by states with transition probabilities close 0.5 and low utility, making risky. While may appear attractive to visit 21, the agent might instead end up in of the neighboring low-utility states. Consequently. as becomes more negative, the agent may learn to avoid this region in order to mitigate risk which may lead to smaller cumulative reward. The environment is deterministic across the terminal rows and columns. The code is available at: https: // /github. http::////thuis
RRikk Sens innsitin iive CMDP.
Table 2, Reward matrix r(t,j) for state (i,
Row
Col
0
1
2
3
4
0
0.0
0.1
0.2
0.2
0.1
1
0.5
0.1
1.5
0.5
0.3
2
0.1
0.1
0.4
0.3
0.2
3
0.1
0.1
0.3
0.1
0.6
4
0.1
0.2
0.3
0.1
0.0
For a faster convergence, we use the bonus terms Bon (8,a) = 0.5H log(K)/N a), and Bon (s, 5,
0.005V mar log( /)/N/ (s, a) instead of the values for which obtain the regret and the violation bound across all the values of a. We use the discretized budget space with precision K-1/2, and å 0.05. The initial policy is uniform across the two actions for every augmented state.
Figure 3 illustrates the frequency of selecting each action (- or 4) at every state for a = -0.01 and a = -0.0001, respectively, with B = 2.2. The displayed policies are the average policies over the last 20 episodes after running the algorithm for 15,000 iterations.
19

---

Online Learning in Risk Sensitive constrained MDP
Table 3. Utility matrix u(t j) for state (f.j).
Row
Col
0
1
2
3
0
0.1
0.1
0.2
0.1
0.1
1
0.4
0.2
0.1
0.0
0.0
2
0.3
0.4
1.0
0.0
0.1
3
0.2
0.5
0.4
0.2
0.1
4
0.1
0.1
0.4
0.2
0.0
Table 4. Probability matrix p(t,)) 5) representing the likelihood that the action taken in state (i, will occur.
Row
Col
0
0.9
0.9
0.7
0.5
1.0
1
0.9
0.9
0.5
0.5
1.0
2
0.7
0.9
0.9
0.6
1.0
3
0.9
0.8
0.8
0.5
1.0
4
1.0
1.0
1.0
1.0
1.0
Observe that under the more risk-averse setting -0.01, the algorithm tends to avoid the risky state (1, 2) to satisfy the constraint. In contrast, in the more nest-nl scenario a = -0.0001, the algorithm chooses to visit state (1, more frequently by taking appropriate actions, thereby increasing the reward while still adhering to the constraint.
20


Reviews:
[{"review_id": "o2rpufj9jo", "reviewer": "Reviewer_DeSK", "summary": "This work focuses on Risk-Sensitive Constrained MDPs and proposes a novel algorithm that ensures the entropic risk for an additional utility function remains above a given threshold. Under this setting, the author introduces a new algorithm based on the primal-dual method for an augmented MDP. Additionally, the author provides the first sub-linear regret guarantee for the reward in this setting, along with a non-optimal violation magnitude for the constraints.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for providing thoughtful comments. Please see our responses below.\n>*Regarding the computational efficiency...*\n* *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. \n* 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.\n\n>*..the novelty of the approach is limited.*\n\nIn the following, we state the novelty of our proposed approach. \n* 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.  \n* 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. \n* 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. \n* 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. \n\n>*Other violation metric..*\n* 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. \n* 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. \n \n[A1]. Ghosh et al. \"Towards achieving sub-linear regret and hard constraint violation in model-free rl.\" AISTATS,2024.", "claims_and_evidence": "The author provides a clear claim of the result in the theorems and includes a proof sketch to outline the key steps of the theoretical analysis.", "methods_and_evaluation_criteria": "The main contribution of this work focuses on the theoretical analysis of regret and does not have experiment.", "theoretical_claims": "The novel algorithm combines the augmented method with the primal-dual method, where the augmented method is widely used in risk-sensitive reinforcement learning, and the primal-dual approach is commonly applied in constrained MDPs. Therefore, the algorithm is well-motivated. The author provides a clear proof sketch, and there are no concerns about correctness based on the proof sketch.", "experimental_designs_or_analyses": "The main contribution of this work focuses on the theoretical analysis of regret and does not have experiment.", "relation_to_broader_scientific_literature": "This work mainly focuses on risk-sensitive constrained reinforcement learning; however, the proposed algorithm is highly computationally inefficient, making it primarily relevant for the theoretical analysis of reinforcement learning rather than practical applications.", "essential_references_not_discussed": "This paper provides a comprehensive discussion of related work in risk-sensitive reinforcement learning and constrained reinforcement learning.", "other_strengths_and_weaknesses": "1. The proposed algorithm is highly computationally inefficient due to the augmented feature of the budget variable. Specifically, in tabular MDPs, the number of state-action pairs is finite, allowing for efficient value function updates. However, the augmented budget variable can take any real value, making the value function update (Lines 13-14) computationally expensive, as it must be performed over a continuous range of budget values. Additionally, the optimization of $\\tau$ in Line 16 may also be inefficient, especially if the value function lacks useful properties such as convexity. A discussion on potential computational improvements or approximations would be beneficial.\n\n2.The algorithm appears to be a direct combination of the existing primal-dual method used in constrained RL and the augmented method used in risk-sensitive RL. As a result, the novelty of the approach is limited.\n\n3. It is not clear why violation is an appropriate measure for constraint RL. Specifically, in a strictly constrained setting, the utility should be above the threshold in each episode, rather than being averaged over multiple rounds. Even in a soft-constrained setting (such as in classification problems), a more natural approach would be to use a truncated violation measure like $\\max(0, B - V_g)$ in each round, preventing a scenario where a round with high utility compensates for rounds with low utility. Furthermore, even if such compensation is allowed, given that the author considers a risk-sensitive utility function, it would be more reasonable to introduce an entropy-based loss structure for the compensation process rather than using a linear summation, which is more suitable for risk-neutral cases.", "other_comments_or_suggestions": "1. It is not clear why violation is an appropriate measure for constraint RL. Specifically, in a strictly constrained setting, the utility should be above the threshold in each episode, rather than being averaged over multiple rounds. Even in a soft-constrained setting (such as in classification problems), a more natural approach would be to use a truncated violation measure like $\\max(0, B - V_g)$ in each round, preventing a scenario where a round with high utility compensates for rounds with low utility. Furthermore, even if such compensation is allowed, given that the author considers a risk-sensitive utility function, it would be more reasonable to introduce an entropy-based loss structure for the compensation process rather than using a linear summation, which is more suitable for risk-neutral cases.\n\n2. In this work, the author considers a deterministic reward. In the traditional RL framework, it is natural to transform the reward into its expectation, and unbiased noise does not significantly affect the learning process, as most challenges arise from learning the transition dynamics. However, it is unclear whether the assumption of a deterministic reward is reasonable in a risk-sensitive environment. Will this assumption have further implications for the entropy-type value function?", "questions_for_authors": "1.In the learning matrix, why consider a linear summation for the compensation process rather than an entropy-based loss structure, which is more aligned with risk-sensitive settings?\n\n2. 1. deterministic reward", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EYSs7OLWRx", "reviewer": "Reviewer_c96z", "summary": "The paper studies online learning in episodic finite-horizon constrained Markov Decision Processes  with entropic risk-sensitive constraints. Traditional primal-dual methods fail to directly address risk-sensitive CMDPs due to the non-linear nature of entropic risk constraints and the lack of strong duality. The authors propose augmenting the CMDP by incorporating a budget variable into the state-space, allowing the use of value iteration. They then introduce a primal-dual algorithm with regularized dual updates and prove the first known sublinear regret and violation bounds  for risk-sensitive CMDPs.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing thoughtful comments. Please see our responses below.\n>*Lack of numerical results*\n* 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.\n* 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.\n\n>*Dual regularization..*\n* 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. \n\n>*Choice of ERM rather than CVaR..*\n\nThe entropic risk measure prioritizes policies with desirable robustness and performance trade-offs. Specifically:\n* **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. \n\n* **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.\n\n* **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.\n\n>*Implications of the regularization term*\n* 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.\n\n>*Regarding lower bound*\n* 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.\n* 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.\n\n>*Extending other OCE representations*\n* 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.", "claims_and_evidence": "- The major claims of achieving sublinear regret and violation bounds for the risk-sensitive CMDP setup are well-supported by theoretical arguments and detailed proofs. \n- The paper claims that the augmented CMDP allows for a tractable solution to the risk-sensitive constraint, but the paper does not provide a computational complexity analysis.", "methods_and_evaluation_criteria": "The introduction of an augmented CMDP framework to overcome the challenge of nonlinear entropic risk measures is inspired by (B¨auerle & Ott, 2011; Wang et al., 2024), which is sensible. While the evaluation criteria, specifically regret and constraint violation, seems quite standard for the considered setting, I do have some questions regarding the learning metric. Does the metric is defined over the admissible/feasible policy set? If not, then some policy may achieve negative violation. Should we take the positive part of violation then?\n Another concern regarding evaluation is that the paper lacks empirical evaluation, including simple numerical experiements.", "theoretical_claims": "I checked the main theoretical claims, specifically the correctness of Lemmas 3.1 and 4.1, which  the value-function equivalences and existence of Markovian optimal policies. No significant issues were identified; the derivations appear mathematically sound and clearly presented.", "experimental_designs_or_analyses": "The paper is purely theoretical, and no empirical experiments are presented. While  its absence does not detract from the theoretical contributions, numerical validation could strengthen the paper.", "relation_to_broader_scientific_literature": "The paper  situates its contribution within the existing literature on CMDPs and risk-sensitive RL. It  dentifies gaps related to nonlinear risk constraints and appropriately builds upon recent advances (Wang et al., 2023; Ding & Lavaei, 2023) and extends primal-dual methods but adapts them to risk-sensitive settings.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths:\n- First rigorous theoretical analysis of CMDPs with entropic risk-sensitive constraints.\n- Clear theoretical exposition and solid analytical framework.\n \n\nWeaknesses:\n- Lack of numerical examples or empirical validation\n- The dual regularization strategy is somewhat heuristic; further justification or exploration of alternatives would strengthen the approach.", "other_comments_or_suggestions": "- A more detailed discussion on why entropic risk measures, rather than CVaR or other risk measures, are particularly valuable would help clarify the practical implications. In contrast, CVaR or VaR-constrained  formulation is well-known and well motivated\n\n- There are also some typos throughout the paper. Need proofreading.", "questions_for_authors": "- Can the authors discuss the implications of regularization parameter  in more detail, including its choice and sensitivity?\n\n- Regarding the regret bound in section 5.1, the lower bound result for ERM-MDP is improved and proven tight in Liang and Luo 2024, in contrast to Fei et al. 2021, which is not discussed. While it might be challenging, is it possible to derive or adapt lower bounds to this setting? How tight are your proposed upper bounds likely to be compared to these potential lower bounds?\n\n- The author should also carefully discuss the worsening of bounds compared with risk-neutral CMDP in terms of SAKH, rather than K only.\n\n- Following the idea of (Wang et al., 2023,2024), it seems to be possible to directly extend the whole framework from ERM-constrained setting to OCE-constrained setting.\n\nFei, Y., Yang, Z., Chen, Y., and Wang, Z. Exponential bellman equation and improved regret bounds for risksensitive reinforcement learning. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NIPS ’21\n\nWang, K., Kallus, N., and Sun, W. Near-minimax-optimal risk-sensitive reinforcement learning with cvar. In International Conference on Machine Learning, pp. 3586435907. PMLR, 2023. \n\nWang, K., Liang, D., Kallus, N., and Sun, W. Risk-sensitive rl with optimized certainty equivalents via reduction to standard rl. arXiv preprint arXiv:2403.06323, 2024.\n\nLiang, H., & Luo, Z. Q. (2024). Bridging distributional and risk-sensitive reinforcement learning with provable regret bounds. Journal of Machine Learning Research, 25(221), 1-56.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sjlq3lgEhh", "reviewer": "Reviewer_DwFN", "summary": "The paper develops the first sublinear regret bound for the risk sensitive CMDP problems. In contrast to the classical CMDP, an additional risk measure is put on the left hand side of the constraint value, and it is required that the final value is greater than a threshold. The paper develops the clever idea of introducing an augmented variable to denote the budget constraint and the optimizing over the minimax formulation of the CMDP, with an additional augmented state. Finally, the sublinear regret has been developed for the objective value, as well as the constraint.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing thoughtful comments. Please see our responses to your questions below.\n\n>*For multiple constraints*\n* 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.\n\n>*Lack of numerical experiments*\n* 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.\n* 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.\n* 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. \n* 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. \n\n>*Computational Complexity*\n\n* 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. \n\n>*Lower Bound*\n* 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. \n\n>*Regarding the references*\n\n* 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.\n* 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.", "claims_and_evidence": "The claims look good to me.", "methods_and_evaluation_criteria": "The method makes sense but the numerical experiment is lacking.", "theoretical_claims": "The claims and proofs look correct to me.", "experimental_designs_or_analyses": "There is no numerical experiment of the paper.", "relation_to_broader_scientific_literature": "The paper develops the first sublinear regret for the risk-sensitive CMDP.", "essential_references_not_discussed": "The algorithm developed in the paper is based on the Lagrangian formulation, where the primal-dual algorithmic framework is widely developed to solve it. However, primal-based algorithms have also been developed to solve the CMDP problems. For example, the primal-based algorithm has been developed in [1], [2], [3], [4], and [5]. In particular, the paper [6] develops resolving primal LP methods to solve the CMDP and achieves the first instance-dependent $\\tilde{O}(1/\\epsilon)$ sample complexity. I think these papers are worth mentioning in the literature.\n\nReferences:\n\n[1]. Yongshuai Liu, Jiaxin Ding, and Xin Liu. Ipo: Interior-point policy optimization under constraints. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 4940–4947, 2020.\n\n[2]. Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone. Risk-constrained reinforcement learning with percentile risk criteria. Journal of Machine Learning Research, 18(167):1–51, 2018.\n\n[3]. Yinlam Chow, Ofir Nachum, Aleksandra Faust, Edgar Duenez-Guzman, and Mohammad Ghavamzadeh. Lyapunov-based safe policy optimization for continuous control. arXiv preprint arXiv:1901.10031, 2019.\n\n[4]. Gal Dalal, Krishnamurthy Dvijotham, Matej Vecerik, Todd Hester, Cosmin Paduraru, and Yuval Tassa. Safe exploration in continuous action spaces. arXiv preprint arXiv:1801.08757, 2018.\n\n[5]. Tengyu Xu, Yingbin Liang, and Guanghui Lan. Crpo: A new approach for safe reinforcement learning with convergence guarantee. In International Conference on Machine Learning, pages 11480–11491. PMLR, 2021.\n\n[6]. Jiang, Jiashuo, and Yinyu Ye. \"Achieving $\\tilde{O}(1/\\epsilon)$ Sample Complexity for Constrained Markov Decision Process.\" NeurIPS, 2024.", "other_strengths_and_weaknesses": "Strength:\n\nThe paper develops the clever idea of considering the augmented state space by letting a state variable to denote the budget. The paper achieves the first sublinear regret for this type of risk-sentitive CMDP.\n\nWeakness:\n\n1. The current method applies to the case with a single-constraint. Though the authors claim that there is a way to extend to multiple constraints, it is not immediately clear to me and I suspect the current approach would make the computation time exponential in the number of constraints. Please refer to the questions below for more details over this weakness.\n\n2. It is not clear how the developed algorithm works in practice due to the lack of numerical experiments.\n\n3. The computation complexity of their algorithm has not been discussed.", "other_comments_or_suggestions": "Please refer to the questions below.", "questions_for_authors": "1. It is discussed in the extension that the current approach could extend to the multiple constraint case. However, it seems that the current approach optimizes over the augmented variable $\\tau$ by discretizing the range. If there are multiple constraints, will it be the case that a multi-dimensional space would need to be discretized? This will make the computation time exponentially large.\n\n2. Is there any intuition on the lower bound of the regrets for the risk-sensitive CMDP?\n\n3. Could you please provide any comment on the practical performance of the algorithm developed in the paper?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper makes a clear and novel contribution by proposing an algorithm for a specific class of risk-sensitive constrained Markov Decision Processes and establishing both sublinear regret and a bound on constraint violation--results that are the first for this particular formulation. The analysis leverages nontrivial techniques such as state augmentation, and no major flaws were identified during the review process.

However, the practical relevance of the work remains uncertain. This is partly due to the absence of numerical experiments, which limits the reader's ability to assess the empirical behavior of the proposed approach. Given that the studied formulation appears to be chosen in part for analytical tractability--rather than being the most natural or widely applicable model--it is especially important for the authors to include the promised experimental results in the final version.
Decision: Accept (poster)