A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalents
Authors: Kaiwen Wang
Dawen Liang
Nathan Kallus
Wen Sun
Venue: ICML 2025 poster (2025)
Keywords: Risk-Sensitive RL
Reduction to RL
OCE
CVaR
Variance
Primary area: theory->reinforcement_learning_and_planning
TL;DR: Provable algorithms for risk-sensitive RL with static OCE that reduce to standard RL oracles in an augmented MDP.

Abstract: We study risk-sensitive RL where the goal is learn a history-dependent policy that optimizes some risk measure of cumulative rewards.
We consider a family of risks called the optimized certainty equivalents (OCE), which captures important risk measures such as conditional value-at-risk (CVaR), entropic risk and Markowitz's mean-variance. In this setting, we propose two meta-algorithms: one grounded in optimism and another based on policy gradients, both of which can leverage the broad suite of risk-neutral RL algorithms in an augmented Markov Decision Process (MDP). Via a reductions approach, we leverage theory for risk-neutral RL to establish novel OCE bounds in complex, rich-observation MDPs. For the optimism-based algorithm, we prove bounds that generalize prior results in CVaR RL and that provide the first risk-sensitive bounds for exogenous block MDPs. For the gradient-based algorithm, we establish both monotone improvement and global convergence guarantees under a discrete reward assumption. Finally, we empirically show that our algorithms learn the optimal history-dependent policy in a proof-of-concept MDP, where all Markovian policies provably fail.

A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalents
Kaiwen Wang" 12
Dawen Liang?
Nathan Kallus 12 Wen Sun
Abstract
alternative risk- objectives (Yaari, 1987; Bowling et al., 2023). This is especially true in safety-critical settings (Artzner et al., 1999; Coronato et al., 2020; Wang et al., 2023b). In risk-sensitive RL (RSRL), the objective is some risk measure of cumulative rewards under a policy rather than the mean cumulative rewards (Howard and Matheson, 1972; Artzner al., 1999).
We study risk-sensitive RL where the goal learn dettor-d policy that optimizes some risk measure of cumulative rewards. We con- sider a family of risks called the optimized cer- tainty equivalents (OCE), which captures impor- tant risk measures such as conditional value-at- risk (CVaR), entropic risk and Markowitz's 's mean- variance. this setting, we propose two meta- algorithms: one grounded in optimism and an- other based on policy gradients, both of which can leverage the broad suite of risk-neutral RL algo- rithms in an augmented Markov Decision Process (MDP). Via a reductions approach, we leverage theory for risk-neutral RL to establish novel OCE bounds in complex, rich-observation MDPs. For the optimism-based algorithm, we prove bounds that generalize prior results in CVaR RL and that provide the first risk-sensitive bounds for exoge- nous block MDPs. For the gradient-based al- gorithm, we establish both monotone improve- ment and global convergence guarantees under a discrete reward assumption. Finally, we empiri- cally show that our algorithms learn the optimal distory-dependee policy in proof-of proof-of-coneee of-concept MDP, where all Markovian policies provably fail.
In this paper, we propose framework for solving RSRL with any static risk measure that can be expressed as op- timized certainty equivalent (OCE) (Ben-'la -aall and Teboulle, 2007). Specifically, for a utility function u. : IR - (-00,00) oo), the static OCE of policy π is defined as
OCE, == maxter (b E, Ex b)] (1)
where the expectation is w.r.t. the random cumulative re- ward Σx=1 7h under trajectories from π.. The OCE captures several important risks for different choices of u. For ex- ample, with the hinge utility u(t) = min(t/r, 0), OCE,, becomes CVaR at level 7 E (0, 1]. which measures the mean outcome among the worst r-fraction cases (Rockafellar and Uryasev, 2000). Moreover, OCE with the quadratic util- ity recovers Markowitz's mean-variance (Markowitz, 1952) and the exponential utility recovers entropic risk (Föllmer and Schied, 201 1). We present a primer OCE and more examples in App. B. We remark that another risk- sensitive objective is the iterated risk, which captures risk at each time step and orthogonal to our static risk objective (as we explain in related works Sec. 1.1).
1. Introduction
A key technical challenge in OCE RL is that optimal poli- cies in general non-Markovian (i.e., history-dependent), which renders this more complex than risk-neutral RL where Markovian optimal policy always exists. In prior works. promising solution is to augment the MDP with a new state that tracks the cumulative rewards so far, which has been studied for CVaR and spectral risks (Bäuerle and Ott, 201 Bäuerle and Glauner, 2021: Bastani et al., 2022). In this paper, we show that the augmented MDP (AugMDP) can be generalized with an OCE-based reward function to solve OCE RI. with Markovian augmented policies (Sec. 2. 1). We then propose two meta-algorithms that reduce OCE RL to neut-al RL by using the AugMDP as bridge.
In reinforcement learning (RL), the classical objective by which we measure how good is policy is the expected cu- mulative rewards along the trajectory (Sutton, 2004; Sutton and Barto, 2018). However, the mean reward of a choice (the choice of policy in RL being an example of such a choice) a risk niskrneutaal objective that is often observed to be incon- sistent with human preferences, causing Allais Paradoxes (Allais, 1990; Kahneman and Tversky, 2013) and calling for
'Cornell Tech Netflix Research. Correspondence to: Kaiwen Wang <kki wonw. git sithub. lo>. Work done as Netflix intern.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
First, in Sec. 3, we propose mega-algo based opti-

---

Risk-Sensitive RL with Static Optimized Certainty Equivalents
mistic RL oracles and we prove that its OCE regret can be bounded by the RI. oracle's regret within the Au up to a factor depending on (Thm. 3.2). We show that this approach can be instantiated with many RL oracles in- cluding UCB-VI for tabular MDPs (Azar et al., 2017) and Rep-UCB (Uchara et al., 2022) for low-rank MDPs, gener- alizing prior results in CVaR RL (Wang et al., 2023a; Zhao et al., 2024) to the OCE setting. While prior works in RSRL only considered model-based algorithms, we show that our approach is also amenable to the model-free optimistic RL oracle called GOLF (Jin et al., 2021). This establishes the first risk-sensitive RL bounds for exogenous block MDPs (Efroni et al., 2022; Xie et al., 2023).
(Uehara et al., 2022) in the Aug For entropic risk, Fei et al. (2020; 2021) proposed UCB- algorithms for tab- ular MDPs based on exponential Bellman equations. These prior works are limited to model- -ased optimistic oracles and largely do not extend heyond tabular MDPs, while our work provides a general framework for applying both model- free and model-based oracles to rich-observation OCE RL, including the challenging exogenous block MDP (Efroni et al., 2022). Moreover, these prior works are limited to CVaR or entropic risk, while our work provides a unifying framework for the broad class of OCE risk measures.
Chen et al. (2024) derives regret bounds for static Lipschitz risks under function approximation which is more related to our setting. However, their optimistic algorithm requires bounded eluder dimension or witness rank, which does not easily apply to the challenging exogenous block MDP set- ting. Indeed, the Bellman eluder dimension can grow with the size of the exogenous state space which is exponentially large or infinite (Xie et al., 2023). In contrast, we employ a coverability argument in the augmented MDP to obtain the first PAC bound for exogenous block MDP in risk-sensitive RL. Moreover, our work also studies other methods such as policy gradients, which are complementary optimistic algorithms.
Next, in Sec. 4, we propose a gradient-basee based meta-algorithm that uses policy gradient oracles and prove two types of guarantees: (1) convergence to the optimal OCE policy (Thm. 4.2), and (2) monotone improvement in risk lower bound (Thm. 4.4), novel property in RSRL theory. We in- stantiate our method with the natural policy gradient (NPG) oracle (Kakade, 2001) and prove these two guarantees un- der the standard conditions of policy optimization (Agarwal et al., 2021), plus a discrete reward assumption. Finally, our numerical simulation validates that our meta-algorithms can indeed learn the optimal OCE policy in a simple MDP where all Markovian policies (e.g., Dabney et al., 2018; Lim and Malik, 2022) must have sub-optimal performance. This validates our thesis that history-dependent, non- non-Markovian policies are required for OCE optimality.
There are also several prior works on gradient-base based RSRL algorithms that prove local and asymptotic convergence (Chow and Ghavamzadeh, 2014; Tamar et al., 2015a;b; Chow et al., 2018; Greenberg et al., 2022). These guar- antees are not ideal since (1) any local optima can be much worse than the global optima and (2) asymptotics do not quantify the rate of convergence which could be very slow. In contrast, we fill this gap by proving non-asymptotic finite- sample bounds for the global convergence of gradient-based algorithms, by leveraging recent advances in risk-neutral policy gradient theory (Agarwal et al., 2021; Xiao, 2022). Finally, we also prove monotone improvement which is a novel property for RSRL to the best of our knowledge.
In sum, our main contributions are the following:
1. We propose an optimistic meta-algorithm for OCE RL that generalizes all prior works in CVaaR to the more novel
general OCE setting. We also apply GOLF oracle and prove the first risk-sensitive bounds in the challenging exogenous block MDP. (Sec. 3)
2. We propose a gradient-basse based meta-algorithm for OCE RL that enjoys both local improvement and global convergence. These are the first finite-sample bounds for gradient-based RSRL algorithms. (Sec. 4)
From the empirical side, popular framework for RSRL is distributional RL (DistRL), which has demonstrated state- of-the-art art results in both online (Bellemare et al., 2017: Dabney et al., 2018; Keramati et al., 2020; Ma et al., 2020) and offline RI. (Urpí et al., 2021; Ma et al., 2021). At a high level, these algorithms learn the reward-to-go distribution and then greedily act to optimize the risk of the learned distribution at each step. Unfortunately, this can diverge for some MDPs since it is not consistent with any Bellman equations. To address this, Lim and Malik (2022) proposed to apply DistRL in an AugMDP, but their algorithm still relies on the strong assumption that the optimal policy is Markov, which is false in our counterexample (Sec. 5).
3. In numerical simulation, we show that our meta- algorithms indeed optimally solve OCE RL in a proof- of-concept MDP where Markovian policies provably have sub-optimal performance. (Sec. 5)
1.1. Related Works
From the theoretical side, prior works with deskssensitvee regret or PAC bounds are based on optimistic, model-based oracles for CVaR or entropic risk. For CVaR, Bastani et al. (2022); Wang et al. (2023a) proposed UCB-based algo- rithms for tabular MDPs by using the AugMDP proposed by Bäuerle and Ott (2011). Zhao et al. (2024) then extended this approach to low-rank MDPs using the Rep-UCB oracle
Another solution is Trajectory Q-Learning (TQL) (Zhou et al., 2023) which learns -epeedet policies and dis-
2

---

Risk-Sensitive RL with Static Optimized Certainty Equivalents
tributionnl Q-functions. While learning history-dependent policies ensures that TQL converges to the optimal RSRL policy, the learning process can be quite costly in sample complexity, computation and memory since it essentially ignores the Markov property of MDPs. Instead, our ap- proach searches over the minimal sufficient policy set, the Markovian policies in the AugMDP, to optimally solve OCE RL while also maintaining statistical and computa- tional efficiency. Finally, TQL. requires DistRL to learn the reward-to-go distribution, while our framework supports both regression- and distribution-base methods for learning the AugMDP value function.
We focus on the online setting, where at each round k 1, .....; K, the learner outputs (distory-dependent) policy nh E IHD.. The learner's goal is to minimize the total sub-optimality across K rounds:
RegocE (K) := >x OCE - (T*)
Probably approximately correct (PAC) bounds are upper bounds on Regoce( that hold with high probability over the randomness of the learner. In particular, PAC bounds imply that at least one policy has high OCE, i.e., minke]K)(OCEE,
OCE (T*)} I K Regoce(()). If the learner only executes policy x* at round k, then Regocr (K) is also called regret bound.
Iterated risk (a.k.a. dynamic risk). Another sensisvee RL objective the iterated risk p(ri + p(2 + p(ra+...) +...))), where p is some risk measure. The iterated risk, a.k.a. dy- namic risk, captures risk of the rewards-to-go each time step and has been studied by many works (Ruszczyíski, 2010; Du et al., 2023; Lam et al., 2023; Xu et al., 2023; Rigter et al., 2023; Liang and Luo, 2024). Dynamic risk also has close relations to distributionally robust MDPs, where an adversary can perturb the transition kernel at each time step (Wiesemann al., 2013; Kumar et al., 2023; Ben- nett al., 2024). The main benefit of iterated risk is that there exist Bellman equations and an optimal Markovian policy like in the classic RL setting. However, iterated risk may be overly risky in certain cases and overly conservative in other cases, and is also less interpretable due to the nested structure (Lim and Malik, 2022). In contrast, our static risk p(r1 + 12 + T3 )...) ) models the trajectory-Iever risk rather than at the step-level and is more interpretable. We highlight that static and dynamic risk are orthogonal objectives and the objective is ultimately the user's choice.
2.1. Augmented MDP for OCE
The key challenge in RSRL with static risk is that the opti- mal policies are history-dependent, as there are no Bellman- like equations. A promising solution from prior works is to augment the MDP with scalar state, which has been studied for CVaR and spectral risks (Bäuerle and Ott, 2011; Bäuerle and Glauner, 2021) - in this augmented state space, there does exist a Markovian optimal policy, bypassing the need to maintain history- dependent policies. In this section, we describe the augmented MDP (AugMDP) and extend it to the OCE setting, generalizing prior constructions.
The AugMDP has states (sh, by.) Saug := S x |-1, 1]. where s) is the original MDP state and b;, is a new scalar state called the budget, which intuitively tracks the cumula- tive rewards so far. The initial budget by E [0. 1] is chosen by the learning algorithm and the budget transitions via bp+1 = bn Th where rh is reward at step h. The re- ward of the AugMDP is defined as räug(s. b, a) 0 for h < H and rägg(s, b, a) = En- (s.)) [u(r - b)]. where /mmax = max [u(e]] measures the scale of raug. The augmented reward encodes the utility u and is critical for the following optimality theorem.
2. Preliminaries
We consider an MDP with state space S, action space A,
horizon H. transition kernels Ph : S x A + (SS) and con- ditional reward distributions RA : S A + A(0 1)), where A(S) denotes the set of distributions on the set S. A history-dependent policy π = (тл))е(н) interacts with the MDP in the following way: start from an ini- tial state $1, then, for each step h = ......., H, sam- ple an action ag ~ TH (8h, Hr), collect reward Ps ~ Rg (sh, an), observe the next state Sh+11 (sh a.). Here, Hn, = {(>i, di, re)] denotes the history so far. We denote the cumulative reward distribution under as 2(T) = Σd= The where randomness arises from both the MDP and the policy π. We also assume that ZTT) E [0, 1] almost surely for all policies (Jiang and Agarwal, 2018). The goal of OCE RL is to learn history-dependent policy that maximizes the OCE objective:
Theorem 2.1. There exists an initial budget bj E [0, I] s.I. the optimal risk-neutral Taug in the AugMDP with initial budget by achieves optimal OCE in the original MDP.
Since the optimal iiskrneutral policy Taug is Markovian and deterministic. this theorem crucially mitigates the need to maintain history-dependent policies. We note that (maug bi) is a special depeeret policy in the original MDP. Thus, Thm. 2.1 proves that the set of (Taug b1), where Tuug is Markovian augmented policy and 6₁ is an initial budget, is special class of depeenden policies that is suffi- cient for OCE optimality. Moreover, natural implementa- tion of Thm. 2.1 is to solve risk-neutral RL in the AugMDP, which is the key idea behind our algorithms. We remark that our AugMDP construction generalizes the CVaR AugMDP from (Bäuerle and Ott, 201 1) to any OCE risk.
OCE* := max OCE,(TT)
where THD denotes the set of history policies.
3

---

Risk-Sensitive RL with Static Optimized Certainty Equivalents
For the AugMDP, we also define its quality function Qaug Shy bu, a4) E,, [u[ rt 0b)) | Sh: On; by] and value function Vaug (Sh, bn) = Em (aug (on, nn bn, an)
Definition 3.1 (Optimistic oracle). At each round k: ; K, the oracle OPTALG first outputs an optimistic value function (-,, then sees initial state k and finally outputs a policy x which is rolled-out from $1,k to collect data. Two conditions must be satisfied:
1,2....;
Sh; bn.. Also, let Vaug (sh, bn) m THo Vaugi (sh, bn)
be the optimal value function of the AugMDP.
1. (Optimism) (11,(11) 2 (i)()))-= for all initial states opp $1, where Ek are slack variables;
The main step is to write OCE, in terms of the optimal value of the AugMDP:
Proof of Thm. 2.1.
OCE2 (
mal e (0.1] 1) (b (z) b)]}
2. (Bounded Regret) Ek=i (V ($1,()) - VT - Vmaa Regop(( (K), where Vmmax is the scale of cumu- lative rewards and Regopt (K) is bounds the total sub- optimality gap across K rounds. For this to be useful, Regom (K) should be sublinear in K, Le., O(VK).
max (b mal El[(Z((T) - b]]}
(6)
(0 (b max Vaug (8]
(Hl)
[ (b Vaug 611,)).
(3)
Step (i) uses OCE's definition in Eq. (1) and (T²) E [o, 1]
We remark that the conditions of OPTALG can be satis- fied in the Augmented MDP by modifying standard opti- mistic algorithms such as UCB-VI, Rep-UCB and GOLE, For model- -base oracles (e.g., UCB-V VI, Rep-UCB), the aug- mented transition kernel for is known and deterministic and thus introduces no extra statistical or computational complexity for model learning in the augmented MDP. For model-free oracles (e.g., GOLF), we need to be more careful and redefine important concepts such completeness and coverability in the augmented MDP. We provide detailed algorithms and proofs for satisfying OPTALG in App. D.
w.p. I, so the max, can be taken over [0, 1]. Step (ii) uses the definition of by and raug deduce that E,, [u,["(([, Fh
bi]] E, [M(H bx) | bi]
Er (SH1 bn, an)
b1] = (s, ($1, b1) for any π and bj. Step (iii) uses
the classical RL result that the optimal risk-neutral pol- icy augg achieves the maximum value Väúg over history- dependent policies (Puterman, 2014). Thus, letting bj arg (o. + Vaug (s1, b)), we have:
OTug 01)
m0ax (b + Ering dj (Taug: b1) bb]}
Given an oracle OPTALG, our optimistic meta-algorithm (Alg. 1) proceeds as follows: at each round k: = 1,2, 1....... K, we query OPTALG in the Aug and obtain an optimistic value function Vi,+(+). Then, we compute the initial budget by solving:
2 bi + Ering b1 (u( (TTug bi) - bi)]
= bj + Vaug (s1, b1) = OCE
This proves that (Tagg b1) achieves the optimal OCE; LI
Remark: the MDD is easy to simulate. The transition function for the augmented state by is simply ba+1 = by- The which is known and deterministic. This ensures that simulating the AugMDP is computationally efficient. This is also important for proving bounds in the AugMDP. For example, model-based algorithms do not need to learn the AugMDP transitions (since it known), so they generally inherent the same bounds in the original MDP.
by + arg max (b + Vi,u(s1, b1)}.
(4)
Finally, we give the initial state (s1, bb) OPTALG, receive policy m², and proceed to the next round. We now state our main result for Alg. 1.
Theorem 3.2. Assuming that OPTALG satisfies Def. 3.1, running Alg. I for K rounds ensures that:
K
Σ OCE; OCE,( (&) S VmNA Regop (K) +
3. Meta-Algorithm with Optimism
In this section, we propose a meta-algorithm for OCE RL based on optimistic RL oracles. Our framework generalizes existing works in CVaR RL to more OCE risk measures and to more complex MDPs such as exogenous block MDPs. At high level, the aeta-algorithm implements the intuition from Thm. 2.1 and has two parts: (1) we apply an RL oracle in the AugMDP to learn aug and (2) then select the right initial budget bj. We start by formally defining optimistic oracles, which are RL algorithms that can explore using optimistic value functions:
This theorem is a deterministic statement which bounds Alg. I's OCE regret by the oracle's AugMDP regret, up to scaling of V.max Here, V.max intuitively measures the statistical hardness of estimating OCE, relative to E, which has V.nax = 1. For instance, Vevan, -- Another intu- ition for Vmmax is the Lipschitz constant of the risk measure (Liang and Luo, 2024; Chen et al., 2024). Please see App. B for more examples. We now instantiate this result with three optimistic oracles from the RL. literature.

---

Risk-Sensitive RL with Static Optimized Certainty Equivalents
Algorithm 1 Meta-algorithm for optimistic oracles
3.1. Bounds for exogenous block MDPs
1: Input: number of rounds K, optimistic oracle OPTALG satisfying Def. 3.1.
We now present a third optimistic oracle called GOLF (Jin et al., 2021) and prove the first risk- bound in the challenging exogenous block MDP (Ex-BMDP) problem, due to Efroni et al. (2022).
2: for round k- = 1,2,.... K do
3: Query OPTALG in AugMDP for value func. (-,)(-).
4: Compute initial budget by via Eq. (4).
Definition 3.3. An Ex-BMDP has latent states (2% 2h e 2 x 2% where 2en is the endogenous part which is tabular, and g is the exogenous part which is arbitrarily large. The endogenous latent transition conditions on the action 2h41 PET an), while the exogenous does not Th+1 ~ (x((2)) (2%). The observation state is emitted from the latents 8h ~ (x(= : =xx) and, importantly, there exists a unique function 0% such that (s)) = (2% 25 recovers the latents from the observation.
5: Give initial state (s) to OPTALG and receive T².
6: Collect a trajectory with x² starting from bx).
7: end for
First, UCB-VI is a model-based algorithm for tabular MDPs with near-minimax minimax-optimall dependence on |S]. |S),) K (Azar et al., 2017). While the AugMDP not tabular due to the real-valued augmented state bn. the augmented state has a known and deterministic transition (ba+1 by, rh): hence, UCB-VI VI only needs to learn the original MDP's tran- sition model when operating in the AugMDP. Indeed, by adapting the proof of Wang et al. (2023a) in Thm. D.I, we prove that UCB-V VT satisfies Def. 3. Iss conditions in the Aug- MDP with ex 0 and Regop. (K) < ((V SIV/IAA AH Combined with Thm. 3.2, this immediately implies OCE regret bound of Ö(V /SAHKK) which is also near- minimax-optimal in (8), [AA,, K for tabular MDPs. More- over, in App. D.4, we obtain tight rates for CVaR using second-order oracles, showing our upper bound is tight.
the
GOLF is a value-based (model-free) RL algorithm that achieves optimism by optimizing over a version space of Q-functions (Jin et al., 2021). The version space con- sists of candidate Q-functions from a function class F = (Fh (h)))E(H) FR C Saug x A + IR whose Bellman backup is consistent with the data up to statistical noise. Value-based methods have shown promise in important applications such as LLM post-training (Mudgal et al., 2024; Zhou et al., 2025; Wang et al., 2025b). Due to space constraints, we defer the formal definition of GOLF in the AugMDP to App. D.3.
The standard condition required for Bellman-consisten al- gorithms like GOLF is completeness, which is required for Bellman backups to be well-behaved (Tsitsiklis and Van Roy, 1996; Munos and Szepesvári, 2008). Since we apply GOLF in the AugMDP, we posit completeness w.r.t. the AuD Bellman operator denoted as Taug.
The second oracle we discuss is Rep-UCB (Uehara et al., 2022), a model-based optimistic algorithm for low-rank MDPs (defined in Def. D.2), which are MDPs with rank d transition kernel and potentially infinite state space (Agar- wal et al., 2020); low-rank MDPs capture tabular MDPs and linear MDPs. Again, the original MDP being low-rank does not necessarily imply that the augmented MDP is low-rank. Fortunately, as before, the augmented state b,, has a known transition function and thus Rep-UCB only needs learn the low-rank transitions of the original MDP, even when running in the AugMDP. Indeed Zhao et al. (2024) proved that Rep-UCB enjoys the same PAC bound in the Aug- MDP as in original low-rank MDP. We adapt their proof in Thm. D.4 and show that Rep-UCB satisfies Def. 3s condi- tions in the AugMDP with (e S ((H3)
Assumption 3.4. Taug fn+1 E Fr, for all fi+1 E Fat1.
Another condition we require is discrete rewards (As- sump. 3.5), which we use for bounding coverability in the AugMDP (Xie et al., 2023). Many safety-critical RL prob- lems have discrete rewards, e.g., in sepsis treatment, reward is the patient's 's discharge status (Johnson et al., 2016).
Assumption 3.5. We have finite set B C [0, 1] such that (T)) E B w.p. 1 for all n, where (TT) is the cumulative reward of roll-outs from x.
and c opt < (Kg Together with Thm. 3.2, we thus have an OCE PAC bound of ÕV 3 [A VK), generalizing Zhao et al. (2024) to any OCE risk measure.
This assumption can be satisfied by discretizing rewards as is common in distributional RL (Bellemare et al., 2017; Imani et al., 2024; Ayoub et al., 2024; Wang et al., 2025a) and in theory (Bastani et al., 2022; Wang et al., 2023a).
We have presented two examples with model-based oracles, whose bounds naturally lifts to the AugMDP since the aug- mented state by has known and deterministic transition. In general, model-based oracles enjoy the same bounds in the AugMDP as in the original MDP, making them convenient oracles for our meta-ale meta-algorithm. Next, we discuss a model- free oracle to solve the challenging exogenous block MDP, where it is not tractable to learn the transition model.
We now state our main result for Ex-BMDPs.
Theorem 3.6. For 8 (0,1), under Assumps. 3.4 and 3.5, running Alg. I with OPTALG as GOLF (Alg. 5 in App. D.3)
ensures that w.p. 1 1-6 8.
1=11 OCE" - OCE, ( 0x))
S 5((Vmax H |3| A
log( (F188))
5

---

Risk-Sensitive RL with Static Optimized Certainty Equivalents
Notably, the bound scales with the endogenous state size | and the function class's complexity log((F));; indeed, all salient problem parameters matches the original risk- neutral bound from Xie et al. (2023). The completeness assumption may be weakened to realizability if we have lo- cal simulator access (Mhammedi et al., 2024); but otherwise unavoidable even restrll RL (Jin et al., 2021; Xie et al.. 2023). Thus, Thm. 3.6 demonstrates the versatility of our meta-algorithm to solve challenging MDPs that go beyond tabular and low-rank.
Algorithm 2 Meta-algorithm for PO oracles
1: Input: number of rounds K, initial budget set B (As- sump. 3.5), oracle POALG (Def. 4.1).
2: Let d:uu = (5(s1) (l)) be the init. augmented state distribution. Initialize POALG with di
3: for round A: = ..2..... K do
4: Obtain policy x and value estimate Vir" from run- ning POALG in the AugMDP.
5: Compute the initial budget by with Eq. (5).
6: Give init. augmented state (s1, to POALG.
To prove Thm. 3.6, we need to show that GOLF satisfies the OPTALG conditions in Def. 3.1 with Regom I (H B|| = | [ and E = O. Due to completeness, we can invoke GOLF's coverability regret bound from Xie et al. (2023). Then, prove that the AugMDP coverability is bounded by |B|| ||| in Ex-BMDPs via a change-of- measure argument. Then, Thm. 3.6 immediately follows from Thm. 3.2. Please see App. D.3 for the full proof.
7: end for
where the last inequality is due to the oracle's regret bound (second condition of Def. 3.1).
Computational Complexity of Alg. 1. There are two sources of computational cost. The first cost is OPTALG: from the examples we discussed, UCB-VI VI and Rep-UCB are computationally and oracle efficient while GOLF is inef- ficient due to its version space optimism (Dann et al., 2018). So long as OPTALG is computationally efficient, then calls to OPTALG should also be efficient. The second cost is by: computing Eq. (4) exactly is difficult since the objec- tive is non-convex. However, it can be efficiently approxi- mated by projecting rewards to a discrete grid with spacing O(1K), so each round's Eq. (4) can be done in O(K) time. Notably, the approximation error per round is at most Hi and across K rounds is at most O(H K) O(H), which is a lower order term (Wang et al., 2023a, App. H). Thus, provided that the oracle is efficient, Alg. both computationally and statistically efficient for OCE RL.
Remark on Discrete Rewards. It is possible to relax As- sump. 3.5 by rounding rewards to fixed bins spaced c apart. This discretization of width introduces an additional regret of most O(V Ke) and creates [B] O(1/c) (Wang et al., 2023a). Thus, if an algorithm has regret bound of ())) then applying this discretization would yield regret bound of O(vimax /K/c- + V V.max Kc). Then, we can choose O(K- to yield regret bound of O(V.Ta*X K2/3) which is sublinear. Thus, even when re- wards are continuous, we can avoid Assump. 3.5 by dis- cretizing rewards and paying a regret with rate O(K3/3) instead of the minimax-optimal rate of O(K1/2).
3.2. Proof for Main Reduction (Thm. 3.2)
Proof of Thm. 3.2. First, we upper bound OCE;;
4. Meta--Agoriithm with Policy Optimization
OCE;
bj + auu (s1, bi)
In this section, we propose a meta-algorithm that uses stan- dard policy optimization (PO) oracles, which enjoy a new type of guarantee called local improvement that ensures the policy's performance monotonically improves at each round, First, we formalize the conditions needed for the risk-neutral PO oracle, which we remark is satisfied by gradient- mradient-based a algorithms such as REINFORCE, NPG and PPO (Kakade, 2001; Agarwal et al., 2021; Grudzien et al., 2022).
(1))
S bj + (3,, bj) + ck
(m0)
< by + Vi. + opr
where (i) is by Sec. 2.1, (ii) is by optimism of the oracle (first condition of Def. 3. 1), and (iii) is by the definition of be via Eq. (4). Second, we lower bound OCE, ( bx):
Definition 4.1 (PO Oracle). Let di denote an exploratory initial state distribution. At each round k = 1, 2....... K, the oracle POALG outputs a policy x² and its value estimate V (-) such that Ee,,d, IVT* (s1) VT= (si) < eBo Then, there are two conditions on { "<eee()) performance:
OCE, ( Tw)) max (b E[u(( (Z(k Tw) b]]} 2 by + E bb)
= Th + Vaug .1 (s1,bx).
Thus, En OCF, - -CCFu ( TTx) is bounded by:
1. (Approx. Improvement) Vi=" (di) > VT (di) - Po where V(d1) == Ex,rd, ((s)) and E are slack vars;
$ En (11, ba) - x² . (s1, bb)) + sk opt
< V.max Regop (K) + * c
opt
2. (Global Convergence) I (V/(()) - VT (d:)) S
6

---

Risk-Sensitive RL with Static Optimized Certainty Equivalents
Vmax Regpo (K) where Re K)) bounds the total sub- optimality gap of POALG across K rounds.
Lemma 4.3 (RLB). The RLB( approximately lower xh bounds the true OCE of with initial budget by:
RLB (k) - OCE,, b&) S 2|Blek
(7)
Since this oracle will be applied in the AugMDP, the y=* term will be set as Vaug. Moreover, we remark that the small
Moreover, the lower bound is tight on average:
estimation error condition (Vr= (s1) (5)) po eg can be satisfied by via off-policy evaluation (OPE) by using the data collected in prior rounds (Munos and Szepesvári, 2008; Chang al., 2022; Kallus and Uchara, 2020). Given access simulator, can of course also es- timate the value by collecting online Monte Carlo roll-outs.
PT- (s1)l 1
Σn OCE,(T (w) - -RLB < <BlV Regro
We state the approximate improvement guarantee. Theorem 4.4 (Local Improvement). Under Assump. 3.5 and assuming POALG satisfies the approximate improvement criterion of Def. 4.1, running Alg. 2 ensures that:
Given the oracle POALG, our meta-algorithm (Alg. 2) pro- ceeds as follows: at each round I: = 1, 2. K, we query POALG with the initial budget distribution (B), where B the set of possible initial budgets that we assume to be discrete (Assump. 3.5). We require Assump. 3.5 because PO oracles, unlike optimistic ones, do not strategically explore and thus rely on an exploratory initial state distribution even in risk-neutral RL (Agarwal et al., 2021). Then, POALG returns policy x and an estimate of its value Vi (+), with which we compute the initial budget by via
4k E [K] RLB(++1) 2 RLB 1188")-1BB86 -B16
This theorem shows that Alg. 2's policies are approximately improving at each step. up to an error |B| Hence, if the value estimation error from POALG is small, then the new policy's RLB cannot be much worse than the current. While local improvement is known for risk-neutral RL (Agarwal et al., 2021), to the best of our knowledge, Thm. 4.4 is the first analog in risk-sensitive RL. In sum, Thm. 4.2 and Thm. 4.4 provide complementary global and local guaran- tees for OCE RL, stated in finite-sample manner.
by f arg max (br + b1)
(5)
This is different from the optimistic version (Eq. (4)) since the maximization is restricted to B. We now state our main results for Alg. 2, starting with global convergence.
12 1.5 x Ber(0.75)
a1
Theorem 4.2 (Global Convergence). Under Assump. 3.5 and assuming POALG satisfies the global convergence cri- terion of Def. 4.1, running Alg. 2 ensures that:
1
Ber(0.5)
2
0.5 w.p.
Σk= OCE - -OCE, (** (x)
Figure I. A simple MDP where the optimal CVaR policy history- dependent. Each policy's 's cumulative reward distribution is shown in the table helow.
S (V Regro (K) 2
This theorem bounds Alg. 2's sub-optimality by the PO or- acle's sub-optimality, up factor of [B] Viaa,, plus the value estimation errors. Thus, if POALG has small value estimation errors and converges to the optimal policy, then Alg. 2 converges to the optimal OCE policy. We high- light that Thm. 4.2 is a finite-sample PAC bound whereas prior guarantees for risk-sensitive policy gradients have been asymptotic (Tamar al., 201 5a:b).
Action $2
Cumulative-Rewall Dist.
CVaRo.25
[0.. 1/a), (1, 1/a) (1.5, (2.5, 1/s)
(Markov)
0.5
02 (Markov)
[[0.5, 1/2), (1.5, 1/2)
0.5
a1 if r
{(0, 1/8), 7/s))
0.75
a2 ifr==
Table I. The cumulative reward distribution of Markovian policies (rows 1-2) and the optimal policy (row 3). For the distribution. {V.,P.) denotes random variable that takes value i, w.p. Pt. s.t. Σ, The optimal CVaR policy has CVaR2 0.75 while both Markovian policies have CVaRe.25 = 0.5.
Next, toward stating the local improvement result, we intro- duce the risk lower bound (RLB) (KB(()) defined as:
RLB(x)= == maxt,es (br + Vang (s1, b1))-
(6)
4.1. Case Study: Natural Policy Gradient
Notice that the lower bound is tight at n": RLB(T*)
OCE due Eq. (3). In general, RLB approximately lower bounds the true OCE of (1th, by), as the following lemma proves.
As an example POALG, we consider natural policy gradients (NPG; Kakade, 2001) whose core ideas underpin TRPO and PPO (Schulman al., 2015; 2017). Let = denote
7

---

Risk-Sensitive RL with Static Optimized Certainty Equivalents
OCE
Optimistic Alg (Alg. 1)
PO Alg (Alg. 2)
Best Markovian
Markovian Optimal?
E Var(X)
1.07 = 0.01
1.06 + 0.01
0.95
E E 2Vr(())
0.81 + 0.01
0.75 + 0.08
0.5
X
Entr- 1.o (.0 x
1.25 + 0.01
1.23 + 0.03
1.25
(X)
0.90 0.02
0.90 + 0.01
0.91
/
CVaRu.28 25 (X)
0.75 + 0.02
0.71 + 0.08
0.5
X
cVaRn.5(X)
1.12 + 0.03
1.12 + 0.03
1.0
X
Table We benchmark our optimistic Alg. with UCB-VI VI as OPTALG and our PO Alg. 2 with NPG as POALG against the best Markovian policy for various OCEs. We repeat the experiment 10 times and report 95% confidence intervals for the average performance.
an augmented policy with parameters On Then, the NPG update is given by
The MDP is designed so that the optimal CVaR policy is non- Markovian. Due to the MDP's simplicity, we can compute the optimal CVaR and the Markovian policies' CVaR in closed form, which we list in Table 1. Specifically, the optimal action at 82 depends on the random outcome of the first reward T1: if r1 0 then should be risky and pick di; ri then it should be conservative and pick 0g. This optimal policy achieves CVaR 0.75, while Markovian policies, which do not react to rı, can only achieve CVaRo.25 25 0.5. This reinforces our thesis that policies are required for optimality.
0 = 0% + n Vo, Vaug
(8)
where Fh.K- E Vo log ( Sh: by V log (an
Sb, by) [] the Fisher info matrix and FR, is its pseudo- inverse. A special class of policies are softmax policies: (a s, x exp(O",..a) with 0%. 20,00 R. Under softmax parameterization, the NPG update in Eq. (8) is equivalent to soft policy iteration (Kakade, 2001):
.h*+1 (a s. x (a s, b) cxp(n Qaig (s, b, a)).
Experiment with tabular policies. We now apply our meta-algorithms the synthetic MDP. For our optimistic meta-algorithm (Alg- 1), we UCB-VI (Azar et al., 2017) the oracle OPTALG. For our gradient- based meta- algorithm (Alg. 2), we use NPG as the oracle POALG. We evaluate our algorithms and compute the best Markovian policies for six OCEs: two CVaRs, two entropic risks and two mean mean-variances, where recall CVaR and entropic risks are defined as:
We now show that NPG in the AugMDP satisfies both condi- tions Def. 4.1. First, for local improvement, Agarwal et al. (2021, Lemma 5.2) implies that Un- = (s1. b) Vaug (s), b)] 2 O, which uses the fact that the initial budget distribution is UB). Then, for global conver- gence, Agarwal al. (2021, Theorem 5.3) proves that (e) < (H)), provided we set an appropriate learn- ing rate 17 = H log [A). Thus, NPG satisfies Def. 1 so we can apply both Thm. 4.2 and Thm. 4.4. To the best of our knowledge, these are the first non-asymptotic guarantees for grad risk-sensitive RL. App. E.I, we ex- tend this analysis further to smooth policy parameterization and unknown Qaug functions, using compatible function approximation à la Agarwal al. (2021); Xiao (2022).
CVaR, (X) == maX (b - E[ - X)+I,
Entra (X) In E(exp(33.))
The results are in Table 2 and we see that our algorithms are consistently better than the best Markovian policy. We remark that entropic risk is special case where the optimal policy is Markovian (Fei et al., 2020; 202 I); nonetheless, algorithms still consistently learn the optimal policy despite AugMDP not being necessary for entropic risk.
5. Simulation Experiments
We describe a numerical simulation to demonstrate the im- portance of learning history-dependent policies for OCE RL and to empirically evaluate our algorithms. Our code can be found at https:/ tttpp::/ggitti /ggttub..b/tt////// com/ www.www/wwwwwe////
Experiment with neural network policies. To test the versatility of our PO algorithm (Alg. 2), we also evaluate three deep RL oracles: PPO with forward KL (Schulman et al.. 2017), PPO with backward KL (Hsu al., 2020), and REINFORCE (Sutton et al., 1999). Using neural networks to approximate the policy and Q functions, we train all three oracles to maximize CVaRo.25 in the synthetic MDP.
Setting up synthetic MDP. The proof-of-concept MDP is shown in Figure and has two states. At 81, all actions lead
to a random reward rı (er(0.5) and transits to 82. At 82, the first action a gives a random reward F2 $2, aj ~ 1.5- (er(0.75), while another action d2 gives a deterministic reward r2 82, 02 = 0.5. The trajectory ends after 82.
We plot the learning curves in Figure 2, where we see that Alg. consistently converges to the optimal CVaR value of 0.75 for all three oracles. An interesting trend that
8

---

Risk-Sensitive RL with Static Optimized Certainty Equivalents
Policy Optimization for CVaR
Impact Statement
Best Hictory-Seprrder Palicy
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
0.0
Coelt stve
0.5
Marta NitE
References
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and represen- tation learning of low rank mdps. Advances in neural information processing systems, 33:20095-20107, 2020.
0.4-
RE NFFORC
2000
4000
6000
2000
10000
32000
34000
step
Figure 2. Learning curves for Alg. 2 with three oracles: REIN- FORCE and PPO with fwd & bwd KL. We repeat runs five times and report 95% confidence intervals for the mean performance.
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. The Journal of Machine Learning Research, 22(1):4431-44 -506, 2021.
Alg. 2 tends first plateau at Markovian policy at 2k steps, and then eventually converge to the optimal non- Markovian policy at ~ 8k steps, suggesting that Marko- vian policies are perhaps easier-to-learn local optima in the AugMDP. Nonetheless, our algorithm consistently con- verges to the optimal policy given enough gradient steps. In sum, our experiments demonstrate the importance of history- dependent policies in risk-sensitive RL and the effectiveness of our AugMDP algorithms. We report all hyperparameters and training details in App. C.
Maurice Allais. Allais paradox. In Utility and probability, pages 3-9. Springer, 1990.
Philippe Artzner, Freddy Delbaen, Jean-Mare Eber, and David Heath. Coherent measures of risk. Mathematical finance, 9(3):203-228. 1999.
Alex Ayoub, Kaiwen Wang, Vincent Liu, Samuel Robert- son, James McInerney, Dawen Liang, Nathan Kallus, and Csaba Szepesvári. Switching the loss reduces the cost in batch reinforcement learning. In Forty-first International Conference on Machine Learning, 2024.
6. Conclusion
In this paper, we proposed two meta-algorithms for RSRL with the static OCE risk. These meta-algorithms provide general reduction from OCE RL risk-neutral RL in the augmented MDP framework. First, we proposed an optimistic algorithm (Alg. 1) that generalizes all prior bounds in CVaR RL to the OCE setting when UCB-VI and Rep-UCB are used as the optimistic oracle. Moreover, using GOLF as the optimistic oracle, we proved the first risk- sensitive regret bounds for exogenous block MDPs. Sec- ond, we proposed gradient-based meta-algorithm (Alg. 2) that enjoys both global convergence and local improvement. With this framework, we deduced the first finite-sample bounds for policy gradients in risk-sensitive RL. Finally, we evaluate our algorithms in a proof-of-concep MDP where they consistently learn the optimal policy and outperform the best Markovian policy. A promising direction for future work is to scale our ideas to more complex tasks such as robotics or finetuning LLMs (Ouyang et al., 2022). Given the plurality of values and risks, it is also promising to apply our ideas to design algorithms for risk-sensitive pluralistic alignment (Sorensen et al., 2024; Wang et al., 2024a).
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272. PMLR, 2017.
Osbert Bastani, Yecheng Jason Ma, Estelle Shen, and Wan- qiao Xu. Regret bounds for risk-sensitive reinforcement learning. In Alice H. Oh, Alekh Agarwal, Danielle Bel- grave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL https: // //oenrevieew eew..www.... net. forum? d=y.EUDf2TTT...
Nicole Bäuerle and Alexander Glauner. Minimizing spec- tral risk measures applied to markov decision processes. Mathematical Methods of Operations Research, 94(1); 35-69, 2021.
Nicole Bäuerle and Jonathan Ott. Markov decision pro- cesses with vvorage-value-tteee criteria. Mathematical Methods of Operations Research, 74(3):361-37,, 201
Acknowledgementts This work was supported by Google PhD fellowship and grants NSF 115-1154,,,, NSF CA- REER 2339395, IIS- 1846210, and DARPA LANCER: LeArnnng Network CybERagents.
Mare G Bellemare, Will Dabney, and Rémi Munos. A distributional perspective on reinforcement learning. In International Conference on Machine Learning, pages 449-458. PMLR, 2017.
9

---

Risk-Sensitive RL with Static Optimized Certainty Equivalents
Aharon Ben-Tal and Mare Teboulle. An old-new concept of convex risk measures: The optimized certainty equivalent. Mathematical Finance, 17(3):499476, 2007.
exogenous distractors using multistep inverse dynamics. In International Conference Learning Representations, 2022. URL https: /ttp///peeeeeeeeeeeeeeeeeeeeeeee net forum? i id-RoLLaMCefQu.
Andrew Bennett, Nathan Kallus, Miruna Oprescu, Wen Sun, and Kaiwen Wang. Efficient and sharp off- off-policy evaluation in robust markov decision processes. Advances in Neural Information Processing Systems, 2024.
Yingjie Fei, Zhuoran Yang, Yudong Chen, Zhaoran Wang, and Qiaomin Xie. Risk-sensitive reinforcement learning: Near-optimal risk-sample tradeoff in regret. Advances in Neural Information Processing Systems, 33:22384- 22395, 2020.
Michael Bowling, John Martin, David Abel, and Will Dab- ney. Settling the reward hypothesis. In International Con- ference on Machine Learning, pages 3003-3020. PMLR, 2023.
Yingjie Fei, Zhuoran Yang. Yudong Chen, and Zhaoran Wang. Exponential bellman equation and improved re- gret bounds for risk-sensitive reinforcement learning. Ad- vances in Neural Information Processing Systems, 34: 20436-20446, 2021.
Jonathan Chang, Kaiwen Wang, Nathan Kallus, and Wen Sun. Learning bellman complete representations for of-
fline policy evaluation. In International Conference on Machine Learning, pages
1. PMLR, 2022.
Hans Föllmer and Alexander Schied. Stochastic finance: an introduction in discrete time. Walter de Gruyter, 2011. 1.
Yu Chen, XiangCheng Zhang, Siwei Wang, and Longbo Huang. Provable risk-sensitive distributional rein- forcement learning with general function approxima- tion. In Forty-first International Conference Machine Learning, 2024. URL https: / wowp/eeveeee...eeoooeeee net. forum? 0xddd=00ffffxmmmmmm FF..
Ido Greenberg, Yinlam Chow, Mohammad Ghavanzadeh, and Shie Mannor. Efficient risk-averse reinforcement learning. Advances in Neural Information Processing Systems, 35:32639-3222 2022.
Jakub Grudzien, Christian A Schroeder De Witt, and Jakob Foerster. Mirror learning: A unifying framework of policy optimisation. In International Conference Machine Learning, pages 7825-7844, PMLR, 2022.
Yinlam Chow and Mohammad Ghavamzadeh. Algorithms for evar optimization in mdps. Advances in neural infor- mation processing systems, 27, 2014.
Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone. Risk-constr reinforcement learn- ing with percentile risk criteria. Journal of Machine Learning Research, 18(167):1-1,, 2018.
Ronald Howard and James E Matheson. Risk-sensitive markov decision processes. Management science, 18(7): 356-369, 1972.
Chloe Ching-Yun Hsu, Celestine Mendler-Dtinner, and Moritz Hardt. Revisiting design choices in proximal policy optimization. arXiv preprint arXiv:2009. 2020.
Antonio Coronato, Muddasar Naeem, Giuseppe De Pietro, and Giovanni Paragliola. Reinforcement learning for intelligent healthcare applications: A survey. Artificial intelligence in medicine, 101910,,,4, 2020.
Audrey Huang, Jinglin Chen, and Nan Jiang. Reinforce- ment learning in low-rank mdps with density features. In International Conference on Machine Learning, pages 13710-13752. PMLR, 2023.
Will Dabney, Georg Ostrovski, David Silver, and Rémi Munos. Implicit quantile networks for distributional re- inforcement learning. In International conference on machine learning, pages 1096-1105. PMLR, 2018.
Ehsan Imani, Kai Luedemann, Sam Scholnick-Hughes, Esraa Elelimy, and Martha White. Investigating the histogram loss in regression. arXiv preprint arXiv:2402. 13425, 2024.
Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alckh Agarwal, John Langford, and Robert Schapire. On oracle-efficient pac rl with rich observations. Advances in neural information processing systems, 31, 2018
Nan Jiang and Alekh Agarwal. Open problem: The depen- dence of sample complexity lower bounds on planning horizon. In Conference On Learning Theory, pages 3395- 3398. PMLR, 2018.
Yihan Du, Siwei Wang, and Longbo Huang. Provably effi- cient sensitvne reinforcement learning: Iterated CVar and worst path. In The Eleventh International Conference on Learning Representations, 2023. URL https:// -HNW-
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. Advances in neural informa- tion processing systems, 14:13406--133 2021.
openreview wwtp::ttttttttttmttteemmmmaa
Yonathan Efroni, Dipendra Misra, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Provably filtering
10

---

Risk-Sensitive RL with Static Optimized Certainty Equivalents
Alistair EW Johnson, Tom J Pollard, Lu Shen, Li-wei H Lehman, Mengling Feng, Mohammad Ghassemi, Ben- jamin Moody, Peter Szolovits, Leo Anthony Celi, and Roger G Mark. Mimic-iii, a freely accessible critical care database. Scientific data, 3(1):1-9, 2016.
HM Markowitz. Portfolio selection, the journal of finance. 7 (1). N, 1:71-91, 1952.
Zakaria Mhammedi, Dylan Foster, and Alexander Rakhlin.
The power of resets in online reinforcement learning. In The Thirty-eighth Annual Conference on Neural In- formation Processing Systems, 2024. URL https: / openreview net/ for.mrormmii woorummid=sscccaatoo d=s.accaccscc.c......
Daniel Kahneman and Amos Tversky. Prospect theory: An analysis of decision under risk. In Handbook of the fundamentals of financial decision making; Part I, pages 99-127. World Scientific, 2013.
Sidharth Mudgal, Jong Lee, Harish Ganapathy, Yaguang Li, Tao Wang, Yanping Huang, Zhifeng Chen, Heng- Tze Cheng, Michael Collins, Trevor Strohman, et al. Con- trolled decoding from language models. In International Conference on Machine Learning, pages 36486-36500 PMLR, 2024.
Sham M Kakade. A natural policy gradient. Advances in neural information processing systems, 14, 2001.
Nathan Kallus and Masatoshi Uehara. Double reinforcement learning for efficient off-policy evaluation in markov de- cision processes. Journal of Machine Learning Research, 21(167):1-63, 2020.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Reseurch, 9()., 2008
Ramtin Keramati, Christoph Dann, Alex Tamkin, and Emma Brunskill. Being optimistic to be conservative: Quickly learning a ovar policy. In Proceedings of the AAAI con- ference on artificial intelligence, 2020.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Car- roll Wainwright, Pamela Mishkin, Chong Zhang, Sand- hini Agarwal, Katarina Slama, Alex Ray, et al. Training language models follow instructions with human feed- back. Advances in neural information processing systems. 35:27730- 27744, 2022.
Navdeep Kumar, Esther Derman, Mathhiu Geist, Kfir Yehuda Levy, and Shie Mannor. Policy gradient for rectangular robust markov decision processes. In Thirty-seventh Conference on Neural Information Pro- cessing Systems, 2023. URL https: http///eeeeeeeeeeeeeeeeeee net/
Fabio Pardo, Arash Tavakoli, Vitaly Levdik, and Petar Kor- mushev. Time limits in reinforcement learning. In Inter- national Conference on Machine Learning, pages 4045- 4054, PMLR, 2018
Thanh Lam, Arun Verma, Bryan Kian Hsiang Low, and Patrick Jaillet. Risk-aware reinforcement learning with coherent risk measures and non-linear function approx- imation. In The Eleventh International Conference on Learning Representations, 2023. URL https:// // openreview met/forumm d= RwZOVybbj.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sonn, 2014.
Mare Rigter, Bruno Lacerda, and Nick Hawes. One risk to rule them all: A risk-sensitive perspective on model- based offline reinforcement learning. Advances in Neural Information Processing Systems, 36, 2023.
Hao Liang and Zhiquan Luo. Regret bounds for risk- sensitive reinforcement learning with lipschitz dynamic risk measures. In International Conference on Artifi- cial Intelligence and Statistics, pages 1774-1782. PMLR, 2024.
R Tyrelll Rockafellar and Stanislav Uryasev. Optimization of conditional value-at-risk. Journal of risk, 2:21 --21-4, 2000.
Shiau Hong Lim and Ilyas Malik. Distributional reinforce- ment learning for risk-sensitive policies. Advances in Neu- ral Information Processing Systems, 35:30977-30989, 2022.
Andrzej Ruszczyússi. Risk-averse dynamic programming for markov decision processes. Mathematical p program- ming, 125:235-261, 2010.
Xiaoteng Ma, Li Xia, Zhengyuan Zhou, Jun Yang, and Qianchuan Zhao. Dsac: Distributional soft actor critic for risk-sensitive reinforcement learning. arXiv preprint arXiv:2004. 14547, 2020.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jor- dan, and Philipp Moritz. Trust region policy optimization. In International conference machine learning, pages 1 1897. PMLR, 2015.
Yecheng Ma, Dinesh Jayaraman, and Osbert Bastani. Con- servative offline distributional reinforcement learning. Ad- vances in Neural Information Processing Systems, 34: 19235-19247, 2021.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Rad- ford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 067407 2017.

---

Risk-Sensitive RL with Static Optimized Certainty Equivalents
Taylor Sorensen, Jared Moore, Jillian Fisher, Mitchell L Gordon, Niloofar Mireshghallah, Christopher Michael Rytting, Andre Ye, Liwei Jiang, Ximing Lu, Nouha Dziri, et al. Position: A roadmap to pluralistic alignment. In International Conference on Machine Learning, 2024.
Kaiwen Wang, Owen Oertell, Alekh Agarwal, Nathan Kallus, and Wen Sun. More benefits of being distri- butional: Second-order bounds for reinforcement lear-- ing. In Forty-first International Conference on Ma- chine Learning, 2024h. URL htw.t::///////m https///ppeeeeiieeee net/ formm wineinddd----e k2BCkkkBCCFFe3
Richard S. Sutton. The reward hypothesis. http:// incompleteiden htt.:eeteeeeeae.eeeeeeaaeeeeeeee wwweeeeeerneeee.eeeeeeeeeieeeaae cs ualberta. htm1,20 2004.
Kaiwen Wang, Nathan Kallus, and Wen Sun. The central role of the loss function in reinforcement learning. Statis- tical Science, 2025a.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Kaiwen Wang, Jin Peng Zhou, Jonathan Chang, Zhaolin Gao, Nathan Kallus, Kianté Brantley, and Wen Sun. Value-guided search for efficient chain-of-thought soning. arXiv preprint arXiv:2505.17373 2025b.
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforce- ment learning with function approximation. Advances in neural information processing systems, 12, 1999.
Zhiyong Wang. Dongruo Zhou, John Lui, and Wen Sun. Model-based rl as a minimalist approach to horizon-free and second-order bounds. arXiv preprint arXiv:2408.0888 08994, 2024c.
Aviv Tamar, Yinlam Chow, Mohammad Ghavamzadeh, and Shie Mannor. Policy gradient for coherent risk measures. Advances in neural information processing systems, 28, 2015a.
Wolfram Wiesemann, Daniel Kuhn, and Berç Rustem. Ro- bust markov decision processes. Mathematics of Opera- tions Research, 38(1 (0(() 1:11-183,, 2013.
Aviv Tamar, Yonatan Glassner, and Shie Mannor. Opti- mizing the cvar via sampling. In Twenty-inth AAAI Conference on Artificial Intelligence, 2015b.
Lin Xiao. On the convergence rates of policy gradient methods. Journal of Machine Learning Research, 23 (282):1-36, 2022.
John Tsitsiklis and Benjamin Van Roy. Analysis of temporal- diffference learning with function approximation. Ad- vances in neural information processing systems, 9, 1996.
Tengyang Xie, Dylan J Foster, Yu Bai, Nan Jiang, and Sham M. Kakade. The role of coverage in online rein- forcement learning. In The Eleventh International Confer- ence Learning Representations, 2023. URL https: / //openreview.ree ftr.m//orrm///// ddn 2ww.ttt222PPPt22300
Masatoshi Uehara, Xuezhou Zhang, and Wen Sun. Repre- sentation learning for online and offline RL in low-rank MDPs. In ICLR, 2022. URL https: / epenreview. Sett/oorumiid-Jae
Wenhao Xu, Xuefeng Gao, and Xuedong He. Regret bounds for markov decision processes with recursive optimized certainty equivalents. International Conference on Ma- chine Learning. 2023.
Núria Armengol Urpi, Scbastian Curi, and Andreas Krause. Risk-averse offline reinforcement learning. Interna- tional Conference on Learning Representations, 2021.
Menahem E Yaari. The dual theory of choice under risk. Econometrica: Journal of the Econometric Society, pages 95-115, 1987.
Kaiwen Wang, Nathan Kallus, and Wen Sun. optimal risk-sensitive reinforcement learning with cvar. International Conference on Machine Learning, 2023a.
Andrea Zanette and Emma Brunskill. Tighter problem- dependent regret bounds in reinforcement learning with- out domain knowledge using value function bounds. In International Conference on Machine Learning, pages 7304-7312. PMLR, 2019.
Kaiwen Wang. Junxiong Wang, Yueying Li, Nathan Kallus, Immanuel Trummer, and Wen Sun. Joingym: An effi- cient query optimization enviromment for reinforcement learning. arXiv preprint arXiv:2307.11704 2023b.
Kaiwen Wang. Rahul Kidambi, Ryan Sullivan, Alekh Agar- wal, Christoph Dann, Andrea Michi, Marco Gelmi, Yunx- uan Li, Raghav Gupta, Avinava Dubey, et al. Conditional language policy: A general framework for steerable multi- objective finetuning. Findings of Empirical Methods in Natural Language Processing, 2024a.
Yulai Zhao, Wenhao Zhan, Xiaoyan Hu, Ho fung Leung, Farzan Farnia, Wen Sun, and Jason D. Lee. Provably efficient CVar RL in low-rank MDPs. In The Twelfth International Conference on Learning Representations, 2024. URL https://////.....t. /ppenreviewwweeeeeee net/ forum? id=9x6yrFAPnx.
12

---

Risk-Sensitive RL with Static Optimized Certainty Equivalents
Jin Peng Zhou, Kaiwen Wang, Jonathan Chang, Zhaolin Gao, Nathan Kallus, Kilian Q Weinherger, Kianté Brant- ley, and Wen Sun. qf: Provably optimal distributional rl for Ilm post-training, arXiv preprint arX1v:2500.20554, 2025.
Ruiwen Zhou, Minghuan Liu, Kan Ren, Xufang Luo, Weinan Zhang, and Dongsheng Li. Is risk-sensitive re- inforcement learning properly resolved? arXiv preprint arXiv:2307.00547, 2023.
13

---

Risk-Sensitive RL with Static Optimized Certainty Equivalents
Appendices
A. List of Notations
Table 3. List of notations used in the paper.
S,A
State and action spaces.
Н
Time horizon.
((S)
The set of distributions supported by set S.
Markov
Class of Markovian policies that act only based current state.
HD
Class of history-dependent policies.
sug HTD
Class of Markovian and history-dependent policies in the AugMDP.
aug
Qaig. Vaug
and value functions of in the ADP.
Qaig.
Vaug
Optimal Q and value functions in the AugMDP..
(T,
Run the policy π from an initial state ($1, b) in the AugMDP.
(TT)
The cumulative reward distribution of policy æ.
(CE,(()
Optimized certainty equivalent with utility for ((T) (see App. B for primer on OCE).
OCE
Optimal OCE of cumulative rewards by history policy, i.e. max OCE,(T).
(LB(A)
The risk lower bound round k for policy optimization algorithms (defined in Eq. (6)).
Vmax
Scale utility u defined as V/max max |u(c)].
B. Primer on Optimized Certainty Equivalents (OCE)
In section is short primer optimized certainty equivalents (OCE), which capture many important risk measures including conditional value-at-risk (CVaR) (Rockafellar and Uryasev, 2000), entropic risk (Föllmer and Schied, 201 I) and Markowitz's mean-variance (Markowitz, 1952). For utility function
R + [-00, the OCE of random variable X is defined as:
OCF,((X) == max + Elu [x(X - b)]}
In the paper, we focused on the case where X is the cumulative reward distribution of some policy æ, and the goal is to learn the policy that maximizes the OCE. While the OCE is well-defined for any utility function, there are common regularity conditions proposed by Ben-Tu and Teboulle (2007) that ensure the OCE is well-behaver These conditions are:
[R]] u proper meaning that its domain non-empty, iee,, dom (u) : {I E R u(() > -oo + 0:
[R2] u is closed meaning that its hypograph hyp(u) ((t,r) E A R:R: u(t)) is closed set;
[R3] concave meaning that its hypograph is convex;
[R4] u non-decreasing:
[R5] (0) = 0 and 1 E @ov()), where Ou(x:) = (g V2 E R ((()))-(()))/(=> =x) is the subgradient.
Ben-Tal and Teboulle (2007, Theorem 2.1) showed that, if u satisfies R1-R5, then OCE, enjoys the following properties:
[PI] Translation invariance: OC + c) OCE, (X) + e for constant c R:
[P2] Monotonicity: if X (w) < Y (w), Vw E Ω, then OCE,, (X) S OYE;
[P3] Concavity: for any X, Y E Loo A E [0, 1], we have OCE, (AX + (1 -))) AOCE, + (1 OCE,(Y);
[P4] Consistency: OCF,,(0) (0)
14

---

Risk-Sensitive RL with Static Optimized Certainty Equivalents
Translation invariance (PI) and consistency (P4) are intuitive since deterministic payoff of should have value of c. Monotonicity (P2) states that if X is dominated by Y, then the risk of X should be greater than the risk of Y. Concavity (P3) implies that- OCE,, is convex risk measure. However, we remark that these properties do not imply that OCE, is coherent risk measure (Artzner et al., 1999), which would require sub-additivity and positive homogeneity. Indeed, convexity is a relaxation of sub-addivitity and positive homogeneity, which are not always satisfied by OCF,, even if a satisfies RI-R5. For example, the entropic risk an OCE with an exponential utility function satisfying RI-R5, but it is not a coherent risk measure.
In Table below, we provide important examples of OCE, which includes (1) expectation, (2) entropic risk, (3) CVaR and (4) Markowitz's s mean-varianee Recall that CVaR and Entropic risk are defined by:
C'VaR, (X) == maxsER T - x)+
(X) == 1 log IE exp(
Risk Name
Parameter
Utility function a
V-max
Mean (EX)
None
u(t) =
1
Cond. Value-at-Risk (CVaR=(X))
T E (0, 1]
u(I) = - (-1)+
7-1
Entropic Risk (Entry(X))
B E (-o0, 0)
u(t) = 1 (cxp((3) -1)
1 (cxp(131) - 1)
3
Vecan-Vriannee (E.X- - c. Var(X))
<> 0
u(t) t - et2 if S 1/(2c) else
+
u(t) = 1/(4c)
Mean-CVaR, (x1EX + (1 K1) CV)R,(X))
K1 E [0,1]
u(t) (1(+) N2( where K2 T 11 15) 6-
K2
Table 4. Examples of OCE risk measures with their corresponding and Vimax
Table 4 also lists each OCE's Vimax which recall is defined as Vmax == maxce[-1.1] [u(c) and roughly measures the statistical hardness of learning OCE, relative to E (which has V. = 1). We remark that OCE is a Lipschitz risk measures (Liang and Luo, 2024; Chen et al., 2024) with Lipschitz constant Vimax and so V/max can also be interpreted in this way.
The first four rows of Table 4 are well-known risk measures and are known be OCEs. The final row Mean-CVaR, is lesser known example of OCE, but is perhaps more relevant in practice since it captures both the average and tail risks together. We now provide proof that Mean-CVaR, is an OCE with the piecewise linear utility.
Theorem B.1. Let 0 S K1 < 1 < R2 and consider the piece-wise linear utility:
UNIiNg (t) = K1 (t(+) kz(--))
where we denote (v)+ max 0). Then, with 1-K1
have that
62-
OCE (X) = KiEX + (1 - K1) CVaR, (X).
Proof. By Ben- Tal and Teboulle (2007, Example 2.3),
OCF (X) max (b + ki B( b) R22R((b X)+]}. bEj0.1]
Moreover, the optimal dual variable b* Ft1 k1)/ k1)), where Ft(t)= inf inf(x F(x) 2 f) is the quantile
function and F is the CDF of X. Expanding Eq. (9) and using the fact that (1)+ (-1)+ = we get
OCEw,yin (X) Ex + max {(1 - bE(0,1]
((1--K)0 k1)b - (M2 K2 E((b (b - x)+1}
=x + (1 k1) max (b
K2 K1
El(b X)+1}
bElU.1]
1 Ki
= + (1 x1) CVaR,
where 7 N2-Kj
1-81,
This completes the proof.
15

---

Risk-Sensitive RL with Static Optimized Certainty Equivalents
C. More Details on Experimental Setup
C.1. Network Architecture and Input Features
We parameterize both the augmented Q-values and the softmax policy using multilayer perceptrons (MLPs) with two hidden layers of dimension 64. For the policy network, we one-hot encode the budget by, before passing into the network. This transformation does introduce approximation error since rewards are discrete in the Markov Decision Process (MDP). We observed that when b; inputted directly real number, the training of the policy less stable and often diverged. In contrast, the Q-network demonstrated greater robustness to how by. is featurized, likely due the augmented value function being Lipschitz and monotonic in bj. Unlike the policy network, the Q-network receives by, as direct input without encoding. Finally, since the task is finite-horizon, we incorporate the time step h as part of the state representation, following Pardo et al. (2018).
C.2. Regularization
Log-barrier regularization played a crucial role in stabilizing and preventing the optimization from getting stuck due to vanishing gradients. Indeed in softmax policies, the gradients tend to vanish as the policy becomes more deterministic. To mitigate this issue, we applied a regularization weight of 0.1 which helped to prevent the policy from becoming too deterministic. We remark that policy gradients with log-barric barrier regularization also have theoretical guarantees Agarwal et al. (2021, Theorem 12), making this valid POALG for our PO algorithm.
C.3. Hyperparameter Settings
Component
Value/Description
Policy Network
Softmax policy with MLP with two hidden layers of dimension 64
Value Network
MLP with two hidden layers of dimension 64
Budget Encoding (Policy)
One-hot
Budget Encoding (Q-network)
Direct input
Optimizer
Adam with B1 0.9, 8n 0.999
Batch Size
256
Learning Rate
x 10-3
GAE A
0.95
PPO KL weight
0.1
Regularization Weight
0.1
Table 5. Hyperparameter settings used in our experiments.
16

---

Risk-Sensitive RL with Static Optimized Certainty Equivalents
D. Proofs for Optimistic Meta-Algorithm
In this section, we study three illustrative examples of optimistic oracles that satisfy Def. 3.1 in the AugMDP. In particular, all these oracles can be used with our meta- meta-algorithm Alg. 1 form an optimistic OCE algorithm with the regret/ PAC bounds in Thm. 3.2. The three oracles we consider are UCB-VI (Azar al., 2017), Rep-UCB (Uchara al., 2022) and GOLF (Jin al., 2021).
First, UCB-VI is a model-based algorithm based on optimistic value iteration with exploration bonuses and achieves minimax-optimal regret in tabular MDPs (Azar et al., 2017). Second, Rep-UCB is model-based algorithm based on elliptical exploration bonuses and achieves PAC bounds in low-rank MDPs (Uchara et al., 2022). While the AugMDP may initially seem more complex, since it no longer tabular or low-rank, the regret bounds of these algorithms actually easily transfers to the Mug when the underlying MDP (i.e., the MDP being augmented) tabular or low-rank. The intuition because the AugMDP does introduce any new unknowns the model, as the augmented transition and reward functions are known and deterministie, as highlighted in Sec. 2.1. Hence, the model that needs to be learned is the same in the original MDP and the AugMDP, and the prior regret bounds naturally translate to the AugMDP, which we formalize in the following subsections. In particular, we will see that prior works such as (Wang et al., 2023a; Zhao et al., 2024) have already implicitly proven that UCB-VI and Rep-UCB satisfies Def. 3.1 in the CVaR AugMDP.
The third optimistic oracle we consider GOLF, model-free algorithm based on version space optimism and can achieve regret bounds exogenous block MDPs (Xie et al., 2023). Unlike model-based algorithm, extending GOLF the AugMDP requires more care since the value functions being learned also takes in the augmented state input; that is, the value function class is more complex in the AugMDP. To handle this added complexity, posit a discreteness assumption in Assump. 3.5. Under this premise, we prove the previous GOLF analysis based on coverability can be extended to the AugMDP. Consequently, we derive the first OCE regret bounds in exogenous block MDPs (Efroni et al., 2022).
Finally, we conclude this section by showing how second-orden -rder bounds for the oracle can lead to tight and optimal regret for CVaR, in tabular MDPs, recovering the main result of (Wang et al., 2023a). In particular, we observe that the key idea of the complex argument of (Wang al., 2023a) is simply access an oracle with second-order regret. We believe this observation can lead to tighter RSRL bounds, especially since second-order bounds have recently been possible in much more general MDPs via distributional RL (Wang et al., 2024b; 2025a; 2024c).
17

---

Risk-Sensitive RL with Static Optimized Certainty Equivalents
Algorithm 3 Optimistic Oracle: UCB-VI (Azar et al., 2017)
1: Input: Number of rounds K, failure probability d.
2: for round & = 2, K do
3: Compute counts and empirical transition estimate,
H
No(5,a,8')
[ss an 8h41.) (s, (s,
h= ==1
Na((s,a88)
(s(s, 1 ak(s,a,s',, Pa(s' s,a)
N)(
s'ES
4: For all E 8, E [0, 1), set (H+,,K(s, u(-b).
5: for h = H, H -,..... do
6: For all s, s,
log (SSHAAK//))
a, = Er, R(sa)) ( +1
(a(s,a)
(s, arg max (s, b)) = min (n, b, Ti b)), Vmnx]
a
7:
end for
8:
Output optimistic value function (
9: Receive adversarial bg-
10: Collect [Sh,,e dh,es Th, (h.))) Ieem by executing x starting from (s1, by) in AugMDP.
11:
end for
D.1. Example 1: UCB-VI
UCB-VI (Azar et al., 2017) is a model-based algorithm for tabular MDPs based on value iteration with exploration bonuses. Alg. formalizes the UCB-VI algorithm the AugMDP. The following theorem recovers the results from Wang et al. (2023a, Theorem 5.2), who focused on the more restricted CVaR RL setting.
Theorem D.I. For any E (0, 1). running Alg. enjoys the following w.p. 8:
1. (Optimism) (11, b1) Vaug (81, b1) for all &s E [K],01 [0, 1];
2. (Regret) The regret in the AugMDP is at most,
E (e) - vant (51, bu) (VSAHK S2 AH)).
where Ō()) ignores terms logarithmic S, A, H, K.
Proof Sketch. Thm. D.1 can be proved by following the same argument in (Wang et al., 2023a, Appendix G.3), except that the CVaR utility - min(t, f, 0) is replaced by any generic OCE utility u. particular, optimism ensured by Lemma G.3 and the Equation Bon The regret bound is ensured by the proof of Theorem 5.2 on Page 35, Thus, by applying the argument in (Wang et al., 2023a), we can show that UCB-VI satisfies the oracle conditions in Def.3.1.
Therefore, Thm. D.1 shows that UCB-VI satisfies the oracle conditions Def. 3.1 in the AugMDP with E 0 and Regom (K) S (O(SSAH log(1/5) + 8 At)).
18

---

Risk-Sensitive RL with Static Optimized Certainty Equivalents
Algorithm 4 Optimistic Oracle: Rep-UCB (Uehara et al., 2022)
Input: No. episodes K, Model Classes (#, T). 2: Initialize D (0) D/ 0 for all h E [H].
3: for round k = 1, 2,
do 4: Learn the model via maximum likelihood estimation (MLE): for all h E [H]]
(k) (K) Ph 1h
arg max NEU,NET
Σ
log ((5n, an.)) p(
8,0,8' e'EE DDD(-1)
5: Define the empirical covariance MA, E St tb (s,a)((p)) (8) (s, a)) Axd.
6: Define the bonus, (8, a) = min((xx 100h (k)
(s, a) a) 2) if < H. Otherwise biI = 0.
7: Let (n, b, a) denote quality function of the AugMDP with reward raug(s, b, + (, a) and transitions
Pk (s s.a) = ( a) ui (s)). Let (), max (s, b, a) and Th arg ma Qn.u(s,b,a)
This can be achieved via a planning oracle (Zhao et al., 2024).
8: Output optimistic value function (s,,))
9: Receive adversarial by.
10: For each h E [H], execute Th starting from (s1, by) in AugMDP until sh, by and take two uniform actions. That is, Uni,(AA, observe 8h+1 Ph (sh, an), and take da+1 Un),(A), observe 8h42 Ph+1 11 Then, add to datasets: (ha) h + (k-1) U {(h,, an sh+1] and ((k) end for
h+1 + (kk)
h+1 U {(8h+1, A4t1 $1+2))
11:
D.2. Example 2: Rep-UCB
Rep-UCB (Uchara et al., 2022) is a model-based algorithm for low-rank MDPs based on elliptical bonuses. We first recall the definition of low-rank MDP (Agarwal et al., 2020).
Definition D.2 (Low-Rank MDP). An MDP is has rank d if its transitions have a low-rank decomposition (s 8,a) = (8,s,, a) TT (s') where (s, a). 11 (s") E Rdd are unknown features that satisfy sups,a (8, ())22 S and (s()(d))))))))1 < lo v for all g:
R.
Rep-UCB utilizes a model class (Ø, T) to learn the low-rank transition (s, (7) Assumption D.3 (Realizability). + E + and μj E Y for all [H].
Rep-UCB as an oracle in the AugMDP is presented in Alg. 4. Our theory recovers the results of Zhao et al. (2024), who focused on the more restricted CVaR setting.
Theorem D.4. Under Def. D.2 and Assump. D.3. any 8 E (0. Alg. 4 enjoys the following w.p. 1-
1. (Optimism) For all k E [K] and by. we have (s, b1) (1,)(s,,b)) s O(H /AL/k) where log( @ (H|THK//8)
2. (Total sub-optimality gap)
ΣK (1, - Vatg' (81, (s)) S O(Viax Ad Ad& VKL)).
Proof Sketch. Thm. D.4 can be proved by following the same argument in Zhao et al. (2024), except that the CVaR utility -'' min(t 0) replaced by any generic OCE utility In particular, optimism is ensured by Lemma C.2. The total sub-optimality gap bound was proven in Lemma C.I, where any 7 -- Rt)+ can be replaced by u(R - t). Thus. by applying the argument in (Zhao et al., 2024), we show that Rep-UCB satisfies the oracle conditions in Def. 3.1.
Therefore, Thm. D.4 shows that Rep-UCB satisfies the oracle conditions Def. 3.1 in the AugMDP with Regop (K) S 3 Ad A& VTT) and Ex & opt & OHHTTT)
19

---

Risk-Sensitive RL with Static Optimized Certainty Equivalents
Algorithm 5 Optimistic Oracle: GOLF (Jin et al., 2021)
1: Input: No. rounds K, Function class F = Fi
Fr, threshold B.
2: Initialize (/ = for all h, and F=()) = F.
3: for round & 1, 2, ................................ K do
4: For each b E [o, IJ. define Qu(;;b)= = arg je max (1
5: Output optimistic value functions (&, b; bi) = m (u(s,b,abbl
6: Receive adversarial by-
7: Define policy T (a 8, arg aa (s. b,b)).
8: Execute x from by in the AugMDP and collect trajectory (5% b/
oh , (EEHH
(k) (8)
9: Update dataset // = (D(h-1) U {(sh b (k), (k) (6) (()))) Compute confidence set:
(1))
aah) ih Sh41
F(M) - {FEFF Cf (fh, (fr fht1) S minger, C (g. fh+1) + +, E [m1] (1) (1)
where c/ (g.8") (9
(0) 0 aa)) -rlh m f' (5 (41: a))a
11: end for D.3. Example 3: GOLF
GOLF (Jin al., 2021) is a model-free algorithm that establishes optimism by optimizing over version space of candidate Q-functions. In this section, we show that GOLF's regret in the AugMDP can be bounded under discreteness premise on the cumulative rewards (cf. Assump. 3.5).
We consider a function class F Fi x .... x FF with elements / (fi,.... SH) F such that fn. S [0. 1] x A + [-Vamax | As convention, we set (s, b, a) = =(-b).
GOLF constructs the version space by selecting subset of such that the TD-error small for all h. This is formalized in Alg. with the squared TD-error. To ensure the regression at each step can succeed, GOLF requires Bellman completeness (Jin al., 2021; Xie et al., 2023). To state Bellman completeness, we first define the Bellman optimality operator in the AugMDP: for function f S [0, 1) x A + R and any h H:
d'EA Tatul f(h,, bn, an) = E Ph on) mmax f(hh+1, by - rr,, at)d)))
Taig H
fH+1(8H by, an) = Er Ro (o [u(ru bb)]]-
Assumption D.5 (AugMDP Bellman Completeness). Taug fn+1 Fn for all Sa+1 E F h E [H].
To prove regret bounds for exogenous block MDPs, we recall the definition of coverability from Xie al. (2023). Coverability is a complexity measure that captures the minimum possible concentrability coefficient in the MDP:
Cov == min (A(Sx Thaanov NeE
di
where Markav is the set of policies in the original MDP. We extend this notion to the AugMDP:
CoVaug == minp,ea((s((01)xx) MeX
d
We now state the AugMDP regret bound for GOLE Theorem D.6. Under Assump. D.5, for any d E (0, 1), running Alg. 5 with 3 O(log(KH)]T) enjoys the following w.p.1 5:
1. (Optimism) (81, b1; 2 Vatg (81, for all l E [K], by E [0, 1]:
20

---

Risk-Sensitive RL with Static Optimized Certainty Equivalents
2. (Regret bound)
EkS (1, bu; 2 (81, bR) S (V. H CoVaug 3K ())
Proof Sketch. Thm. D.6 is direct consequence of Jin et al. (2021); Xie et al. (2023), since all that we have done is rewritten everything (algorithms, assumptions and theorems) in the AugMDP notation. For example, optimism is proved by Jin et al. (2021, Section 4.2, Page 9). Moreover, the regret bound is proved by Xie et al. (2023, Theorem 1).
Therefore, Thm. D.6 shows that GOLF satisfies the oracle conditions Def. 3.1 in the AugMDP with & and Rogopt ( - (H /CVaagg Iog(K))
The main question now whether we can bound CoVaug by the original coverability Cov, which we know is bounded for low-rank MDPs (Def. D.2) and exogenous block MDPs (Def. 3.3). We now show that if cumulative rewards live discrete set B (cf. Assump. 3.5), we can bound CoVaug [B] Cov by simple importance sampling argument. Lemma D.7. Under Assump. 3.5, we have
CoVaug S |8|Cov.
Proof.
CoVaug
[
E. b,,, by Jo.h (s,b.a)
IA3
maX Es, (0..eEx(00.11)44 max max E|0.1] dh bibb (s,
(184)
maX E Ex.baeSx(0..14 max (8,
[ Σ E. (A E di (s,
B ma E Ex eaxael di (s, a)
B C)V,,
where is by coverability's equivalence cumulative reachability (Xie et al., 2023, Lemma 3); (ii) by d bs, s da.bi (s, a) since B is discrete; (iii) is since т. b2 be viewed policy in the original MDP; (iv) is by the Markov optimality theorem for risk-neutral RL: mаxхетнн di (s',a'') is equivalent to standard RL with the reward rh (s, a) TI [[(s.a) a) (s', a')] and zero otherwise, and we know that Markovian policies are optimal for risk-neutral RL; (v) is by discreteness of to collect common terms; and (vi) is again by Xie et al. (2023, Lemma 3) in the original MDP.
We can now state our OCE regret guarantees for low-rank MDPs and exogenous block MDPs. Note these are the first risk-sensitive regret bounds for these rich-observation MDPs. Theorem D.8. In exogenous block MDP (Def. 3.3), under Assump. 3.5, have
Covaug I | | 2 [[A]
Therefore, under Assump. D.5, running Alg. with the GOLF oracle (cf. Alg. 5) enjoys the regret bound:
Σ K 1= OCE, OCE, bx) O(Vimax H B TM A|
log(K)).
Proof. To prove the first statement, recall that Cov < [A) as was proved by Xie et al. (2023, Proposition 5). Thus, Lemma D.7 implics that CoVaug < |B] ze| [|. To prove the second statement, simply combine our meta-algorithm guarantee in Thm. 3.2 with the GOLF oracle guarantee Thm. D.6.
Theorem D.9. In a low-rank MDP with rank (Def. D.2), under Assump. 3.5, we have
Covaug S |B[d]AA).
Therefore, under Assump. D.5, running Alg. 1 with the GOLF oracle (ef. Alg. 5) enjoys the regret bound:
Σ OCE; - OCE,, ( Tra) < o V.max H / A|KK log(K)) (Kdg)))))oo(())
21

---

Risk-Sensitive RL with Static Optimized Certainty Equivalents
Proof. To prove the first statement, recall that Cov v d| as was proved by Huang al. (2023, Proposition 3). Thus, Lemma D.7 implies that CoVaug [B] .d] To prove the second statement, simply combine our meta-algorithm guarantee in Thm. 3.2 with the GOLF oracle guarantee in Thm. D.6.
Note the above the first risk-sensitive regret bound for low-rank MDPs. The previous Rep-UCB result ((Zhao et al., 2024) or Thm. D.4) technically not a regret bound since the data collection policy takes uniform exploratory actions, i.e. Rep-UCB can only yield PAC bounds.
D.4. Tight bounds for CVaR via an oracle with second-order regret
Recall that Thm. 3.2 combined with UCB-VI (Thm. D.I) gave an OCE regret bound of O(Vi /SAHK). Specializing to CVaR, have L----VSSAK A weakness in this bound is that it is not tight in т, since the minimax-optimal rate for CVaR RL actually scales with 1/2 (Wang et al., 2023a, Theorem 3.1).
In this section, we address this issue by assuming that the oracle has a second-order regret. Second-orde regret, a.k.a. crriance-dependent regret, is an instance-dependent regret bound that scales with the variance of returns throughout K episodes, and is strictly stronger than the standard v K minimax-oppiimll regret. Specifically, an oracle with second-order regret takes the following form.
Assumption D.10 (Second-Order Oracle). Regon (K) /C, Ex Var(Z(rh,,b)) + C2 for constants C1, C2-
For example, optimistic model-based algorithms such as UCB-VI with Bernstein bonus (Azar al., 2017; Zanette and Brunskill, 2019) can achieve second-order bounds in tabular MDPs. Indeed, this property of UCB-VI used prove the tight - 1/22 rate for CVaR RL in Wang et al. (2023a); following result generalizes this argument. Recently, distributional RL has been used to also prove second-order bounds in much more general MDPs, such as low-rank MDPs (Wang et al., 2024b; 2025a).
We also assume a continuous returns assumption of (Wang et al., 2023a).
Assumption D.11 (Continuously Distributed Returns). For all policies HHD, the cumulative reward Z(T) is continuously distributed with density lower-bounded by Pmin-
The following result has sharp -1/2 dependence and generalizes the minimax-optimal results of (Wang et al., 2023a).
Theorem D.12 (e-2re-regret for CVaR). Under Assumps. D.10 and D.1 Alg. I enjoys
RegovaR, S 45 1/2 VCJK + (C + C2).
We note that the density lower bound Pmin only scales a lower-order term, which is independent of K. The proof uses the fact that the AugMDP return variance is at most under the true initial budget bj arg max Var (s1, b)). Then, under Assump. D.11, the approximation (bg bg)² can be related to Regope which leads self-bounding inequality that solves to Regon (K) < VC,KT + 2C1pmi + 2C2.. Compared to Wang et al. (2023a, Theorem 5.5), our result is more general (applies beyond tabular MDPs) and Thm. D.12 also sharpens lower-order terms (Pmin is not multiplied with K1/4),
Proof. First, we want show: under continuous returns (Assump. D.11), we have
Regom (K) < 22/C/ C,KT 2C 2C2.
(10)
Recall for CVaR, the normalized reward in the AugMDP is precisely precisely (br - 2( ,,, (x))) Let bj denote the true
22

---

Risk-Sensitive RL with Static Optimized Certainty Equivalents
7-quantile of ( (n).
Regopt (K)
(
/G VGE, En Var(b; 7(x bk)+) + Va Var((b: 7(Th,bb)) bb))+ (bg 2( bk))+) + C2
VGKT+ VO Var( Z(* bx)) (bg - b())+) + C2
(1)
VGKK++ / GE b2)2 + C₂
(1))
VCTT+ + 20 10 Regop (K) C2
S VCCKT Ciemin + Regop (K) + C2.
(AM-GM)
(i) holds since / Var(X +Y) = VVr((X) + /Var(Y) for any random variables X, Y. (ii) holds since (ar( I E[x 2 0]] & Pr(X 0) for any bounded X [-1,1] and bú is the true 7-quantile. (iii) holds since (b. Z (l4 7x) S 1bx bg almost surely. (iv) holds by (Wang al., 2023a, Lemma G.10): states that under Assump. D.11,
the choice of by ensures:
(6x b2) S 2pmia (Vi, B&) V
Rearranging Regopt (K) implies the desired Eq. (10). Therefore, we can conclude the proof applying Thm. 3.2 and using Vmmax -- and Eq. (10):
Regoce (k) 4/- 4C + C2).
E. Proofs for Policy Optimization Meta-Algorithm
We begin by proving stronger global convergence guarantee than the one stated in the main paper. Theorem E.1 (Strong Global Convergence). Under Assump. 3.5 and Def. 4.1, we have
Σk, -RLB()))))) < |8| V Regpo (K).
Proof.
Σ OCE; SCM-RIIN (R)B( Σk=1 (bi + (5i maxxe(o.11 b ' (s1, b)}
Σk Vaūg (81, bi) Vaai (s1
< Σ E |B] [ EsEr
(Vag((s), b) Vaug ((1, b)
$ |B] Regro(K)
where the last step uses the global convergence premise of POALG in the AugMDP.
This is stronger than the global convergence in the main paper (cf. Thm. 4.2), since the RLB approximately lower bounds OCEg (xx Ba)), as we prove next. Therefore, Thm. 4.2 direct consequence of Thm. E. and the following RLB lemma (Eq. (7)).
Lemma 4.3 (RLB). The (k) approximately lower bounds the true OCE of nh with initial budget by:
(I.((*) - OCE, ( bx) S e
(7)
Moreover, the lower bound is tight on average:
Σx OT (h)) - (R)
< V mmax Regro (K).
23

---

Risk-Sensitive RL with Static Optimized Certainty Equivalents
Proof. First, we prove Eq. (7). By importance sampling and the value estimate guarantee of Def. 4.1: for all bj E B, have |VT" (11,b1) Vi (s1, & |B =: E Thus,
OCE,(T* bu) mb + (l bk) 6]]}
BEB
2 fo (lu(Z(TT 64) bb
(6k E B, by Eq. (5))
Chx Vaug i (s1, dk))
(def. of V**)
- fox + Vir" (s1, bk]} - Ek
= max + Vir" b1), - E/
(def. of by. by Eq. (5))
biE8
(1))
max (b) + Vaug (81, b1)} - 22's
b
= (LB -2E'
(def. of RLB, by Eq. (6))
where the inequalities (i,ii) are due to the value estimate guarantee. This finishes the proof of Eq. (7).
To prove the second statement, simply apply the stronger global convergence result Thm. E.1 with the fact that OCE (T bx)) < OCE,
Theorem 4.4 (Local Improvement). Under Assump. 3.5 and assuming POALG satisfies the approximate improvement criterion of Def. 4.1, running Alg. ensures that:
wk E [K] RLB((+1) 2 (LB -1B]=)
Proof. Let 6% arg max {b + Vaug
(s1. b)}. Then,
RLB - -RLB(+11) {bj + Vaug .1 (s), b1) - max Vaūg vat ((1, 6)}
Vaig x+1 (s1 bg)
Vang (s1, bt)
[8] Eee ( (Vaug" (s1, b)
Vaug
+1
(s1. b))
where the last step uses local improvement premise of POALG in the AugMDP.
E.1. Primer on Natural Policy Gradient in Finite-Horizon MDPs
In this section, we provide primer on natural policy gradient (NPG) for finite-horizon MDPs and its guarantees, supple- menting the case study (Sec. 4.1) of the main paper. Our analysis is based on the infinite-horizon analysis of Agarwal et al. (2021). Let dj denote an fixed initial state distribution. For policy let (7(s), an) E,, [rx Th+1 +... + TH 8h an denote the Q-function, V (8a) = Beg [Q% (8x, ax)] denote the value function, and A a) 27 (s,a)) V (s) denote the advantage function.
We consider policies T² [.ff....,.. parameterized by weight vectors = (f2....,0) 0n) where 8₁ E Rm. Initialize 000) for all h [H] Consider the generic update rule for is 1,,,..., K:
for all h,
k+ (++1)
k/4² + +
h
(k) where w/ E R. have fo-norm at most W. Let n² denote the policy parameterized by g(k), Then, we have the following lemma that bounds the sub-optimality the update rule.
Lemma E.2. Suppose the log- -ropobbbayylity parameterization 8n + log To, (a | s) is 3-smooth for all h, s, Then, setting
Alog(A) 1 3KW2. we have
EKyE Exinds (V]((1)) VT" (s1)) HW HW / log(A) + Σn.k erTh,k.
where errh,k == Bejndy 1 (Ap" (sn, un) - wy -w (k)
Vo, log π. go(e) (an (an 8n)]-
24

---

Risk-Sensitive RL with Static Optimized Certainty Equivalents
Proof. First, notice that the smoothness assumption implies that for all hi 8,8,0,
log A
(a (a log o. s) 2 (0/++1) 0 Vo, log oa s) _110
++1
s)
/
11
2 mw (R). Vo, log Tg (a 8) wr2
(by update rule)
Rearranging, we have
wh
(k)
Va, log T gg (8) S n log(Th
(t (al 6)/m/((a 8)) + AnW?
(11)
Then, we can bound the sub-optimality at the k-th round by:
Egy Edy (s1) VT (s1))
= - Boindh n- [A% (sk: an)
(by performance difference lemma)
En orTh,k + BBy rdy . [wr Vo, log a o0 (as (an sh)l
En CrT +1 "B Eg, bi [log( a ++1
( (an a (x))) PnWa
(by Eq. (11))
En errh, +n "B ( || (sn)) DxL (x)(((((s)) Th * (sn)) + anW?
where DKL is the KL-divergence. Finally, summing over i implies the final result by telescoping:
Σk ENg dd (V) Vi (s1)
+ +1 En Borndi .r (TA(O))(ON)) ll m)((N)) (T)()( || (*x))) k erri.k @nHW2K K
s BnHW2 + +1 log(A) (A) En, eITh,k
(r(() is uniform)
2 ())2+ En, erth,k
(choice of n))
This finishes the proof.
(k) natural idea is set ih to minimize the erta, error terms, which exactly motivates the NPG update. Specifically, the (idealized) NPG update vector is defined as:
(k) arg min wlllsw Ln (w; (w; ((t)), dh
where L, (wp; 8¹, vn) == Es,,,, ((A7 (sn, an) Wp. log Tey (ax, [s,))
for Op E d and in A(S A). In other words, the idealized NPG update vector minimizes the squared error term while having Euclidean norm most W. Since the mean is unknown, we approximate the above using samples. Thus, the actual NPG update consider minimizes the empirical error
Wh (k) arg min (w; (n,
(12)
where La (wii; 0', (sn, NE)) N EA (Sn.5,an.)) wh V Vlog Tep (an.i sn,,))² and 8h,i anei dx N i.i.d. samples from roll-outs.
We now bound the sub-optimality of the NPG update. We define two sources of error. First, there is the statistical estimation error from using the empirical loss L, instead of the true L2, This error is expected to converge at O(1/vN) rate or faster, where is the number of samples per round. Second, there a transfer / approximation error that measures the performance of the best population vector ((k) under the optimal policy's visitations d,." This quantity is small if the training policies for data collection cover the traces of the optimal policy n². The first estimation error is also measured
under the distribution induced by x*, but can be handled by using the relative condition number, which is weaker measure of coverage than fox density ratio bounds.
The following results are based on the
MDP analysis Agarwal al. (2021, Section 6.3).
25

---

Risk-Sensitive RL with Static Optimized Certainty Equivalents
Assumption E.3. The update vectors generated by NPG satisfy for all ls E [K] h E [M]:
1. (Excess risk) The statistical estimation error is bounded by Estar:
(k), L g(h), , L(wi ( dih S Esaa-
2. (Coverage) The relative condition number of the covariance under di. and dz. is bounded by
W En.kk.
sup wERd w Ep,k,
S Ki
where Enh,k,=' EE, Vo, log (as. (V), log (an sk))
3. (Transfer Error) Assume the transfer error is bounded by Ebins:
(k (00) df S Ebias.
Theorem E.4 (Agnostic NPG). Under Assump. E.3, running the NPG update in Eq. (12) enjoys:
Σ K
Es (Vi((s)) V/" (s1) s HW 28K log(A) HK Ebias + HK / KE stat
This is finite-horizon analog of Agarwal et al. (2021, Theorem 6.2), where their effective horizon with the horizon H.
is replaced
Proof. The proof focuses decomposing the error term in Lemma E.2.
e = Es xx [AR (sh, an) - wh Vo, log g0 (ap sh)l
(k).
Egi [A (Shy an) Wh
(k)
Van log क o (ap sn)l (ir(t)
(+)) Begndi or (V log Tap (an sn)
est.error
approz.error error
Let dz = dT be the h-th visitation distribution of rolling in nt from dj. The approximation error can be handled by:
E Exrdd [A (sh, an) - w/) Ve, log Top (an ss,]
V E B [[Ag" (sh, an) w0(h) (k) Vo, log Top (an sn)) v Ln (17% 00K)), (()),d1).
The estimation error can be handled by:
(w (k)
w/ (k)) E. Exi [o,, log
(ap sn)l s 11/0 w/ I.
Then by definition of the relative condition number Kb,A = || (EN,,, - -1/25 (Ep -1/2 2/ we have
(k) wh 11 S / Vin.alll (1())) -whh ||
(1)
=Vens(Lnlu) (8), 0a0), drth) La (n(h/) B(k)) dr")))
Therefore, have shown that
eTTH, S V Ln(ww)))
(k), ;00k), (0())dd)) + v Ken (k), 0(K), d7")) - La (a( ; (((k),dT') drg"))
/ Ebius / stai
which concludes the proof.
26


Reviews:
[{"review_id": "Dp4F0QQxcb", "reviewer": "Reviewer_1jGh", "summary": "This paper studies risk-sensitive reinforcement learning (RSRL) with the goal of learning a history-dependent policy that optimizes Optimized Certainty Equivalents (OCE) risk measures of cumulative rewards. The authors propose two meta-algorithms, one based on optimism and another on policy gradients, that reduce the RSRL problem to risk-neutral RL in an augmented Markov Decision Process (MDP). Theoretical guarantees, including regret bounds and convergence properties, are established, and empirical results demonstrate the effectiveness of the proposed methods in learning optimal history-dependent policies.", "questions": "", "limitations": "", "rating": 4, "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": "Dear Reviewer 1jGh,\n\nThanks very much for providing helpful feedback. We truly appreciate the time and effort that have been invested in providing constructive comments. Please find our responses below.\n\n**Reviewer: the constant $V^{\\max}_u$ is not defined formally**\n\n**Authors' reply:** We kindly refer the reviewer to line 130 where $V^{\\max}_u$ is defined. We will make sure to highlight this definition in the revision with examples and connection to Lipschitz risk measure (see next reply).\n\n**Reviewer: My main concern is that the author has not referenced the studies on the Lipschitz risk measure in [1, 2]. Although not previously discussed in related works, I believe that the OCE is encompassed within the Lipschitz risk measure. The factor $V^{\\max}_u$ closely resembles the Lipschitz constant described in [1, 2], which might give a formal way to determine this factor. Since [2] has already proposed an optimism - based algorithm grounded in distribution learning for the Lipschitz risk, I suggest that the author offer a comprehensive comparison with [2]. This would help to clearly elucidate the novelty of the first contribution of this paper.**\n\n**Authors' reply:** Thanks very much for pointing out Lipschitz risk measures. You're right that they indeed encompass the OCE with Lipschitz constant at most $V^{\\max}_u$ and we'll cite and discuss this as another way to interpret $V^{\\max}_u$. Our work is distinguished from prior Lipschitz risk RL [1,2] as follows:\n* [1] studies RL with dynamic risk objective (a.k.a. iterated risk) $\\rho(r_1+\\rho(r_2+\\rho(r_3+...)))$ which measures per-step risk and is different from our static risk objective $\\rho(r_1+r_2+r_3+...)$ which measures trajectory-wise risk. Both objectives are important and we discuss dynamic risks in Lines 110-128 of Related Works, to which we'll add a citation to [1]. \n* [2] derives regret bounds for static Lipschitz risks under function approximation which is more related to our setting. However, a key technical assumption made in [2] is bounded Bellman eluder dimension or witness rank, which are insufficient to capture the challenging exogenous block MDP setting. Indeed, the Bellman eluder dimension can grow with the size of the exogenous state space which is exponentially large or infinite (Xie et al. 2023). In contrast, we employ a coverability argument in the augmented MDP to obtain the first PAC bound for exogenous block MDP in risk-sensitive RL. Thus, our first contribution is distinct from [2] since our framework can deal with the challenging exogenous block MDP while [2] cannot. Moreover, our work includes other contributions such as studying policy gradient methods that are complementary to optimistic algorithms.\n\n**Reviewer: I recommend that the authors delve deeper into the computational efficiency of the proposed algorithms. For instance, they could explore and discuss what the major challenges are in developing a computationally and statistically efficient algorithm for OCE RL.**\n\n**Authors' reply:** Thanks for this suggestion, we'll certainly add more discussion in the revision. In short, our work shows that the computational and statistical complexity of OCE RL algorithms can largely be reduced to standard risk-neutral RL in the AugMDP. In terms of computation, the main costs come from 1) optimizing over $b$, which is efficient under reward discretization, and 2) querying the underlying risk-neutral RL oracle. In terms of sample efficiency, our main theorems (Thm 3.2 & 4.2) ensure that the OCE regret is bounded by the underlying oracle's regret up to constant factors. Thus, in both cases, the major challenge is devising a risk-neutral oracle that is efficient within the AugMDP. We will make sure to incorporate these discussions in the revision.\n\n**Reviewer: Given that discretizing the total reward in Risk-Sensitive Reinforcement Learning (RSRL) is a prevalent technique, as demonstrated in [3, 4], discretization appears to be a rational approach to address the discrete reward assumption (Assump. 3.5). Will this method works in OCE RL?**\n\n**Authors' reply:** Thanks for this question! Yes, discretizing rewards as in [3, 4] can indeed by used to address the discrete reward assumption (Assump 3.5), at the cost of a slower regret rate. Specifically, using a discretization width of $\\epsilon$ introduces additional regret of $O(K\\epsilon)$ and creates $|\\mathcal{B}|=1/\\epsilon$ atoms. Thus, our regret bound in Thm 3.6 would become $O(\\sqrt{K/\\epsilon} + K\\epsilon)$. The $\\epsilon$ which minimizes this is $\\epsilon = \\Theta(1/K^{1/3})$, which leads to a regret bound of $O(K^{2/3})$ which is sub-linear and meaningful. In other words, we can remove Assump 3.5 by discretizing rewards with bin width of $1/K^{1/3}$, and our regret bound in Thm 3.6 becomes $O(V^{\\max}_uHK^{2/3} \\sqrt{ Z^{en}A\\log(|\\mathcal{F}|/\\delta) })$. We'll make sure to discuss this in the revision.\n\nPlease let us know if you have any other questions!", "claims_and_evidence": "The claims are supported by rigorous mathematical proofs and experiments.", "methods_and_evaluation_criteria": "The methods and evaluation criteria are appropriate.", "theoretical_claims": "I have checked the correctness of the main theoretical claims. The proofs appear to be logically sound and technically correct. However, the constant $V_{\\max}^u$ is not defined formally, which is confusing.", "experimental_designs_or_analyses": "I have checked the soundness of the experimental design.", "relation_to_broader_scientific_literature": "n/a", "essential_references_not_discussed": "See weakness part.", "other_strengths_and_weaknesses": "### Strength\nStrengths include the originality of the reductions approach to OCE RL, the significance of providing the first risk-sensitive bounds for exogenous block MDPs, and the clarity of the theoretical and empirical results.\n\n### Weakness\nMy main concern is that the author has not referenced the studies on the Lipschitz risk measure in [1, 2]. Although not previously discussed in related works, I believe that the OCE is encompassed within the Lipschitz risk measure. The factor $V_{\\max}^u$ closely resembles the Lipschitz constant described in [1, 2], which might give a formal way to determine this factor. Since [2] has already proposed an optimism - based algorithm grounded in distribution learning for the Lipschitz risk, I suggest that the author offer a comprehensive comparison with [2]. This would help to clearly elucidate the novelty of the first contribution of this paper.\n\n[1] Liang, H., & Luo, Z. (2024, April). Regret bounds for risk-sensitive reinforcement learning with lipschitz dynamic risk measures. In International Conference on Artificial Intelligence and Statistics (pp. 1774-1782). PMLR.\n\n[2] Chen, Y., Zhang, X., Wang, S., & Huang, L. (2024, July). Provable Risk-Sensitive Distributional Reinforcement Learning with General Function Approximation. In International Conference on Machine Learning (pp. 7748-7791). PMLR.", "other_comments_or_suggestions": "I recommend that the authors delve deeper into the computational efficiency of the proposed algorithms. For instance, they could explore and discuss what the major challenges are in developing a computationally and statistically efficient algorithm for OCE RL.\n\n\nIf my concerns and comments are adequately addressed, I will consider raising my score.", "questions_for_authors": "Given that discretizing the total reward in Risk-Sensitive Reinforcement Learning (RSRL) is a prevalent technique, as demonstrated in [3, 4], discretization appears to be a rational approach to address the discrete reward assumption (Assump. 3.5). Will this method works in OCE RL?\n\n[3] Bastani, O., Ma, J. Y., Shen, E., & Xu, W. (2022). Regret bounds for risk-sensitive reinforcement learning. Advances in Neural Information Processing Systems, 35, 36259-36269.\n\n[4] Chen, Y., Du, Y., Hu, P., Wang, S., Wu, D., & Huang, L. Provably Efficient Iterated CVaR Reinforcement Learning with Function Approximation and Human Feedback. In The Twelfth International Conference on Learning Representations.", "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": "pK4o7L7wUV", "reviewer": "Reviewer_5fhe", "summary": "**I am very unfamiliar with this topic. I will maintain the lowest confidence level.**\n\nThis paper develops a study on risk-sensitive RL, which is formulated through OCE. Two meta algorithms are proposed with further analysis.", "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": "Dear Reviewer 5fhe,\n\nThanks for providing your helpful feedback. We truly appreciate the time and effort that have been invested in providing constructive comments. Please find our responses below.\n\n**Reviewer: The paper could benefit from more explanation. For example, in eq (1) defining OCE, it is unclear to me what this definition means. Some examples could help.**\n\n**Authors' reply:** Thanks for the suggestion. Eq (1) is the risk-sensitive RL objective defined using the static OCE risk measure and is the key objective we aim to optimize in the paper. Right after Eq (1), we provide a few examples of OCE risk measures, such as CVaR when u is the hinge utility and Markowitz's mean-variance when u is the quadratic utility. We will elaborate more on these examples in the revision by moving some content from Appendix B to the main text.\n\n**Reviewer: In def 3.1, an oracle is introduced. Is this oracle used in later algorithm designs? And how do you implement it?**\n\n**Authors' reply:** Thanks for the question! Yes, the optimistic oracle in Def 3.1 is used in the meta-algorithm Alg 1, and similarly the policy gradient oracle in Def 4.1 is used in the meta-algorithm Alg 2. In our paper, we discuss several examples of how to implement these oracles for different settings. For example, for the optimistic oracle in Def 3.1, we discuss three ways to implement it using (1) UCB-VI, (2) Rep-UCB and (3) GOLF. Moreover, for our policy gradient oracle in Def 4.1, we discuss natural policy gradients (NPG) as an example instantiation. By employing different oracles, we are able to derive guarantees in several types of MDPs, e.g. UCB-VI is used in tabular MDPs, Rep-UCB in low-rank MDPs, GOLF in exogenous block MDPs, NPG in MDPs with good initial state distribution, where the latter two are novel to risk-sensitive RL. If you have any further questions about how these oracles are implemented, we would be happy to answer them!", "claims_and_evidence": "The paper propose an augmented MDP for the OCE problem, which bypasses the challenges. The theorems indeed support the claims that the augmentations can help solve OCE.", "methods_and_evaluation_criteria": "The experiments seem to only contain a simple MDP, which could benefit from more evaluations.", "theoretical_claims": "I checked the proof of THM 2.1. Although the proof is not very easy to follow, it seems to be correct.", "experimental_designs_or_analyses": "The experiment only contains one simple MDP, although neural policies and advanced algorithms like PPO are considered.", "relation_to_broader_scientific_literature": "n/a", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "The paper could benefit from more explanation. For example, in eq (1) defining OCE, it is unclear to me what this definition means. Some examples could help. \n\nIn def 3.1, an oracle is introduced. Is this oracle used in later algorithm designs? And how do you implement it?", "other_comments_or_suggestions": "n/a", "questions_for_authors": "See above.", "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": "4QzwxIp8NM", "reviewer": "Reviewer_ZPJ1", "summary": "This work studies risk-sensitive reinforcement learning, where the target is to maximize $\\max_{\\pi} \\max_{b} \\\\{b+E_{\\pi}[u(\\sum_{h=1}^H r_h - b)]\\\\}$ where $u$ is some utility function. For this problem, the authors prove that by augmentation, there exists a Markovian policy which reaches the optimality. Based on UCB-VI, the authors designed an algorithm with provable regret bound. Then authors combine their formulation with several other frameworks to generalize the convergence rate.", "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": "Dear Reviewer ZPJ1,\n\nThanks very much for providing helpful feedback. We truly appreciate the time and effort that have been invested in providing constructive comments. Please find our responses below.\n\n**Reviewer: The empirical results are too minor to support the claim that the augmentation method is powerful.**\n\n**Authors' reply:** Yes, we concur that our empirical results are only a proof-of-concept, while our main contribution is theoretical. Our empirical simulation is specifically to show that, in a minimal MDP, our methods indeed learn the optimal risk-sensitive policy while previous algorithms with Markov policies have bounded performance (i.e. they fail to learn the optimal policy), which motivates further research to step away from Markov policies and to use the AugMDP. \n\n**Reviewer: My major concern is that the method in this work is very limited in both technical novelty and conceptual insight. Firstly, by the definition of OCE, it is very nature to formulate the problem with an augmented state space, which is roughly a combination of traditional RL (to learn $P$) with dynamic programming (to learn $b$). Secondly, the proofs in this work are merely straightforward applications of existing algorithms, which significantly limits the technical novelty.**\n\n**Authors' reply:** While we concur with the reviewer that our approaches are inspired by existing algorithms, we believe our work nonetheless contributes several novel and insightful results to risk-sensitive RL:\n1. We establish the first risk-sensitive PAC bounds for exogenous block MDPs (Thm 3.6 in Sec 3.1) – not captured by low-rank MDPs (Zhao et al. 2024) and requires novel techniques to handle the interplay between coverability and the augmented MDP.\n2. We derive the first risk-sensitive bounds for policy-gradient algorithms and prove a novel local improvement property in risk-sensitive RL (Thms 4.2 and 4.4 in Sec 4). This bridges the gap in the literature where policy gradient methods lacked theoretical guarantees in risk-sensitive settings.\n3. By abstracting out oracles, we provide a unifying framework for studying the large class of OCE risk measures that were previously disconnected in the risk-sensitive RL literature (e.g., Bastani et al. 2022, Wang et al. 2023, Zhao et al. 2024). Our framework not only simplifies analysis but also enables new algorithmic design (leading to the above two contributions), applicable across multiple risk measures. Our Related Works section (Sec 1.1) provides a more comprehensive discussion that positions our novel contributions within the RL literature. \n\n**Reviewer: Why do you consider the assumption that $Z(\\pi)\\in[0,1]$, instead of the classical assumption that each $r_h\\in[0,1]$?**\n\n**Authors' reply:** Our assumption to normalize cumulative rewards is actually *more general* than normalizing per-step reward as it allows for reward values that drastically vary across actions and states. For example, the reward sequence $0, 0, ..., 0, H$ is allowed under our framework (after scaling our normalization by $H$). This is in contrast to the arguably more popular assumption in the RL theory community that per-step rewards are in $[0,1]$ and cumulative rewards are in $[0,H]$, which only allows for dense rewards and precludes the above sparse reward example. A helpful resource that helped us understand the benefit of normalizing cumulative rewards is the paper http://proceedings.mlr.press/v75/jiang18a/jiang18a.pdf (which we cite at line 145) and their COLT 2018 talk https://youtu.be/If63ZSpEiSs at the 5:10 mark.\n\nPlease let us know if you have any other questions!", "claims_and_evidence": "The theoretical claims are well supported by the regret bounds, and the empirical results are too minor to support the claim that the augmentation method is powerful.", "methods_and_evaluation_criteria": "NA", "theoretical_claims": "As far as I see, the proofs are correct.", "experimental_designs_or_analyses": "Only a few experiments were conducted on a toy example, which does not significantly influence the evaluation of this work.", "relation_to_broader_scientific_literature": "This work focuses on risk-sensitive RL with OCE reward, which provides insights for exploring the risk-sensitive RL problem.", "essential_references_not_discussed": "The related works are well discussed.", "other_strengths_and_weaknesses": "Strength:\nThe authors  designed a  meta-algorithm which could be applied to many different OCE-RL settings,  including the challenging exogenous block MDP.\n\nWeakness:\n\nMy major concern is that the method in this work is very limited in both technical novelty and conceptual insight. Firstly, by the definition of OCE, it is very nature to formulate the problem with an augmented state space, which is roughly a combination of traditional RL (to learn $P$) with dynamic programming (to learn $b$). Secondly, the proofs in this work are merely straightforward applications of existing algorithms, which significantly limits the technical novelty.", "other_comments_or_suggestions": "I do not have any other comments.", "questions_for_authors": "1. Why do you consider the assumption that $Z(\\pi)\\in [0,1]$, instead of the classical assumption that each $r_h \\in [0,1]$?", "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": "y4hiG9Lclc", "reviewer": "Reviewer_t1og", "summary": "In this paper, the authors study the risk-sensitive RL problem to optimize a risk-measure of cumulative rewards. A family of risks called Optimized Certainty Equivalents (OCEs) are considered, and this includes popular risk measures such as CVaR and entropic risk. Two algorithms have been proposed in the paper, based on optimism principle and policy gradient, respectively. By forming an augmented Markov Decision Process (MDP), the formalism developed for risk-neutral MDP has been utilized in the paper. In the first algorithm, bounds that generalize prior results in CVaR RL, has been established. For the policy gradient based algorithm, monotone improvement and global convergence guarantees have been established under some assumptions. Empirically, it has been verified that the proposed algorithms learn the optimal history-dependent policy and Markovian policies fail to achieve optimality.\n\n## update after rebuttal\n The response addresses my major questions. I have slightly raised my score to 3 (as the generalization of AugMDP to the OCE setting does not seem to be very novel and is highly dependent on Rep-UCB in the literature).", "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": "Dear Reviewer t1og,\n\nThanks very much for providing helpful feedback. We truly appreciate the time and effort that have been invested in providing constructive comments. Please find our responses below.\n\n1. Our assumption to normalize cumulative rewards is actually *more general* than normalizing per-step reward, as it allows for reward values that drastically vary across actions and states. For example, the reward sequence $0, 0, ..., 0, H$ is allowed under our framework (after scaling our normalization & bounds by $H$). This is in contrast to assuming that per-step rewards are in $[0,1]$ and cumulative rewards are in $[0,H]$, the arguably more popular assumption in RL theory, which only allows for dense rewards and precludes the above sparse reward example. A helpful resource that helped us understand the benefit of normalizing cumulative rewards is the paper http://proceedings.mlr.press/v75/jiang18a/jiang18a.pdf (which we cite in line 145) and their COLT 2018 talk https://youtu.be/If63ZSpEiSs at the 5:10 mark.\n2. We note that the AugMDP for OCE only has one extra dimensionality compared to the original MDP, since the augmented state $b_h$ is a scalar. Moreover, the AugMDP is very easy to simulate, since $b_h$ has a known and deterministic transition function $b_{h+1}=b_h-r_h$, which adds essentially no overhead to the original MDP. Please see \"Remark: the AugMDP is easy to simulate\" in Lines 184-191 for more details.\n3. Thanks for the question. Regarding how to satisfy the two conditions (optimism and bounded regret) in Def 3.1, we note these conditions are satisfied by many optimistic algorithms in RL even when applied to the AugMDP. For example, UCB-VI satisfies these conditions in tabular MDPs, Rep-UCB in low-rank MDPs and GOLF in MDPs with exogenous block MDPs. We refer the reviewer to the paragraphs after Thm 3.2 and the text in 3.1 for several ways to satisfy these two conditions. \nRegarding logarithmic regret in the second condition, this is certainly captured by our framework; the second condition only states that regret should be sub-linear, which certainly includes $O(\\log K)$ regret as well. The implication on the OCE convergence is stated in Thm 3.2, which shows that the OCE regret is bounded by the oracle's regret multiplied by a constant $V^{\\max}_u$ that doesn't change the rate in $K$. Thus, an oracle with logarithmic regret would yield an OCE algorithm with logarithmic regret.\n4. Thanks for the suggestion, we'll certainly add more intuition about $V^{\\max}_u$: this constant intuitively captures is the statistical complexity of learning the OCE with utility $u$; for example, it is $1/\\tau$ for CVaR at level $\\tau$ and this is intuitive because smaller levels of $\\tau$ measures a smaller sub-population and thus requires more samples to learn. We will list and discuss more examples of $V^{\\max}_u$ in the main text (they are currently in Table 4 of the appendix due to page limit).\n5. We will also elaborate more about the exogenous block MDP in the revision.\n6. Thanks for the question. In theory, small value estimation error can be ensured by online supervised learning or regression, which is fairly standard (Agarwal et al. 2021). In practice, policy optimization algorithms such as REINFORCE with value baseline or PPO maintain a separate value network and interleave in gradient updates to the value network by minimizing squared loss (Schulman et al. 2017). We will add more discussions in the revision.\n7. While we concur with the reviewer that our approaches are inspired by existing algorithms, we believe our work nonetheless contributes several novel and insightful results to risk-sensitive RL:\n\n    1. We establish the first risk-sensitive PAC bounds for exogenous block MDPs (Thm 3.6 in Sec 3.1) – not captured by low-rank MDPs (Zhao et al. 2024) and requires novel techniques to handle the interplay between coverability and the augmented MDP.\n    2. We derive the first risk-sensitive bounds for policy-gradient algorithms and prove a novel local improvement property in risk-sensitive RL (Thms 4.2 and 4.4 in Sec 4). This bridges the gap in the literature where policy gradient methods lacked theoretical guarantees in risk-sensitive settings.\n    3. By abstracting out oracles, we provide a unifying framework for studying the large class of OCE risk measures that were previously disconnected in the risk-sensitive RL literature (e.g., Bastani et al. 2022, Wang et al. 2023, Zhao et al. 2024). Our framework not only simplifies analysis but also enables new algorithmic design (leading to the above two contributions), applicable across multiple risk measures. Our Related Works section (Sec 1.1) provides a more comprehensive discussion that positions our novel contributions within the RL literature. We are happy to answer any questions on our technical contributions.\n\nPlease let us know if you have any other questions!", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "The proofs seem to be okay.", "experimental_designs_or_analyses": "Experimental designs seem to be fine.", "relation_to_broader_scientific_literature": "A family of risks called Optimized Certainty Equivalents (OCEs) are considered, and this includes popular risk measures such as CVaR and entropic risk. Two algorithms have been proposed in the paper, based on optimism principle and policy gradient, respectively. In the first algorithm, bounds that generalize prior results in CVaR RL, has been established. For the policy gradient based algorithm, monotone improvement and global convergence guarantees have been established under some assumptions.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "The paper is well-written, however difficult to follow at some places. It introduces many concepts but some of the claims are largely based on existing works. There are some assumptions that requires further justifications.", "other_comments_or_suggestions": "Not applicable", "questions_for_authors": "1.\tWhy do we need to assume that $Z(\\pi)\\in[0,1]$? Since this is a summation of rewards, this may create a dependence between per-stage reward and horizon length. What happens when this condition is violated? This assumption seems far from reality. \n2.\tThe augmented MDP for OCE has a state space which has a much higher dimensionality than the original state space. The approach for construction for augmented MDP does not seem to be very efficient. \n3.\tThe optimistic oracle outputs an optimistic value function if two conditions, viz., optimism and bounded regret, are satisfied. How do one guarantee that these conditions will be satisfied? Also, second condition states that the regret needs to be sublinear, i.e., $O(\\sqrt(K))$? Is to possible to achieve logarithmic regret in the second condition? What will be the implication of the result on the overall convergence?\n4.\tMore intuition needs to be provided while defining $V_u^{\\max}$. Please quantify this in details. \n5.\tThe basic concepts behind exogenous block MDP needs to be elaborated. \n6.\tTheorem 4.2 guarantees global convergence if POA_LG has small value estimation error. How do one guarantees this small value estimation error?\n7.\tOverall, the paper introduces many notions towards a single objective. This impacts the readability of the paper, requiring more intuitions to be provided throughout the paper. Novelty of the proposed methodologies are limited, e.g., the generalization of AugMDP to the OCE setting does not seem to be very novel and is highly dependent on Rep-UCB in the literature.", "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": "vxRKO7wDBq", "reviewer": "Reviewer_74co", "summary": "The paper propose two meta-algorithms for solving static risk sensitive MDPs by using the augmented formulation for OCE objectives. The first one uses models based oracles and the other one using policy optimization based oracles. Regret bounds are analyzed with the assumption that the oracles are reasonably well designed.", "questions": "", "limitations": "", "rating": 4, "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": "Dear Reviewer 74co, \n\nThank you for your encouraging review and strong support! We truly appreciate the time and effort that have been invested in providing constructive comments.\n\nRegarding your question about notation on the value function:\n* $\\hat V_{1,k}$ is an estimated augmented value function from the Optimistic Oracle (Def 3.1). The subscript $1,k$ denotes it's at step $h=1$ and is from $k$-th round of the meta-algorithm (Alg 1).\n* $V^{\\pi^k}\\_1$ and $V^{\\pi^k}\\_{\\text{aug}}$ are both denoting the true augmented value function of policy $\\pi^k$ at step $h=1$. Thanks for catching this duplicated notation, we will consolidate these two notations into one.\n\nRegarding your concern about the novelty of our work:\nWhile the AugMDP has been studied for specific risk measures like CVaR, our work makes several novel contributions beyond straightforward application of this approach:\n\n1. We establish the first risk-sensitive PAC bounds for exogenous block MDPs (Thm 3.6 in Sec 3.1) – not captured by low-rank MDPs (Zhao et al. 2024) and requires novel techniques to handle the interplay between coverability and the augmented MDP.\n2. We derive the first risk-sensitive bounds for policy-gradient algorithms and prove a novel local improvement property in risk-sensitive RL (Thms 4.2 and 4.4 in Sec 4). This bridges the gap in the literature where policy gradient methods lacked theoretical guarantees in risk-sensitive settings.\n3. By abstracting out oracles, we provide a unifying framework for studying the large class of OCE risk measures that were previously disconnected in the risk-sensitive RL literature (e.g., Bastani et al. 2022, Wang et al. 2023, Zhao et al. 2024). Our framework not only simplifies analysis but also enables new algorithmic design (leading to the above two contributions), applicable across multiple risk measures. Our Related Works section (Sec 1.1) provides a more comprehensive discussion that positions our novel contributions within the RL literature. We are happy to answer any questions on our technical contributions.\n\nPlease let us know if you have any other questions!", "claims_and_evidence": "The claims are clearly presented with theoretical results (regret bounds) and some computational results.", "methods_and_evaluation_criteria": "The methods and evaluations are suitable.", "theoretical_claims": "Proofs in the main section are checked.", "experimental_designs_or_analyses": "The experiments are reasonable and interesting to see.", "relation_to_broader_scientific_literature": "RSRL is known to be hard to solve. This paper provides a good summary for existing methods for static OCE objectives, and demonstrated efficient implementations are possible.", "essential_references_not_discussed": "The related works are relatively complete.", "other_strengths_and_weaknesses": "The paper is well written. The introduction is clear and relationship with prior works are well discussed.\nThe augmented approach is practical due to the objective being intuitive. The presented meta-algorithms cover a wide range of application and problem setups.\nThe biggest weakness is that the results are hardly surprising as the augmented MDP approach is well known and has been studied extensively. Plus given a known oracle with assumption/definition 3.1 & 4.1, all regret bounds seem to be easy to derive.", "other_comments_or_suggestions": "I am a little confused by the notion on the value function with all the sub/sup scripts. What's the relationship between: $ \\hat V_{1,k} $, $ V_1^{\\pi^k} $, $ V_{\\text{aug}}^{\\pi^k} $?", "questions_for_authors": "Please see above.", "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 reviewers agree that the paper describes a useful algorithm for a practical setting. The writing is clear, and the paper is organized well. Most of the results are supported by proofs, although some of the proofs (such as Thm 2.1 and Thm 3.2) are much more just proof sketches than actual proofs. Although the proofs are not rigorous, most of the results are plausible. The numerical results are limited but illustrate the setting and algorithm quite well. 

Although the results in the paper are novel, they are somewhat incremental. The extension from CVaR to OCE is relatively straightforward, and not developed in great depth. The reviewers did not find much methodological innovation in the paper. It is not clear if there are any technical difficulties that need to be overcome.
Decision: Accept (poster)