On Dynamic Programming Decompositions of Static Risk Measures in Markov Decision Processes
Authors: Jia Lin Hau
Erick Delage
Mohammad Ghavamzadeh
Marek Petrik
Venue: NeurIPS 2023 poster (2023)
Keywords: reinforcement learning
markov decision processes
monetary risk measures
TL;DR: Showing that many risk measure decompositions are not optimal by given counterexamples.

Abstract: Optimizing static risk-averse objectives in Markov decision processes is difficult because they do not admit standard dynamic programming equations common in Reinforcement Learning (RL) algorithms. Dynamic programming decompositions that augment the state space with discrete risk levels have recently gained popularity in the RL community. Prior work has shown that these decompositions are optimal when the risk level is discretized sufficiently. However, we show that these popular decompositions for Conditional-Value-at-Risk (CVaR) and Entropic-Value-at-Risk (EVaR) are inherently suboptimal regardless of the discretization level. In particular, we show that a saddle point property assumed to hold in prior literature may be violated. However, a decomposition does hold for Value-at-Risk and our proof demonstrates how this risk measure differs from CVaR and EVaR. Our findings are significant because risk-averse algorithms are used in high-stake environments, making their correctness much more critical.

On Dynamic Programming Decompositions of Static Risk Measures in Markov Decision Processes
Jia Lin Hau University of New Hampshire Durham, NH jialin. hau@unh. edu
Erick Delage HEC Montréal Montréal (Québec) eri erick. delage@hec.
Mohammad Ghavamzadeh*
Amazon
Palo Alto, CA
ghavamzalamazon.co com
Marek Petrik
University of New Hampshire Durham, NH mpetrikēcs unh edu
Abstract
Optimizing static risk-averse objectives Markov decision processes difficult because they do not admit standard dynamic programming equations common in Reinforcement Learning (RL) algorithms. Dynamic programming decompositions that augment the state space with discrete risk levels have recently gained pop- ularity in the RI. community. Prior work has shown that these decompositions are optimal when the risk level is discretized sufficiently. However, these popular decompositions for Conditional- Value-at-Rii (CVaR) and Entropic- Value-at-Ris (EVaR) are inherently suboptimal regardless of the discretization level. In particular, we show that a saddle point property assumed to hold in prior literature may be violated. However, decomposition does hold for Value-at atsR and our proof demonstrates how this risk measure differs from CVaR and EVaR. Our findings are significant because risk-averse algorithms are used in high-stakes environments, making their correctness much more critical.
show that
1 Introduction
Risk-averse reinforcement learning (RL) seeks to provide a risk-averse policy for high-stakes real- world decision problems. These high-stake domains include autonomous driving (Jin et al., 2019; Sharma et al., 2020), robot collision avoidance (Ahmadi et al., 2021; Hakobyan and Yang, 2021), liver transplant timing (Köse, 2016), HIV treatment (Keramati al., 2020; Zhong, 2020), unmanned aerial vehicle (UAV) (Choudhry et al., 2021), and investment liquidation (Min et al., 2022), to name few. Because these domains call for reliable solutions, risk-averse algorithms must be based on solid theoretical foundations. This is one reason why monetary risk measures, such as Value-at-Risk (VaR) and Conditional Value-at-RR
(CVaR), have become pervasive in risk-averse RL (Prashanth and Fu. 2022). Indeed, risk measures such as CVaR are known to be coherent (Artzner et al., 1999) with respect to set of fundamental axioms that define how risk should be quantified and have been adopted as gold standards in banking regulations (Basel Committee Banking Supervision, 2019).
Introducing risk-averse objectives in Markov decision processes (MDPs)-the primary model used in RL-is challenging. Dynamic programming, the linchpin of most RL. algorithms, cannot be used directly optimize risk measure like VaR CVaR MDPs. One line of work tackles this challenge by exploiting the primal representation of risk measures and augmenting the state space
'The work was done prior joining Amazon, while the author Google Research.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

of their dynamic programs (DPs) with an additional parameter that typically represents the total cumulative reward up to the current point (Bäuerle and Ott, 2011: 1: Boda et al., 2004; Chow and Chavamzadeh, 4014; Filar et al., 1995; Hau et al., 2023; Lin et al., 2003; Wu and Lin, 1999; Xu and Mannor, 10. Even when the original MDP is finite, this DP requires computing the value function for a continuous state space, and thus, has been considered inefficient in practice (Chapman et al., 2022; Chow et al., 2015; Li et al., 2022).
Another line of recent work leverages the dual representation to produce a risk-level decomposition of risk measures (Pflug and Pichler, 2016). Using this decomposition, numerous authors have derived DPs for common risk measures and integrated them within various RL algorithms (Chapman et al., 2019, 2022: Chow et al., 2015; Ding and Feinberg. 2022, 2023; Ni and Lai, 2022; Rigter et al., 2021; Stanko and Macek, 2019). Although this risk-level decomposition requires augmenting the state space with a continuous parameter, this parameter naturally bounded between O and 1. It has been generally accepted, with several tentative proofs supporting this claim (Chow et al., 2015; Li et al., 2022), that these DPs recover the optimal policy if we can discretize the augmented state space sufficiently finely. Moreover, it is believed that one can use the optimal value function from this DP to recover the policies that are optimal for the full range of risk levels.
In this paper, we make a surprising discovery that numerous claims of optimality of risk-level decompositions published in the past several years are incorrect. Even when one discretizes the augmented state space arbitrarily finely, most risk-level DPs are not guaranteed to recover the optimal value function and policy. There are several reasons why existing arguments fail. As the most common reason, several papers assume that a certain saddle point property holds, either explicitly (Chow et al., 2015) or implicitly (Ding and Feinberg, 2022, 2023). We show that this property does not generally hold, invalidating the optimality of DPs, as hinted at in Chapman et al. (2019, 2022). This finding directly refutes the claimed or hypothesized optimality of algorithms proposed in many recent research papers and pre-prints, such as Chapman et al. (2019); Chow et al. (2015); Ding and Feinberg (2022, 2023); Rigter et al. (2021); Stanko and Macek (2019). Our results also affect applications of these algorithms, such as automated vehicle motion planning (Jin et al., 2019). We also identify gaps in related decompositions (Li et al., 2022; Ni and Lai, 2022) and propose how to fix them.
We make the following contributions in this paper. First, we show in Section 3 that the popular DP for optimizing CVaR MDPs may not recover the optimal value function and policy regardless of how finely one discretizes the risk level in the augmented states. This method was first proposed in Chow et al. (2015) but adopted widely afterwards (Chapman et al., 2019; Ding and Feinberg, 2022, 2023; Rigter et al., 2021; Stanko and Macek, 2019). The simple counterexample in this section contradicts the optimality claims in Chow et al. (2015); Ding and Feinberg (2022). We hypothesize that prior work missed this issue because the CVaR DP works for policy evaluation and only fails when one uses to optimize policies based on the "risk-to-go value function"". Therefore, our results do not contradict the original decomposition in Pflug and Pichler (2016) that only applies to policy evaluation. We give a new independent and simple proof that the CVaR decomposition indeed works when evaluating a fixed policy.
Second, we show in Section 4 that the DP for optimizing the Entropic- Petropic-Value-ve Value-at aisk in MDPs, proposed by Ni and Lai (2022), does not compute the correct value function even when the policy fixed. Although EVaR has not been as popular as CVaR, it has been gaining attention in recent years (Hau et al., 2023). We give an example that contradicts the correctness claims of the risk-level decomposition for EVaR in Ni and Lai (2022). The gap that we identify with this objective applies to both policy evaluation and policy optimization. Furthermore, we prove new, correct EVaR decomposition for policy evaluation. Unfortunately, the EVaR decomposition fails and is sub-optimal when applied to policy optimization, similar to CVaR.
Third, we propose an optimal dynamic program for policy optimization of VaR in Section 5. Our DP is based on a resk- decomposition that closely resembles the quantile MDP decomposition in Li et al. (2022) but corrects for several technical inaccuracies. The derivation shows why VaR stands apart from coherent risk measures like CVaR and EVaR. VaR is unique in that the decomposition can be constructed directly from the primal formulation of the risk measure, which avoids the complications that arise in the robust formulations used in CVaR and EVaR decompositions.
It is important to note that the correctness of DPs that augment the state space with the accumulated rewards is unaffected by our results (Bäuerle and Ott, 2011; Chow and Ghavamzadeh, 2014; Chow al., 2018; Hau et al., 2023). These DPs use the primal risk measure representation and do not suffer
2

---

from the same saddle point issue as the augmentation methods that use the dual representation of the risk measures, such as the one in Chow et al. (2015).
2
Preliminaries
This section summarizes relevant properties of monetary risk measures and outlines how they are typically used in the context of solving MDPs.
Monetary Risk Measures We restrict our attention to probability spaces with finite outcome space 52 such that [S2] = m for some m N. We use = IR' to denote the space real-valued random variables. To improve the clarity of probabilistic claims, we always adorn random variables with tilde, such as ă E X. In finite spaces, we can represent any random variable ā E X as a vector R".. We also the m-ddimensional probability simplex. Using this notation, we can write that E [i] = x.
Am represent a probability distribution over Ω where Am represents
A monetary risk measure th: X IR assigns real value to each real-valued random variable in way that it is monotone and cash-invariant (Follmer and Schied, 2016; Shapiro et al., 2014). risk measure can be seen as a generalization of the expectation operator E[-] that also takes into account the uncertainty in the random variable. In this work, we define all risk measures for random variables T that represent rewards. Thus, the risk-averse decision-maker aims to choose actions that maximize the value of the risk measure, i.e., a higher value of risk measure represents a lower exposure to risk.
We consider three monetary risk measures common in RL. Perhaps the most well-known measure Value-at aa-R (VaR), which defined for a risk-level a E [o, 1] and random variable ž X in modern literature as (e.g., Follmer and Schied 2016; Shapiro et al. 2014)
vaRa [d] = sup {a E P < x] s a} = inf {a E R I a}.
(I)
Note that VaR, [+] = oc. The equality between the two definitions holds, for example, by Follmer and Schied (2016, remark A.20).
Another popular risk measure is the Conditional-valne--ata level & E [0. 1] and a random variable å E X distributed as ã. ~ as (e.g., Follmer and Schied 2016, definition 11.8 and Shapiro al. 2014, eq. 6.23)
(CVaR), which is defined for a risk
CVaRa [G]
sup (a-a-'B ))+) inf {E E Am, & s)
(2)
EER
E[a.. The equality above follows from standard conjugacy arguments for finite probability spaces (Follmer and Schied, 2016). Note that our CVaR definition applies
with CVaRo [+] ess inf [ and CVaR1 [
that represents rewards and assumes that higher value of the risk measure is preferable to a lower value. Other CVaR formulations exist in the literature, but they induce identical preferences for appropriately chosen rewards and risk level
Finally, the entropic value at risk (EVaR), with EVaRo [ø] = ess inf and EVaR, [x] defined for (0, 1] as (Ahmadi-Jave 2012)
E[a), is
1 EVaRa [+] = sup log (a -E EE[[Eppppp (-3. R)])
.>00
B
(3)
in (E E Am. < q, (L(ll) S loga).
where KL is the standard KL-divergence defined for each x. y E An as KL(xlly) Even F. log ). This definition is valid only when x is absolutely continuous with respect to y. which is denoted as x & y and corresponds to you = 0 + Fi for each w Ω
Risk Averse MDPs A Markov decision process (MDP) is sequential decision model that underlies most of RL (Puterman, 2005). We consider finite MDPs with states S = (si..... sg} and actions A = {ai...., a.). After taking an action in a state, the agent transitions to the next state according to a transition probability function p: S x A + As such that p(,, a, 8') represents the transition probability from S to s' E S after taking E A. We use Ps.o p(s, a, .) E As to denote the vector of transition probabilities. The initial state &o distributed according to P As. To avoid divisions by 0 that are not central to our claims, we assume that p. > 0 for each E S. Finally,
3

---

the reward function is r: S x A S - R. where r(s, s') represents the deterministic reward associated with the transition to s' from s after taking an action a.
The most general solution to an MDP is a history-dependent randomized policy и which maps a sequence of observed states and actions 8", a² ss ,...,, s to distribution over the next action at. It is well-known that with risk-neutral objectives, there always exists an optimal stationary-dependds only on the last dette-deterministicc policy (Puterman, 2005). When the objective is risk-averse, like VaR, or CVaR, there may not exist an optimal stationary or deterministic policy. Hence, we use the symbol II to denote the set of distory-dependee
randomized policies in the remainder of the paper.
This paper focuses on the finite-horizon objective in which the agent aims to compute policies that optimize the sum of rewards over a known horizon T. We further restrict attention to the objective with horizon T = 1. It turns out that having a single time step is sufficient to derive our counterexamples to existing dynamic programs. Moreover, deriving the decompositions with T = 1 makes it possible to avoid technicalities caused by history-dependent policies, which could distract us from the main ideas presented in this work. Our results an be extended general horizons T > 1 and the discounted infinite-horizon objectives using standard techniques (Chow et al., 2015).
With horizon T = 1, the set of randomized history-dependenn policies is II - { S AAJ. D.J.Th The symbol π (ss, a) denotes the probability of action a in a state s, and π (s) = (s. E A denotes the A- A-dimensional vector of action probabilities in state Given a risk measure with risk level a E [0, 1]. the finite- hatte-horizon avveree value of a policy π E II is computed as
og (a) v/a (8) a, (15,,,8)),
where the superscript in Pa paper, we generally use š to denote the random state at time t = 0 and s' to denote the random state at time In risk-neutral objectives, when 3 E, one can use the tower property of the expectation operator and define a value function for each time step t (Puterman, 2005), but this property does not hold in most static risk measures (Hau et al., 2023). The term policy evaluation in the remainder of the paper refers to computing the value in (4).
(5)) specifies the distribution of the random action. Throughout the
The goal in an MDP is to compute an optimal value function and a policy that attains it. In risk-averse MDPs, this goal is formalized as the following risk-averse optimization
vg (a) max 2o (a) = max 1/ (()) [r a. 8')] =ell
with the optimal policy x* being any policy that attains the maximum in (5). As with policy evaluation, when 1 = E., the optimal value function ey can be defined for each time-step (Puterman, 2005), but this is impossible in general for common risk measures, like VaR and CVaR. The term policy optimization in the remainder of the paper refers to computing the value and the maximizer in (5).
In the remainder of the paper, we study dynamic programming algorithms proposed to solve the policy evaluation problem (4) and policy optimization problem in (5). general, these algorithms build on risk-level decomposition (Pflug and Pichler, 2016) of risk measures to define a value function 27 (s, ar) for each time step / E [T]. state & E S, and risk-level a E [o, 1] (Chow et al., 2015). The value function represents the risk-adjusted sum of rewards that can be obtained if starting in a state s E S at time t and a risk level a. For example, one would define the value function as uf (s, a) = Wa
(s)) (r((s a, 3')] and compute vi using a Bellman operator T op (ai = (TT In risk- neutral objectives, the Bellman operator is defined as (I (aT))(a)) = EleT(5, with a E (1), but in risk-averse formulations the operator definition is more complex. The remainder of the paper discusses the decompositions and the operator for CVaR, EVaR, and VaR risk measures respectively.
3 CVaR: Decomposition Fails in Policy Optimization
In this section, we show that a common CVaR decomposition proposed in Chow ct al. (2015) and used to optimize risk-averse policies is inherently sub-optimal regardless of how closely one discretizes the state space. The following proposition represents one of the key results used to decompose the risk measure in multi-stage decision- makin....

---

r(s), (1, -50
81,
r(s1, a1, (1,82) = 100
81
81, 0/
((,1)a2,))
start
82
82, 01
r(32, 01, = 10
Figure 1: Rewards of MDP Me used in the proof of Theorem 3.2. The dot indicates that the rewards are independent of the next state.
Proposition 3.1 (lemma 22 in Pflug and Pichler 2016). Suppose that II and 8 ~ p. ā ~ (3)..
Ps.a- Then,
CVaRa a 8)]
=
min Ee
CV..VaR.c.a ac, [r(8, ū, 11,,,,
(6)
CEZO
sES
where the state on the right-hand side not random and
Zc E E a
(7)
The notation in Proposition 3.1 differs superficially from lemma 22 in Pflug and Pichler (2016).
Specifically, our CVaR defined for rewards rather than costs, the meaning our a corresponds to 1 - in Pflug and Pichler (2016), and we use &, =.Ps the optimization variable. We include simple proof of Proposition 3.1 completeness Appendix A.1.
The decomposition in Proposition 3. is important because it shows that the CVaR evaluation can be formulated as dynamic program. The theorem shows that CVaR at time t decomposes into convex combination of CVaR values at f = 1. Recursively repeating this process, one can formulate a dynamic program for any finite time horizon T. Because the risk level at 1 differs from the level at t = 0 and depends on the optimal Ç. one must compute CVaR values for all (or many) risk-levels [0, at time & 1. As result, the dynamic program includes an additional state variable that represents the current risk level.
Chow et al. (2015) proposed to adapt the decomposition in Proposition 3.1 to policy optimization as
max CVaR ( ā,), = max min well CEZO
Σ
Sa (CVaR (r(s,, 5') 3= sl) =s)
Hell
ac.p.
SES
(8)
min CEZC
Σse SES
So
max CVaR (r(s,,,5") 3 açpp
dEAA
They used the decomposition in (8) to formulate dynamic program with the current risk level as an additional state variable. We prove in the following theorem that the second equality in (8) marked with question marks is false in general.
Theorem 3.2. There exists an MDP and risk level [0, 1] such that
- (7) (r(5,,, < min max CVaR sell
Σs. max CVaRavd and oC.
(r(,, - 1= (9)
CEZe
dEAA
Before proving Theorem 3.2, we discuss its implications. First, Theorem 3.2 contradicts theorems and 7 in Chow et al. (2015) and shows that their algorithm is inherently sub-optimal regardless of the resolution of the discretization. Theorem 3.2 also contradicts the optimality the accelerated dynamic program proposed in Stanko and Macek (2019). The result of (Chow al., 2015) was exploited as is in Chapman et al. (2019), Ding and Feinberg (2022), and Jin et al. (2019) to propose DP reductions, and extended, without proof, in (Rigter et al., 2021) to the context of Bayesian MDP.
Finally, important to emphasize that Theorem 3.2 only applies to policy optimization setting and does not contradict Proposition 3.1, which holds for the evaluation of policies that assign the same action distribution to each history of states and actions (i.e., policies that are independent the hypothesized values of ().
5

---

40
30
(g(Sn))
0.00
0.25
0.50
0.75 1.00
Sez
Figure 2: The functions 0z (+) and TT (-) used in the CVaR counterexample the proof of Theo- rem 3.2. The dashed line shows the function Sa, + m (z((Se, (-,
Proof. Let a = 0.5 and consider the MDP Mc in Figure 1. state 81, both actions aN and dg are available, and in state $2, only action a is available. The MDP's rewards
r(s1, 01, $1) = -50,
r(s1, a1, $2) = 100,
r(s1, 02 $1) r(51, 02 $2) =0
r(s2, 01) rrsss(( 01, $2) 10.
The transition probabilities in Mc are
p(s1, 01 81 0.4,
((81,11, = 0.6,
and the initial distribution uniform: Ps, = Pmg 0.5.
To simplify the notation, we define 0z Zc - IR for each и E and Ç E Zc as
(c) Σ Co CVaR C as ((s,
s].
SES
Because CVaR is convex in the distribution (Delage et al., 2019) and any distribution for r(5, a, 8)) obtained from policy II is mixture of the distributions of r(3, 81) and r(5, (2,, 5"), it is sufficient to consider only deterministic policies (there exists an optimal deterministic policy). Thus, can reformulate the left-hand side of (9) in terms of 0, (C)
max CVaRá~T(B)) ( ū, 8')] = max mell
CVaR (r(5, a
=E(
max min CG-CVRR actAT
(r(,,,
nE(M)N)) SEZC
max min (z()), TE/Ti.2)CEE2 CEZe
with Fi - (1, 02) and T2(s,
(1( for all E S. The functions 0,, (+) and Oz, (-) are depicted in Figure 2. Similarly, the right-hand side of (9) can be expressed
using the convexity of CVaR the distribution by algebraic manipulation
min CEZc
Es. max CVaRávd #ES
[r(s, a, 8') = min max (x(C). oC,A."
deAA
<E rE(m),)))
Using the notation introduced above and the sufficiency of optimizing over deterministic policies only, the inequality in (9) becomes
max min (x( min max (x(C). (EZOrE(m)mp)
(10)
ZE mp) CEEc
Figure 2 demonstrates the inequality in (10) numerically, with the rectangle representing the left- hand side maximum and the pentagon representing the right-hand side minimum. The dashed line represents the function ++ m( 0, (C).

---

To show the strict inequality in (10) formally, we evaluate the functions a,, (-) and 8 (-) for MDP Mc- The function (, linear because the CVaR applies constant, and CVaR translation invariant. The function 2r (.) is piecewise-lineal and convex, and its slope can be computed using the subgradient that for each S and & Zc satisfies (Chow al., 2015)
dc, S. CVaR C o [r(s, ā, "
s) 3 VaR o0. [r(s, (, 8*) 1==0
= 8]
Simple algebraic manipulation then shows that
Oz, (S) max {10 60 Co 90 Soz 50),
(1) 10 - 10
10
and Zc As, which implies that So. E (0, 1). Therefore, by algebraic manipulation, we get the desired strict inequality
max min (c) Te (m) CE2c
< min max Çe2o (m) (x(C) 4,
where and are represented by the pentagon and rectangle in Figure 2, respectively.
In summary, the decomposition in Proposition 3.1 cannot be exploited in policy optimization because the inequality in the derivation above may not be tight:
max CVaR (VaR@==(#) (r(3, a. 8') 8 == s] = max min Tell ÇEZo
Σ
La CVaRaraii
(r(s,, 8==
well
aGd
#ES
S min max CEZc well
Σ
So CVaR (VVaRaM(E)
(r(,,ū,)) ac.ps
SES
min CEZc #ES
Σ Co max
CVaRand de
ac (r(s,, 8') 3 s]
where the last equality follows from the interchangeability property of optimization and expected value (Shapiro et al., 2014, theorem 7.92).
Finally, omit comment the validity of the CVaR decomposition in Li et al. (2022) given that considers a different measure than the CVaR defined in Equation (1). Namely, their measure takes the form:
CVaR, [+] inf (z + (1 a) -E =1_)
CVaR -a [-
=ER
which is not coherent risk measure.
4 EVaR: Decomposition Fails for Policy Evaluation
In this section. we show that a decomposition for EVaR proposed in Ni and Lai (2022) is inexact even when considering the policy evaluation setting. Ni and Lai (2022) recently proposed decomposition of EVaR for fixed π E II with ā ~ π (3) and a risk level a E (0, 10 as
EVaRa (r(5,ā,8))
??
min
EG.EVaR, ae.p. [r(8, 0 18)
(11)
EEZE
SES
where 5 D. p(3,ā, ā, ), and
implicit in and (2022)
Ze { E As
Σ Es log(Es/p.) sES
-log a, E E
(12)
Note that we use variables E = ZaD. in comparison with z, in Ni and Lai (2022).
The constraint E < in (12) not stated explicitly in Ni and Lai (2022) but is necessary
because EV.Ra [:] is defined only for a' E [0,1]. 1]. When a' = a (11) it must also satisfy for each E S that
d' +
of.i= <1 +
g. S p.
This additional constraint & implies that Zr. C Zc, for the Ze defined in (7).
We claim in the following theorem (see Appendix A.2 for the proof) that the equality (11) does not hold even in the policy evaluation setting.
7

---

Theorem 4.1. There exists an MDP with a single action and a E (0, 1] such that
EVaRa [r(8, 01,8) 8')]
<
min Ee
E.AR GEAT7 [r(s, a1 8') = =s]
(13)
EEZB AES
the set ZE defined by (12).
Theorem 4.1 demonstrates a stronger failure mode than the in Theorem 3.2 (for CVaR policy optimization) since it applies to both policy evaluation and policy optimization settings.
We propose correct decomposition of EVaR in the following theorem and employ it to establish that the decomposition in (11) overestimates the actual value of EVaR (see Appendix A.3 for a proof). Theorem 4.2. Given any finite MDP with horizon T 1 and E (0, 1}. we have that
EVaRa ((s,0,8)
inf ÇE(O, (E,EZ
Σ E. EVaRc, (r(s,,,8) SES
where
()(()= = { E < P.
Σ
E. (1og(E../8.) log(S.)) S - -log log
#ES
Moreover, EVaR can be upper-bounded as EVaR, ar))
min Σ EVaR . (') $EZg AES
(14)
5 VaR: Decomposition Holds for Policy Evaluation and Optimization
In this section, we discuss a dynamic program decomposition for VaR whose decomposition resembles those for CVaR and EVaR described in Sections 3 and 4. We provide a new proof of the VaR decomposition elucidate the differences that make it optimal in contrast CV&R and EVaR decompositions. Our VaR decomposition closely resembles the quantile MDP approach in Li et al. (2022) with a few technical modifications that can significantly impact the computed value.
To contrast the typical definition of VaR with the quantile definition in Li et al. (2022), it is helpful summarize how VaR is related the quantile of random variable. Let q E R define as the a-quantile of E X when
P < q) 2 a and P < q) a
(15)
In general. the set of quantiles is an interval lq (a), q (a)] with the bounds computed as (Follmer and Schied, 2016, appendix A.3)
g (a) sup {= q (a) inf {2 P <
at inf (= P [ 2 a),
2] a} sup (2 P aa.
Note that when the distribution of ă is absolutely continuous (atomless), then q3 (a) 9. (a) and the quantile is unique. The following example illustrates simple setting in which the quantile not unique
Example 1 (Bernoulli random variable). Consider Bernoulli random variable ē such that = 1 and 0 with equal (50%) probabilities. Then, any value q [0, is valid 0.5 0.5-quantile because
9 (0.5) inf
{
PP
K
z] Z 0.5) inf {
2 2 0} =0
zeR
zER
क (0.5)
sup zER
0.5) sup
{= (=|=<1) =1
zek
The objective in Li et al. (2022) is maximize the quantile operator Qo: X reward random variable ā X and a risk level a E [0, 1] as
E defined for
Qa (i)
inf {= {[
(16)
sER
The quantile operator Qa and VaR differ in which quantile of the random variable they consider:
Qa ( = प (a), but
VaR. [ = - (a).
(17)
As result, the quantile MDP objective in (16) coincides with the VaR value only when the quantile is unique, which is not always the case, shown in Example 1.

---

Theorem 5.1. Let ÿ: Q - [N] be random variable distributed as p = (pi),=m with p. > 0. Then for any random variable X, we have
VaRa [
sup
min VG. [ 5 = a. c
a
(18)
CEAN
where we interpret the minimum to evaluate to co if all terms are infinite, which only occurs if a = 1.
Proof. We decompose VaR using the definition in (1) as
VaR
[8]
sup
{=
E R
P
a sup
ZER
i P Σ
<
<<<==0=->
sa
N
(b)
sup
2
E
Ç E
[0, 1
P
< 5
Wi [N],
Eúe S
N
sup
sup
az E RR
<
1 3 [IM] 16 E 00, 11"
Σ
SPs Sa
1=1
N 3 1 1 4 11 = 10,1 Σ
P
tus sup
2z a
R
Sips Sa
[N[3]
N Σ
sup
min sup (E[N]
R
<
= 1 s 6.) 16 I 1),
Site Sa
sup
min VaRç. [ ÿ i] KEIN
1I, Σ Sp. Ippsa
We decompose the probability [ < =] as a marginal of the conditional probabilities step (a) and then lower-bound them by an auxiliary variable Ça in step (b). In step (c) we replace the joint supremum over and Ç by sequential suprema, and then we replace the supremum of intersection by the minimum of the suprema of sets in (d). The equality
= P pā < z == i] and p. = P-
in (d) holds because P J < z] is monotone and, therefore, the sets {z E R P t < y are nested. Finally, step (e) follows from the definition of VaR (1).
i] S {
Focusing on the finite MDP with horizon T' = 1, we can show that the decomposition proposed in Theorem 5.1 is amenable to policy optimization. The main difference between the VaR decomposition and CVaR is that the former VaR was expressed as a supremum instead of an infimum over quantile levels Ç. For VaR, changing the order of maximum (x) and supremum (C) does not suffer from potential gap, but changing the order of maximum (л) and infimun/minimum (C) in CVaR does suffer from such a gap as shown in Theorem 3.2.
The following theorem (proved in Appendix A.4) summarizes the decomposition for VaR. Theorem 5.2. Given any finite MDP with horizon T 1 and E [0, 1), we have
max VaRa~T 3')] sup min max VaRaad Tell
ÇEAs SES dEA. ac, (((s,ā,5) 3 = === s]laa
For completeness, Appendix C extends Theorem 5.2 to a setting with horizon T > 1, providing dynamic programming equations and definition of the optimal policy. These equations are analogous to the equations presented in (Li et al., 2022) yet we obtain them using the accurate definition and decomposition of VaR..
We finally present below a valid decomposition for the lower quantile MDP, used officially as the objective in (Li et al., 2022) (see Appendix A.5 for proof).
Proposition 5.3. Given any finite MDP with horizon = 1 and some a E [0, 1]. we have that:
9
max Qa (3) (r(3,ā,8')) = sup Tell
min 11
max Q² (rdd == Σ
C.D. < a
cE|O.11s
dEAA

---

We note that the difference with the result presented in (Li et al., 2022) resides in the constraint imposed on Ç that replaces the weak inequality with a strict one. In fact, this strict versus weak inequality is the main distinguishing factor between the decompositions for the lower and upper quantiles.
Conclusion
This paper shows that popular decomposition approach solving MDPs with CVaR and EVaR objectives is suboptimal despite the claims to the contrary. This suboptimality arises from a saddle- point gap when optimizing policy. We also prove that a similar decomposition approach optimal for policy optimization and evaluation when solving MDPs with the VaR objective. The decomposition optimal because VaR does not involve the same saddle point problem CVaR and EVaR.
Our findings are significant because practitioners who make risk-averse decisions in high-stakes scenarios need to have confidence in the correctness of the algorithms they use. Our work raises awareness that popular static CVaR and EVaR MDP algorithms are suboptimal, and their analyses inaccurate. We hope the results present in our paper will increase the scrutiny of dynamic programming methods for risk-averse MDPs and motivate research into alternative approaches, such the parametric dynamic programs.
Acknowledgments
We thank Yinlam Chow for his insightful comments that inspired this paper's topic and results. The work in the paper was supported, in part, by NSF grants 2144601 and 2218063. In addition, this work was performed in part while Marek Petrik was a visiting researcher at Google Research. Finally, E. Delage acknowledges the support from the Canadian Natural Sciences and Engineering Research Council and the Canada Research Chair program [Grant RGPIN-2022-0522 and
References
Mohamadreza Ahmadi, Xiaobin Xiong, and Aaron D Ames. Risk-averse control via CVaR barrier functions: Application bipedal robot locomotion. IEEE Control Systems Letters, 6:878-882 2021.
A. Ahmadi-Javid. Entropic Value-at-Risk. A new coherent risk measure. Journal of Optimization Theory and Applications, 155(3):1105-1122 2012.
Philippe Artzner, Freddy Delbaen, Mean-Mare Eber, and David Heath. Coherent measures of risk. Mathematical Finance, 93)):033-22 228, 1999.
Basel Committee on Banking Supervision. Minimum capital requirements for market risk. In Basel III: international regulatory framework for banks, 2019.
Nicole Bäuerle and Jonathan Ott. Markov decision processes with average-value-attrisk criteria. Mathematical Methods of Operations Research, 74(3):361-379, 2011.
Kang Boda, Jerzy A Filar, Yuanlie Lin, and Lieneke Spanjers. Stochastic target hitting time and the problem of early retirement. JEEE Transactions on Automatic Control, 49(3):409-419 2004.
Margaret P Chapman, Jonathan Lacotte, Aviv Tamar, Donggun Lee, Kevin M Smith, Victoria Cheng, Jaime Fisac, Susmit Jha, Marco Pavone, and Claire Tomlin. risk-sensitive finite-time reachability approach for safety of stochastic dynamic systems. In American Control Conference (ACC), pages 2958-2963. IEEE, 2019.
Margaret P Chapman, Riccardo Bonalli, Kevin M Smith, Insoon Yang, Marco Pavone, and Claire Tomlin. Risk-sensitive safety analysis using conditional value-at-risk. IEEE Transactions Automatic Control, (7(12))6521-6533 2022.
Arnay Choudhry, Brady Moon, Jay Patrikar, Constantine Samaras, and Sehastian Scherer. CVaR- based flight energy risk assessment for multirotor uavs using a deep energy model. In IEEE International Conference Robotics and Automation (ICRA), pages 262-268, 2021.
10

---

Yinlam Chow and Mohammad Ghavamzadeh. Algorithms for CVaR optimization in MDPs. In Neural Information Processing Systems (NIPS), 2014.
Yinlam Chow, Aviv Tamar, Shie Mannor, and Marco Pavone. Risk-sensitive and robust decision- making: A CVaR optimization approach. In Neural Information Processing Systems (NIPS), 2015.
Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone. Risk-constrained reinforcement learning with percentile risk criteria. Journal of Machine Learning Research, 18: 1-51, 2018.
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wilex-Interscience,, 2nd edition, 2006.
Erick Delage, Daniel Kuhn, and Wolfram Wiesemann. "Dice"-sion-makke -sin-making under uncertainty: When can random decision reduce risk? Management Science, (5()):3222-3301, 2019.
Rui Ding and Eugene Feinberg. CVaR optimization for MDPs; Existence and computation of optimal policies. ACM SIGMETRICS Performance Evaluation Review, 50(2):39 41, 2022.
Rui Ding and Eugene A. Feinberg. Sequential Optimization of CVaR, February 2023.
Jerzy A. Filar, Dmitry Krass, and Keith W. Ross. Percentile Performance Criteria For Limiting Average Markov Decision Processes. IEEE Transactions on Automatic Control, 40(1):2-10, 1995.
Hans Follmer and Alexander Schied. Stochastic Finance: Introduction in Discrete Time. De Gruyter Graduate, fourth edition, 2016.
Astghik Hakobyan and Insoon Yang. Wasserstein distributionally robust motion control for collision avoidance using conditional value-at-risk. IEEE Transactions on Robotics, 38(2)93999977, 2021.
Jia Lin Hau, Marek Petrik, and Mohammad Ghavamzadeh. Entropic risk optimization discounted MDPs. In Artificial Intelligence and Statistics (AISTATS), 2023.
I Ge Jin, Bastian Schürmann, Richard M Murray, and Matthias Althoff. Risk-aware motion planning for automated vehicle among human-driven cars. In American Control Conference (ACC), pages 3987-3993, 2019.
Ramtin Keramati, Christoph Dann, Alex Tamkin, and Emma Brunskill. Being optimistic to be conservative: Quickly learning a CVaR policy. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 4436-4443. 2020.
Ümit Emre Köse. Optimal timing of living-donor liver transplantation under risk-aversion. PhD thesis, Bilkent Universitesi (Turkey), 2016.
Xiaocheng Li, Huaiyang Zhong, and Margaret Brandeau. Quantile Markov decision processes.
Operations Research, (023):1428-1447 2022.
Yuanlie Lin, Congbin Wu, and Boda Kang. Optimal models with maximizing probability of first achieving target value in the preceding stages. Science in China Series A: Mathematics, 46: 396-414, 2003.
Seungki Min, Ciamac Moallemi, and Costis Maglaras. Risk-sensitiive optimal execution via a conditional value-at-risk objective. arXiv preprint arXiv:200..11962, 2022.
Xinyi Ni and Lifeng Lai. Risk-sensitive reinforcement learning via Entropic- VaR optimization. In Asilomar Conference Signals, Systems, and Computers, pages 953- 9599 IEEE, 2022.
Georg Ch Pflug and Alois Pichler. Time-consistent decisions and temporal dccomposition coherent risk functionals. Mathematics of Operations Research, 41(2):682-699 2016.
Prashanth and Michael Fu. Risk-sensitive reinforcement learning via policy gradient search. Foundations and Trends in Machine Learning, 15(5):537-693, 2022.

---

Martin L Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley-Interscienee 2005.
Mare Rigter, Bruno Lacerda, and Nick Hawes. Risk-averse Bayes-adaptive reinforcement learning. Advances in Neural Information Processing Systems, 34:1142-1155 2021.
A. Shapiro, D. Dentcheva, and A. Ruszezynski. Lectures on Stochastic Programming: Modeling and Theory. SIAM, 2014.
Alexander Shapiro.
Interchangeability principle and dynamic equations in risk averse stochastic programming. Operations Research Letters, 45(4):377-381, 2017.
Vishnu Sharma, Maymoonah Toubeh, Lifeng Zhou, and Pratap Tokekar. Risk-aware planning and assigmment for ground vehicles using uncertain perception from acrial vehicles. In International Conference on Intelligent Robots and Systems (IROS), pages 11763-11769 IEFF, 2020.
Silvestr Stanko and Karel Macek. Risk-averse distributional reinforcement learning: A CVaR optimization approach. In International Joint Conference on Computational Intelligence, pages 412-423, 2019.
Congbin Wu and Yuanlie Lin. Minimizing risk models in Markov decision processes with policies depending on target values. Journal of mathematical analysis and applications, 231()):47-67, 1999.
Huan Xu and Shie Mannor. Probabilistic goal Markov decision processes. In International Joint Conference on Artificial Intelligence, 2011.
Huaiyang Zhong. Decision Making for Disease Treatment: Operations Research and Data Analytic Modeling. Stanford University, 2020.
12

---

$1
81,01 r(s1, r($1,a,)) a1
start
$2
82, 01
r(82, 01,
Figure 3: Rewards the MDP Mg used in the proof Theorem 4.1. The dot indicates that rewards are independent of the next state.
A Proofs
A.1 Proof of Proposition 3.1
Suppose that > 0; the decomposition for 0 holds readily because CVaRR [o] ess ess inf [ To streamline the notation, Define a random variable = r(,, a, 8*) over a random space S x A x S with probability distribution q E Am such that Qs.a.s' = f. (s) p(s, a, s').. The value æ is the vector representation of the random variable ă and &. f.... E R for f I is vector that corresponds to the subset of the elements of S2 in which the first element is some E S. The vectors Z, = x,,,, RS S.A and q, 9s.., E R are defined analogously to &..
Starting with the CVaR definition in (2) and introducing auxiliary variable we get that
CVaRa [t] = min
min T & og S q) EEAm,CERS
{a E ot S 9, S. = 1 vs S}
min {x & a $ q: S. = 1_ Ee. ac. S.. Vs E s}
CEAm
{xT & of < q, Co = E., Vs ES CERO.CEZC
min
In the derivation above, we replaced the infimum by a minimum because is finite, introduced a new variable Ç. derived implied constraints Ç, and then dropped superfluous constraints Continuing with the derivation above and noticing that the constraints on each & are independent given get that
EoJes I at s q, C. = Ee, Vo ES
CVaRa [
min
SERR.CEZe
SES
min CeZo
inf #ES E.ERO
fa, Es og, < qs. So = 1 {T,
min
So min XEAs.A
{o, x app SaXa, S & Va A, s' E {}}
qsa.s,
CEZC
min Ce
C. CVaR oc.
[ =
SES
The step (a) follows from the interchangeability principle (Shapiro et al., 2014, theorem 7.92), and the step (b) follows by substituting Ex.a.s' = SeXa.s' taking care when ñ. = 0 and multiplying both sides of the inequality by 6ー 0. Finally, in step (c), random variable = r(ā, a, 8') conditional on is distributed according to 9, and the equality follows from the definition of CVaR in (2).
A.2 Proof of Theorem Theorem 4.1
Consider an MDP ME depicted in Figure 3 with S = (81, and A= = {ar} and reward function ((81,01,) and r(82, a1,") ) O. We abbreviate the rewards to r(s1) and r(*2) because they only depend on the originating state. The initial distribution is p.; P.2 0.5. We finally let 0.75.
13

---

Because ZB S 2c, the right-hand side of (13) can be lower-bounded by CVaR as
min {EZg
Σ SES
Ee EVaR ac. (r(s,01,3)
min Σ Ear(s)
E
#ES
(19)
min EEZC
Σ Ear(s) = CVaRa (r)),
SES
The first equality holds from the positive homogeneity and cash invariance properties of EVaR, and the last equality follows from the dual representation of CVaR (Follmer and Schied, 2016).
Because EVaR [o] I CVaRa [ă] for each a E [0, 1] and z E X (see (Ahmadi-Jare Javid, 2012, proposition 3.2)),
further lower-bound (19)
EVaRa [r(8, a1. 3 < CVaRa ar, 3')]
min <EZB
Σ SES
E. EVEa as.p," a1ss,a..3 (20)
Therefore, (13) holds with inequality.
To prove by contradiction that the inequality in (13) is strict, suppose that
EVaRa [r(3, (1,,,0188) 8')
min
Σ
EVaR 25.01 (r(s,a1,
(21)
EEZp.
SES
Equalities (21) and (20) imply that EVaR. (r(3, 01, 8')] CVaRa [r($, 01, 01, which false in general (Ahmadi-Javid, 2012).
We now show that EVaR does not equal CVaR even for the categorical distribution of The CVaR of the return in Mr reduces from (2) to
CVaRa (r(3, 01, 01, min Esr(s) max (0, Pm + +a +a-1]
(22)
EEZo
#ES
Since 1 a = 0.25 < 0.5 Pe,, then the optimal 6* in (22) is
Pug +a-1
E-=
Since KL( < - log a we have that 5* is in the relative interior of the EVaR feasible region in (3), and, therefore, there exists an > such that
EVaR,, [r(s, 01, CVaRa (r(3, 01, 8')] CVaR,, (r( s
which proves the desired inequality.
A.3 Proof of Corollary 4.2
We start by proposing a new decomposition for EVaR. Proposition A.1. Given a random variable ī E % and a discrete variable ÿ: - = (I,...,N) with probabilities denoted as {p: I for any (0, 1] we have that
EVaR.. [
inf cE(0.)j EE2((C)
min
Σ& EVAR [ = i)
where
Z)(C) = EEAN < P. Σ G(log(Et/i.)) log(Gi) < -llg a
Proof. Let q denote the joint probability distribution of ã and ÿ. The proof exploits the chain rule of relative entropy (e.g., Cover and Thomas (2006, theorem 2.5.3)), which states that for any probability distributions n, q Ag with 77 < that
KL(nllg)
(L( (z))))
(23)
14

---

where the conditional relative entropy is defined as
n y) q [
(L(n( E" log
with EE" [f(; []] as a shorthand notation to indicate that (Ø: () ~ 1). We can now decompose EVaR from its definition in (3)
F.V.R
[+]
inf mEAm-x:nc
17 i
KT g) S - -logogg log
(
inf
E"
[
KT.
KL ( - log a
ne PEAmNNTE
(
inf ne nEAm.Nin
E [
KT.(17
R"
log q
10 -log
KL (L 1 -
log
inf nE N CE(O, 1
E" TE
Py, E [log( ((((() 81 - - -log(()) =
(
inf (E.
E BE(ERR
[لlل|| (I( E log(S))) -
N
inf SEAw.CE(0.11-4440
Σ EVaR [ = |
& log(E:/D)) Σ ==1
& log(Gi) - log Σ
Here, decompose the relative entropy of n and using (23) in step (a) and then use the tower property the expectation operator in the next step. In step (b), we introduce a variable & for each
realization of ÿ with V to decouple the influence of ( ū), under each in the inequality
constraint. Finally, we replace the conditional EVaR definition by solving for vy ( g)) for a given C in step (c), and representing (ī) using E.
The first part of our theorem follows directly from Proposition A. Suppose that a > 0; the result follows for 0 because EVaRo [-] reduces to ess inf. Then, the second part of the corollary holds as
EVaRa (r(5, ā. 3')] =
= inf CE(0,INNEEA.
Σ Eo EVaR,, (r(s,,,5))) |3 s Σ
Es log
E,
< log a
S.P.
LES
sES
< inf $E(U,1)N,EEA)
Σ EVaR,, (r(s, [3=]] 13== Σ
Eo log
t. Sepe
log a E a
SES
SES
< inf EEAN LEES
E.E ag.p. [r(,,ū,)) == =] و a D
The first inequality follows from adding a constraint on the pairs on the considered by the infimum. The second inequality follows by fixing = S. with Č. = at.p, 1-1 for each s E S. This is an upper bound because Ç. is feasible in the infimum:
E E. log
E. CoD.
log S - log
SES
The value ? is well-defined since 9. > 0 and the constraint & S a a' ensures that & 1. Also, we
can relax the constraint C, > 0 + E. > 0 to E. > 0 because EVaRo [ā] = lim EVaR,, [=]. and, therefore, the infimum is not affected. Finally, the inequality in the corollary follows immediately by further upper bounding the decomposition above by adding constraint.
15

---

A.4 Proof of Theorem 5.2
The equality develops from Theorem 5.1 as (a) VaR a,)] max sup
(VaR (s) (5) [r(s,,,)) s=
s])
min sEB
nell
well CE
aco
VaR (r(s,a,8) s]
min CEAgio CSP Rell REB
sup
max
acop
sup min eES
max dEAA
(r, 8
CEAgia<SS
where we first change the order of maximum and supremum, followed by changing the order of max; min, with minl, max,. The latter a direct consequence of the interchangeability property of the maximum operation (Shapiro, 2017, proposition 2.2).
A.5 Proof of Theorem 5.3
The proof mainly relies correcting the decomposition of lower quantile proposed in (Li et al., 2022).
Proposition A.2. Given an & E X. suppose that random variable ÿ: Ω - N = -1,,...,NN is distributed as p = (px) with pi > O. Then:
Q. (8)
sup <E(O,1)
min iEN:S,S1
C.Di <a
(24)
where interpret the supremum to be minus infinity if its feasible set is empty, which only occurs if
a = O.
Proof. First, we decompose the lower quantile using its definition
N
(z( sup fz P <
sup ZER
Σ
P [a
<aj
i=1
Σ Cipe a, P < (
sup =EB.Ce|0.11
N
sup =ER.ÇE(O.1JN
2 1 (6 (01 4 <1, Σ
Si <a
i=1
sup CE[o,1|
sup zER
{z = - W. 4 < 1} Σ
SiD: < a
Σ Gp. <
sup
min ieN:iis
(ā ( ū=
CE
i=1
We decompose the probability IP [ < 2] in terms of the conditional probabilities PP < 1 0= in step (a) and then lower-bound them by an auxiliary variable G in step (b). In step (c), we exploit the following equivalence:
P < 5 j= < + = < <
1 i)
The direction 4: in the equivalence follows from the definition of Qc, (ā 5 i):
2 < Qc. (5 0 = inf {z P < ÿ = (i P < <
The direction = follows from the definition of VaR (see equation (1)), which implies that VaR upper-bounds any z that satisfies the left-hand condition:
PP [ < 5 = i] < = Qc (5 5 i) = sup {= E R P <> < ( 2 2,
yet Qc, (f 1 = 1) + z otherwise since IP [5 < = 7 = right continuous, there must exist some
> 0 for which P [ < + ū < 4 hence:
= = sup {a IR P < z 5 = i| < 2
which leads to contradiction. In step (e), solve for Finally, we obtain the form in (24).
16

---

M
$1. Q1
0.76
0.25
Ps1
100
start
$1 03
0.5
0.5
400
52
82, 01
200
Figure 4: An example used to show the sub-optimality of a policy in Appendix B.
100
Valuo
-10
0.00 505
0.90
875
1.00
Figure 5: Return computed in Chow et (2015) optimal CVaR policy for the example in Figure with ps, Pss 0.5 and M = 600. The optimal CVaR policy for each is denoted by x². The value function è computed according to the decomposition in the r.h.s. of (8) and the corresponding policy is f.
B CVaR Suboptimal Policy
In this section, we construct simple MDP to demonstrate that the suboptimality of the CVaR decomposition discussed in Section can also lead to computing a suboptimal policy, First, we give particular example in which the policy computed according to Chow et al. (2015) is suboptimal. Then, we show that the sub-optimality gap can be arbitrarily large.
To demonstrate the suboptimality of the policy computed in Chow et al. (2015), consider an MDP with two states and three actions and horizon T = 1 as shown Figure 4. Also let M 600 and
200
0.6
190
Figure 6: The function (-). and C.1 in CVaR decomposition at a = 0.5 for the example in Figure with Psj Psg 0.5 and M 600.
17

---

CV&R decompasition suboptimality
G1l0, Pr.
3000, Pr,
M 600, 0.75
M 3000 0.75
110
633
M- 600, Pa.. 0.
M 5000, Po 0.0
0.90
3000, 0.99
39-
Figure 7: CVaR decomposition suboptimality for different M and Ps2 for MDP defined in Figure
Pst = Psa 0.5. optimal solution for the 81 sub-problem in this example
[VaRRo [r(81, 8)] af < 0.5 CVaRa a1, if a' 2 0.5.
CVaRa $ s1]
Figure depicts the sub-optimality demonstrated by the CVaR decomposition. CVaR decomposition for policy optimization would over-approximate (black dash) the value function and commit to a sub-optimal solution (red solid). This simple example answers the following important concerns on the suboptimality.
First, CVaR policy optimization decomposition in Chow al. (2015) can lead one to choose suboptimal policy. In particular, Figure shows that the CVaR policy optimization decomposition is an overestimate of the return and the decision maker commits to the worst action for CVaR objective a E (0.25, 625). Furthermore, action 0g is never chosen for (Chow et al., 2015) even though is the only optimal action for (0.375, 0.6875). We can see from Figure 6 when we inspect the function for a = 0.5 that ag is optimal with CVaR return of 50. However, the CVaR decomposition would select a a2 and over-estimate the CVaR return to 100, but the sub-optimal actions a a2 would have the true CVaR return of O instead.
Second, there is no upper bound on the sub-optimality of the action chosen with respect CVaR return of the optimal action. The regret of the sub-optimal return is dependent on the distribution of the sub-optimal action and unbounded with respect to the true optimal return, as the performance of the sub-optimal return for a E (0.25, 0.5) is worse than the worst case scenario of the best worst-case policy. Increasing the magnitude (M > 400) for the reward instead of the sub-optimal action a₁ in $1 in Figure 4 increases the sub-optimality and can be arbitrarily large.
Third, the sub-optimalin can occur for any (0. 1). As above, we use the MDP in Figure 4 and
perturb two values to demonstrate the suboptimality by (i) increasing the magnitude (M > 400) for the reward of the sub-optimal action $1, di, or (ii) increasing the initial state probability (px,)) That leads to increasing the range where the CVaR decomposition for policy optimization yields sub-optimal policy shown in Figure 7.
18

---

C Extension to Longer Horizon
For completeness, we include in this section an extension of the corrected decomposition presented in Theorem 5.2 to horizon T > 1. Our demonstration establishes that the decomposition proposed in Theorem and of (Li al., 2022) actually applies the upper quantile (i.e. value-at-risk) of the cumulated reward rather than the lower one as claimed by the authors. In comparison with the proof found (Li et al., 2022), we pay close attention to demonstrating that the supremum in (5.1) l) attained when finite and that deterministic policies are optimal.
Given any finite MDP with horizon T > 0 and [0, 1]. we define the initial value
Ug
max CEAs
min max Q1 (s, aLsp' a $ SSD). EES
(25)
atA
The state-action value function q: Sx AA [0, and each E S and E A is defined as
R for the terminal step T and a E [0,
0o i
gr+1(s,0,a)
0
otherwise.
For each / = 1,.... T and a < the state-action function is defined recursively as
qe a, a) = max <EAs
min max r(s, a, s') + qi+1(s' d', a(s a.. 5. Pea (''S a' a'EAA
(26)
For 1, the state-action value function is defined
(e(s, a, 1) == oc.
To construct the optimal policy, we also need to define a bistory-dependent risk level ā₁ S x 4 [0, 1] that satisfies for each = .,... and 81,..., St and 01, a:-1 that
qe (8, a, (8 (1.--1)) min max a(s,a,8') q++1 (8,, a', uet ([s1a, s'), (01--1, a'I)-
s'ES a'EA
The appropriate values ag can be readily recovered from the optimal solution to (26), Finally, letting
{A
if Oz =1
at (St, az))
(27)
arg max @t (8t, a, ax)) otherwise
we construct deterministic and $1...., and a1, a:-1 that puts all the probability mass 0j (s Q1:-1))), i.e.
policy me St A + A for each 1.....
på pa (āt (s:, ae(S a1:r-1))) =
(28)
The following theorem states that the value function defined above represents the VaR of the returns of the optimal policy. Moreover, the history-dependen policy above is optimal and attains the optimal VaR return.
Theorem C.1. For a finite horizon and any a E [0. 1] we have that up defined in (25) coincides with the optimal VaR return:
Σ r( ãe, Sexi))
max Valdamm(@nnednee
rEll
Moreover, this optimal return is attained by the policy
( defined in (27):
T
VaR "apara
Σ
r(3, ār $041)
Uy
In proving Theorem C.I, we will make use the upper semicontinuity property of VaR, [t]. which presented in the following Lemma for completeness.
Lemma C.2. The function VaR [x] is upper semicontinuous in the interval a [0, 1].
19

---

Proof. This follows from the fact that VaR. is non-decreasing and right-continuous in terms of (see Lemma A.19 in (Follmer and Schied, 2016)).
Proof of Theorem C.I. The proof consists of two steps addressing the two equalities stated by the theorem.
Step I: For all |. 1, -,...,, T, we let
(5t az at,
max VaRai rEll+1IT
(s, 5c+1) +
Σ r(āv ay, Se4+1) St. at M=++1
where 11-1:T refers to the set of all history-dependent policies starting from time 1, and where VaRa[ az] is short for VaRa á, = St. a. ar). We will first show how (s, a, a) = ge (s a, a) for all -..... T. s S, E A, and a E [0, 1]. We follow with our conclusion about No.
First, addressing the case have that
can easily that for all t = 1,.... T, S, and A,
(5t; Ot, 1)
max xell+tu7
VaR,
(1,
Σ
r(ār, ae, 55411) st,
v=1+1
00
(e(ss, dz, 1)
based on our definition of value-at-risk for a Next, for S a < 1 and using short for Psa when can start looking at time = T, where we have that for all 8T S, and or E A:
GT (ST, ur, aT) Valay (r(sT, ar, 8441))
sup CEAs
min S'ES
Val Val (r(sT, 8']] aT S Sp
min VaR VaR 1r a7, s']l aT csp 1
max CEAs
sEES
min r(ST, uT, 8') + VaR VaR [0] or Ç Spp e'ES
max <EAs
max ÇEAs
min r(sT, AT, 8') + max QT ( aTTsPT)) oT Ç SSP #EES
ded
=gT(sT,a7,yy)
where we first the definition of (s, a, a)), then the decomposition of VaR in Theorem 5.1. We follow with confirming. based on extreme value theory, that the supremum over Ç must be achieved given that VaR, (.) of random variable J is upper semi-continuous (usc) in (see Lemma C.2), that the minimum of a finite set of use functions is usc, and that s is compact. The other two steps follow from the translation invariance of VaR and the definition of 4T+1 (8, a, o:).
Moreover, for all < t < T let he (ōLe, - the history between t and t'. Using the short-hand Fe. = r5pr, āe, $14+1,, and when S a, < 1, we have that:
(5t,,, Ge, az) max relles1.r
Valar Va medeme (1 az, 3(41)
+
Σ
r(ār, āe, 3e4
p=t+1
T
max
sup ÇEAs
min E'ES
VaR VaR Capa (r +
Σ
Fv 8841 5 / SSD
*
v=t+1
max (EAs
min VaR a (r( + s'ES a1c,77
Σ
Fy 8111 = =1|
Ssp
*Ell+417
M=141
20

---

T
max <
max rell++17
min S'ES
VaR (a (1 assop
+
Σ
Fv | = 51 at 1o..55 SSP
M=t+1
VaR Marerddan
Pet (b:12.0) (r,),,
max
min
max Jee 12:T
ÇEAs
T
Σ re
3 s'l a S
= max <EAs
min r(s,, C2 8')+ F'ES
VaR VaRatinda Rit1 (het2ee)
T
max d=
Σ n'1+1
Pe
3141 = =11
a S
max min r(st, s') + deti(s', a a.. csp <EAs
(29)
('ES
where, as before, we start by exploiting the decomposition Theorem 5.1 and explicating that the supremum is attained. We then change the order of the two maximums, followed by changing the order of max, ming' with min./ maX,, which follows based on the intrrchangcability property the minimum operation (Shapiro, 2017, proposition 2.2). We finally introduced (s, a--lulue function operator which can reduced as follows:
B (be 1.)
(s =
max (F
VaR.
rBur āe, 31 Σ t=t
max IAI dEA, VaRardd Brdd (hr4s
max
VaRa
r(āg āe, 41) = =5]
(x") (
p=t
VaR (a (r(8,, (,4,),
max ( aEd
max
r(Sy, ue, 11)1)18, =8 8,
p=t+1
max max
VaRa. a ((S,,, ( +
Σ
rlöe, ay, (5 = s, = a]
aEA 11ll,
M=1+1
-max ()) c'A
(30)
where we exploited the fact that value-at-risk is mixture quasi-convex function (Delage et al., 2019),
meaning that it cannot be improved by randomized policy.
Hence, replacing i back in equation (29), get
(St, 0t, at)
max (EAy
min r(st, at, + max S'ES
a -a.-55 SSp
aeA
max
min r(s,, a2 + max max maxx)-115' ((SoP | SS s'ES
ÇEAs
aEA
(e(s,, at at).
Finalizing our conclusion, we get using the short-hand = r(5e, ães 8141) that
VaR (hana)
Σ
max sup xell ÇEds
min s'ES
VaR ( a
Σ Ft 51 =
a < ssp
T
sup çeAg
min E'ES
max de heeeee
V (True) ac
Σ
rs 51 16
aa. 10.10sss)
21

---

sup
min max s'ES Alllarr
VaRaroma(ha)) actp,
Σ Fr 51 = s
a < S
ÇeAe
sup
min max /i (5', a a.. 31 = s'1 a 5. < s'ES aeA
ÇeAs
min max 91 a, | $ a a s
sup
çE
s'eS
00
where we employ the same steps as for reducing de to qt-
Step 2: Regarding the optimality of the proposed policy, we will show inductively that
(51. as)==
T
VaR
r(st,
ar, a(st,
5c+1) +
Σ 1=
r(āe, ār, 3841) I St, Gr. (r(3,,,, Ō1æ-1) = dtz
is an upper envelope for (st, 0t, ax) for all 1 < t < T. Conditioning on ag in the definition above necessary because the policy ø depends on the risk level a. This can then be exploited to obtain the following inequality:
VaR bs tt (hia))
r (5t. ãe, S(+1)l
sup ÇEAs
min SES
VaR (a
rs 3111)1 al
ac,PT
sup çeAs
min VaR VaRaa SES
(s)))
aC.PT
T
min VaRa (baa) sE8
r(5 āz =
(s))
(1)
min à (s, (8, (s, (n))) 2 min (8 ai (1)) (()) #E8
SES
min /) (3, (s.,
min max (1 a, ā (s))
sES
min max qi as, a < s 1 = =00 aES aEd
max
(EAs
T
max VaRasma (hrr)) xell
Σ
r(3e, āi, (e, Be41)
VaR Fe
Σ r(3,, ār, Sem1)
where the first step comes from the decomposition VaR, the second from the definition of π1. The third step follows from the fcasibility of S. := āi (a)/, )) We then exploit the definition of 91. the fact that it upper bounds ?1, the equivalence of i and @1, and definition of aj. On the sixth line, exploit the definition of ân (s), followed with the definition of vo. These steps would therefore confirm that के is optimal.
We are left with showing that ã upper bounds áe for all t I,..., Specifically, starting with t = T, we have:
(S(T,,T,a7) Valar (r(sT, ar, (r aT] (r(s,, (lss,ar,00 ar, aT)
(31)
22

---

Then, for < T we focus on the case a₂ < 1, since otherwise we have oo 2 oc. Specifically, we first define
(e(5,, 06) = Vala, Val (r 8x,11)
r(ay, de, Se ar a1:-1) arl: e=t+1
which captures the value-at-risk at level a of the reward-to to-go looking forward from time t when running given that the history up to time satisfies ãe (5(31.r+ 01:1-1) ) at.
We then take inductive steps starting from / = 7 down to 1 = 2. At each i, we can verify that if q. is upper envelope for dt, then
(st, 1) 00 2 00 max (st, a, 1) (st,1) aEA
and that for 0 $ oz 1:
(s ar)
MaRaroty(he ((s), $441)
r(Sy, ae, 3v41) 81, āz = a( ar)
p=t+1
= (s of (Sc, az), an) 2 (st, oz (st, ar) = ( (s ar) (()
max (8t, a, oz) max (8t, a, ()).
aεA
atA
where we first used the definition of æ. then used the definition of âr. followed with the assumed property that q. is upper envelope for q.- We then employ the equivalence of q, and q. twice, the definition of at, and the relationship between is and & established in (30).
Next, we confirm that if or is an upper envelope for út, then taking one step back and using the short-hand Fe. = r(šv, ae, $141) 1 we get:
( 0,-1, 01-1)
VaR (dieee (188 +
( 01 2) = 02-1)]
Prr
d==
min r (81-1, (EES
sup CEAs
T
Fg 8 = -1 = a-- 0-1 S
===t
sup CEAs
min (11--1,0-1193 SEES
I
Fr 8t = (. = -. a: .
1==1
min dES
(t- 6')+
Val A 11
Σ
8t ( = -6,,
1=1
min r(st-1, az-1, 50) (s',
S'ES
min eES
r(;-1,, 4- 8¹) + iz (8' (1
min
r( 188-1, 8 max EEES
aEA
min e'ES
182-1,4-111 5¹) max aEA
sup <EAg
min ((5--1, + maxq a4 a. a- .5-1 sEES
aEA
23

---

The first step comes from the decomposition of VaR, the second from the fact that ae is known given that 0z-1, št. and a are fixed while Et= r(šy, ăe $1+1) only depends on št and āz The third step follows from replacing the supremum over with feasible member of Ag. The fourth step follows from the definition of 8, followed with the fact that it upper bounds Ü₁ Finally, we exploit the definition of g(-) and of (-1(-). This completes the inductive proof demonstrating that (-)- is an upper envelope for (e(-) for all 1 S t S T. r(st-1, (51-1. de(s', an-1S0P7") ai-1 1
sup çeAs
min SEES
04-1
where
g(a,s, 8, s, := == arg CEAginsSP... E"ES
max min r(s, a, s")
+mxx (s a, "Ce aEA
24


Reviews:
[{"review_id": "SpVN3jF08k", "reviewer": "Reviewer_Vzn6", "summary": "This paper investigates the effectiveness of decomposition approaches for solving risk-averse Markov Decision Processes (MDPs) with Conditional Value-at-Risk (CVaR), Expected Value-at-Risk (EVaR), and Value-at-Risk (VaR) objectives. The goal is to assess the validity and accuracy of these common decomposition techniques for risk-averse decision-making.\n\nMain contributions:\n\nSub-optimality of CVaR and EVaR decomposition: The paper demonstrates that the widely used decomposition approaches for CVaR and EVaR objectives are inherently suboptimal, invalidating previous works. These methods involve a saddle-point gap during policy optimization, leading to incorrect results. As a result, practitioners should exercise caution when using these decomposition techniques for risk-averse MDPs.\n\nOptimal VaR decomposition: In contrast to the suboptimal CVaR and EVaR decompositions, the paper identifies the VaR decomposition as an optimal approach for both policy evaluation and optimization in risk-averse MDPs. The VaR decomposition does not suffer from the same saddle-point problem, making it a reliable method for risk-averse decision-making.\n\nIncreased awareness and call for alternative approaches: The findings highlight the limitations of two traditional decomposition methods, CVaR and EVaR, and emphasize the need for scrutiny when using these decompositions. Researchers are encouraged to explore alternative approaches, such as parametric dynamic programs, to improve risk-averse decision-making in MDPs.", "questions": "Can the authors elaborate on their selection of the specific decomposition approaches used for comparison? Are there any reasons why these three approaches were chosen over others?\n\nCould the authors provide more insights into the computational complexity and scalability of the VaR decomposition method concerning the size and dimensionality of the risk-averse MDPs, either in a short discussion or references? Are there any notable challenges when applying this approach to large and more complex decision problems?\n\nAs a broader point of interest, how significant is the choice of the risk level (alpha) in the performance and efficiency of the VaR decomposition method? Are there any guidelines on selecting appropriate alpha values based on a given problem characteristics? This is important to understand the robustness of this method in a new risky environment, a desideratum for any risk averse decision-making algorithm in high stakes applications, which relates to the broader impact of this work as hinted in the last point of the conclusion.\n\nGiven that the paper focuses on risk-averse MDPs, are there any indications or early results on how the VaR decomposition approach and its optimality might generalize to other types of decision-making frameworks, such as partially observed problems?\n", "limitations": "The paper does a good job at addressing its limitations insofar as it focuses on three specific approaches to risk averse decision making.\n\nThe main limitation which has not been addressed, and which in my opinion should be addressed, is giving more context as to why this three approaches were chosen, or why is it is sensible to choose them, and mention the fact that there exist other state-of-the-art approaches, which need to be considered and comprehensively evaluated in the future, and which could serve as avenues for future research in addition to parametric dynamic programs, e.g., control as inference and active inference.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Rigorous analysis: The main strength of the paper is its rigorous treatment of three decomposition approaches for risk-averse MDPs. \n\nSignificant and clearly stated contribution for the field: The paper shows the sub-optimality of CVaR and EVaR decomposition methods invalidating several previous works on the topic. This finding is valuable as it warns practitioners about unknown limitations of these techniques in risk-averse decision-making.\n\nOptimal VaR decomposition: By identifying the VaR decomposition as an optimal approach for policy evaluation and optimization in risk-averse MDPs, the paper provides a practical solution to the limitations of CVaR and EVaR. Thus this VaR decomposition is a reliable alternative to these two methods.\n\nEncouraging further research: In light of the limitations faced by CVaR and EVaR, the paper calls for exploring alternative approaches, such as parametric dynamic programs.\n\nClarity in presentation and methodology: The paper is well-written. It uses clear explanations, comprehensive mathematical analysis, and compelling illustrative examples.", "weaknesses": "Limited set of approaches: Perhaps the main weakness of the paper is the limited set of (three) decomposition approaches being scrutinized. While the paper highlights the sub-optimality of CVaR and Expected Value-at-Risk EVaR methods, it does not compare a broader range of state-of-the-art techniques. This limitation makes unclear the extent to which VaR decomp Google Mapsosition can be considered optimal. I appreciate that it would not be possible, given length constraints and scope of the paper, to evaluate other baselines comprehensively. However, it would be valuable if the authors could mention other state-of-the-art techniques in a related works section, and whether they can say anything about them in relation to the approaches they investigated here. For instance, control as inference and active inference use the KL divergence as a decision-making objective (i.e., a belief-based reward function) which entails risk-averse behaviour, and which might be related to VaR [1,2,3].\n\nUnclear scalability discussion: The paper does not extensively discuss the scalability of the proposed VaR decomposition concerning problem size or dimensionality. I appreciate that this might not be important for theoretically minded readers, however, since the paper has important implications for practitioners (i.e., widespread adoption of VaR) it would be nice to immediately know, via some discussion or suitable reference, how well this method scales as MDPs grow complex and large in applications.\n\nLimited generalization: The paper comprehensively addresses the setting of risk-averse MDPs. It would be nice to know whether the theoretical analyses presented here can offer some insights on more general problem classes like risk averse partially observable Markov decision processes (POMDPs). For example, has VaR been extended to risk averse POMDPs, and if so would you expected it to be optimal in this case?\n\nFrom the two points above, one of the main weaknesses of this paper is that it is not straightforward to infer to what extent VaR is a viable approach in a wide range of practical problems, and thus it is unclear to what extent the paper implies an optimal, promising in the near long-term approach to the risk-averse decision problem. In my understanding, this is the main point of broader impact in the machine learning community, so it should be addressed.\n\nTypos: l 136, l200\n\n[1]\tS. Levine, ‘Reinforcement Learning and Control as Probabilistic Inference: Tutorial and Review’, arXiv:1805.00909 [cs, stat], May 2018, Accessed: Dec. 29, 2021. [Online]. Available: http://arxiv.org/abs/1805.00909\n[2]\tL. Da Costa, N. Sajid, T. Parr, K. Friston, and R. Smith, ‘Reward Maximization Through Discrete Active Inference’, Neural Computation, vol. 35, no. 5, pp. 807–852, Apr. 2023, doi: 10.1162/neco_a_01574.\n[3]\tD. Hafner, P. A. Ortega, J. Ba, T. Parr, K. Friston, and N. Heess, ‘Action and Perception as Divergence Minimization’, arXiv:2009.01791 [cs, math, stat], Oct. 2020, Accessed: Nov. 07, 2020. [Online]. Available: http://arxiv.org/abs/2009.01791", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the detailed review and the helpful suggestions. We provide some clarification and answer your questions below.\n\n**It would be valuable if the authors could mention other state-of-the-art techniques in a related works section.**\nThat is a good suggestion; thank you. In fact, the introduction describes multiple alternative state-of-the-art techniques that do not suffer from the problems we identified. We will edit the final version to emphasize the existence of these alternative approaches in the introduction and throughout the paper.\n\n**Can the authors elaborate on their selection of the specific decomposition approaches used for comparison? Are there any reasons why these three approaches were chosen over others?**\nThese are good questions. We chose these decompositions because they are popular in modern literature and, as we demonstrate, do not offer the optimality guarantees that the papers claims. Also, these decomposition algorithms use a technique pioneered by Pflug and Pichler (2016). \n\nAs we mention above, other decomposition techniques are worth further study. We hope our results will encourage further research into these alternative approaches, which do not suffer from the same issues we identify in this work. In the final version, we will position these approaches in the context of the three papers proposed by the reviewer.\n\n**Unclear the extent to which VaR decomposition can be considered optimal. How well this method scales as MDPs grow complex and large in applications.**\nThis is a good point. Using the decomposition in large-scale MDPs, one will need to introduce further approximations. This complex issue is beyond this paper's scope and deserves systematic study in future work. The techniques proposed in section 4.2 of Li et al. (2022) and Chow et al. (2015) can be used with VaR decomposition too. \n\n**Could the authors provide more insights into the computational complexity?**\nWhile we agree with the reviewer that this is an important practical question to ask oneself, this paper focuses on the theoretical soundness of the decomposition schemes for VaR, CVaR, and EVaR. We will edit the narrative to further emphasize that the implementation concerns can be found in section 4.3 of Li et al. (2022) and that we leave the question of the optimal algorithm (in terms of complexity) open for future research.\n\n**How significant is the choice of the risk level?**\nAlthough this is an important concern, we must defer it to future work for similar reasons as stated above.\n\n**How the VaR decomposition approach... might generalize to other types of decision-making frameworks, such as partially observed problems?**\nWe agree that this is an important line of work but is beyond this paper's scope. However, one could apply the quantile MDP decomposition scheme to POMDPs after translating them to the equivalent belief-space MDP. Of course, many technical details need to be addressed carefully in doing so.\n\n**This is the main point of broader impact in the machine learning community.**\nWe actually expect our work to have a broad impact on ML, particularly by retarding the propagation of incorrect claims in the risk-averse RL literature. While we are convinced that the quantile MDP decomposition has the potential to be of great help in practice, our paper's main objectives when defining this decomposition are two-fold: 1) correct some technical inaccuracies in Li et al. (2022), and 2) provide insights on conditions under which optimal dynamic programming can be used for policy optimization.\n\n**References**\n\n[1] Yinlam Chow, Aviv Tamar, Shie Mannor, and Marco Pavone. Risk-sensitive and robust decision-making: A CVaR optimization approach. In Neural Information Processing Systems (NIPS),2015.\n\n[2] Xiaocheng Li, Huaiyang Zhong, and Margaret L. Brandeau. Quantile Markov decision processes. Operations Research, 70(3):1428–1447, 2022.\n\n[3] Georg Ch Pflug and Alois Pichler. Time-consistent decisions and temporal decomposition of coherent risk functionals. Mathematics of Operations Research, 41(2):682–699, 2016."}, {"review_id": "oIk8HPRRFp", "reviewer": "Reviewer_bRij", "summary": "The authors demonstrate that dynamic programming decompositions for CVaR and EVaR can be suboptimal, and show that VaR may not be subject to the same problems in MDPs of horizon 1. ", "questions": "- In policy evaluation, will the proposed algorithm need to be able to handle continuous $\\alpha$, and how can that be done? \n\n- Is it possible to learn a policy with $T > 1$, and what would the specific policy learning algorithm look like (in broad strokes)?", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper provides some interesting observations conflicting with previous papers on CVaR and EVaR optimization in RL. ", "weaknesses": "While this paper makes some interesting observations about the decompositions of CVaR, EVaR, and VaR, it seems like an incomplete paper, without enough contributions meriting acceptance. \n\nThe “dynamic program” presented in Section 5 seems far from implementable, with weak (if any) guarantees. For contrast, [Chow 2015] shows that the CVaR Bellman operator is a contraction with a unique fixed point, and also discuss how to discretize the space of $\\alpha$ to make practical implementations possible. They also provide proof-of-concept experiments. The proposed VaR operator seems to face similar issues (e.g., with $\\alpha$ being continuous), but the submitted paper appears to handle none of these points.  It would be interesting to see the decomposition proposed in Theorem 5.2 translated into a policy learning algorithm, e.g., of the style of value iteration proposed in [Chow 2015], complete with theoretical analysis and empirical evaluation.  \n\nAdditionally, Theorems 5.1 and Proposition 5.3 appear to only hold for $T=1$ which is essentially a contextual bandit? While the authors state that results can be extended to $T > 1$ using “standard techniques,” I find that $T = 1$ is an unusual assumption in RL (for MDPs) and usually something that makes risk-sensitive RL much easier (because you don’t have to deal with stochasticity from transitions). In this light, it seems worth it to at least expand Section 5 for $T > 1$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive comments, which encourage us to suggest adding to the appendix of the paper a natural extension of the VaR decomposition presented as Theorem 5.2 to the general case of $T>1$ (more on this below). Indeed, we had not noticed that a reader might consider Section 5 incomplete without a proper derivation of a dynamic program decomposition method for $T>1$, and we are happy to remediate this issue.\n\nThis being said, we strongly disagree with the idea that our paper might be \"incomplete\". Indeed, the goal of our paper is to demonstrate that a popular dual decomposition scheme that is used for CVaR and EVaR (and could continue to be deployed for other coherent risk functionals based on Pflug and Pichler (2016)) is suboptimal, thus encouraging the use of their alternate primal decomposition form, and rigorously identifies a DP decomposition scheme for VaR. Given the wide adoption of the problematic CVaR decomposition and the risk that reinforcement learning researchers or practitioners continue to incorrectly employ the decomposition presented in Pflug and Pichler (2016), this paper addresses important and timely objectives and successfully achieves them. \n\nWe also disagree with the idea that our paper focuses on contextual bandit problems. The decision to identify counterexamples that focus on an MDP with $T=1$ is done without loss of generality and intentionally with the aim of simplifying the technical exposition. We, however, realized when reading the comment that the decomposition in Theorem 5.3 was perhaps overly simplified and are happy to include in an appendix the more general version of this theorem.\n\n**Theorem**. Given any finite MDP with horizon $T>0$ and $\\alpha\\in[0,1]$, we have \n\n$\\max\\_{\\pi\\in\\Pi} VaR\\_\\alpha^{\\tilde a_t\\sim\\pi_t(\\tilde s_t)}[\\sum_{t=1}^T r(\\tilde s_t, \\tilde a_t, \\tilde s_{t+1})]$\n$= \\sup_{\\zeta\\in \\Delta(S)} (  \\min_{s\\in\\mathcal{S}} \\max_{a\\in A } Q_1(s,a,\\alpha \\zeta_s \\hat p_s^{-1})  |  \\alpha\\cdot \\zeta \\leq \\hat p )$.\n\nwith $Q_{T+1}(s,a,\\alpha) := 0$ if $\\alpha<1$ otherwise infinity, and for all $1\\leq t \\leq T$:\n\n$Q_{t}(s,a,\\alpha) :=  \\sup_{\\zeta\\in\\Delta(S)} (  \\min_{s'\\in\\mathcal{S}} r(s,a,s')+\\max_{a'\\in A } Q_{t+1}(s',a',\\alpha \\zeta_s p_{sas'}^{-1}) |  \\alpha\\cdot \\zeta \\leq p_{sa})$\n\nMoreover, the policy\n\n$\\bar \\pi_t(s_{1:t},a_{1:t-1})\\in \\arg\\max_{a\\in A} Q_t(s_t,a,\\bar \\alpha_t(s_{1:t},a_{1:t-1}))$\n\nwith $\\bar \\alpha_0:=\\alpha$ and\n\n$\\bar \\alpha_t(s_{1:t},a_{1:t-1}) \\in  \\bar \\alpha_{t-1}(s_{1:t-1},a_{1:t-2}) p_{s_{t-1},a_{t-1},s_t}^{-1}\\cdot$\n    \n$[\\arg\\max_{\\zeta\\in\\Delta(S):\\bar \\alpha_{t-1}\\cdot\\zeta\\leq p_{s_{t-1},a_{t-1}}}\\min_{s\\in S} \\max_{a\\in A} Q_t(s,a,\\bar \\alpha_{t-1}(s_{1:t-1},a_{1:t-2})\\zeta_s p_{s_{t-1},a_{t-1},s_t}^{-1})]_{s_t}$\n\nis optimal.\n\nWhile the proof is inspired by the work of Li et al. (2022), it corrects for the wrong definition of VaR that is used, circumvents an issue in the proof of Lemma 2, extends the results to the space of stochastic policies, and rigorously confirms that the supremum over $\\zeta\\in\\Delta(S)$ is achieved in order to employ it in the definition of the optimal policy.\n\nRegarding the implementability of the decomposition for VaR, we first recall that the objective of this paper is NOT to propose a new algorithm for VaR-MDP but rather to solidify/question the foundation of methods that have been recently proposed and popularized by proceedings/journals with the highest standards in terms of quality. If the reviewer is interested in implementation details and empirical evaluation, we encourage him/her to refer Li et al. (2022), where section 4 proposes an algorithm for the VaR MDPs that is then deployed in an HIV treatment initiation problem (see section 6.2). We believe this should answer most of the reviewer's questions and perhaps convince him/her that the scope of our paper is justified.\n\nRegarding the existence of a unique fixed point, please note that such a question does not apply to the finite time horizon setting that we consider. We agree, however, that it is a relevant question for extending the decomposition to an infinite horizon setting, but we judged this to be beyond the scope of this paper, given its objectives. There has been relevant work studying this question in the field of distributional RL and target-based Markov decision processes, but this is a complex topic that deserves careful treatment.\n\n**References**\n\n[1] Xiaocheng Li, Huaiyang Zhong, and Margaret L. Brandeau. Quantile Markov decision processes. Operations Research, 70(3):1428–1447, 2022.\n\n[2] Georg Ch Pflug and Alois Pichler. Time-consistent decisions and temporal decomposition of coherent risk functionals. Mathematics of Operations Research, 41(2):682–699, 2016."}, {"review_id": "ftCyBCecW8", "reviewer": "Reviewer_Gp5S", "summary": "The main contribution of the paper is to demonstrate that a popular dynamic programming decomposition for well-known risk metrics only provides suboptimal policies. More precisely, the underlying idea of such decompositions is to operate on an extended state space that incorporates a continuous state variable between 0 and 1 capturing the system risk level at the current stage. The belief in these existing decompositions was that the risk state variable could be finely discretized to approximate the optimal value function arbitrarily. However, the authors show a counter-example for CVaR and EVaR. Finally, they show that VaR does admit such a decomposition with a new proof scheme.   ", "questions": "1. The next natural question is how poor the discretized systems can be. Are there any asymptotic guarantees on its quality, even under some non-zero approximation ratio?\n2. Are there specific coherent metrics where the discretization could still be valid?\n", "limitations": "The authors have not included any limitation subsection. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "+ The paper and proofs are very well-written and structured\n+ Contribution is impactful within the analysis of risk measures\n\nI particularly find that this is an outstanding paper and contribution. First, it closes an open theoretical question on a meaningful and growing body of literature composed of 10+ papers only in these last five years, specifically demonstrating via a relatively simple but ingenious example that discretization is necessarily sub-optimal. The results are intriguing because the discretization assumption was a rather intuitive result, justifying many of the attempted proofs in the most recent literature. The authors also provide corrected decompositions for EVaR and VaR.\n\nI also note that it is also a bit concerning that these results contradict the optimality of many recent works, which are thus worth revisiting in the future. (On that note, I verified the proofs and examples of this paper to the best of my abilities, but did not re-analyze the previous papers' proofs, except to re-check their statements).\n\n ", "weaknesses": "- Much of the intuition is hidden in the proofs.\n- Lack of discussion of possible research avenues to address this issue.\n\nMy primary concern is that the presentation can be excessively technical in some parts. I believe the proofs are very well written and easy to follow, especially as they are mostly counter-examples, but it would be interesting if authors could bring to light what fails more intuitively (just the saddle point discussion was commented on briefly). In particular, my understanding from the examples is that the discretization violates a certain variant of Von Neummann's minimax theorem due to non-convexity/non-concavity of policy choice, here captured in the strict inequality of equation (10). Perhaps my understanding is not accurate, but nonetheless it would be interesting if authors could expand more on the saddle point argument, perhaps providing directions on conditions for other coherent metrics that do not suffer from the same discretization issue. \n\n\nMinor notes:\n\n- Please kindly use capital letters when naming lemmas and theorems, e.g., Lemma X as opposed to lemma X.\n- In the proof of Prop. 3.1, \"Define\" should be \"define\"; also please define \"ess inf\".\n- In the proof of Theorem 4.2, I am a bit confused with line l.457: \"the first inequality follows from adding a constraint on the pairs.\"\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed review and the encouraging words. We answer the questions and clarify some of the points below.\n\n**Lack of discussion of possible research avenues to address this issue.**\nThis is a great point. Given how widespread this error is in the extant literature, we believe that it is important to correct this important misunderstanding. As we discuss in the introduction, the alternative algorithms proposed in Bauerle \\& Ott (2011) and Hau et al. (2023) do not suffer from the same issue. We will clarify the relevant discussion in the introduction and throughout the paper in order to emphasize this issue. \n\n**The next natural question is how poor the discretized systems can be. Are there any asymptotic guarantees on its quality, even under some non-zero approximation ratio?**\nThat is an intriguing question. We attach the sub-optimality plot of the CVaR of the return for this simple MDP in the attached pdf with the global response, our examples indicate that the error can be arbitrarily large without additional structural assumptions on the MDP. One could also refer to the $\\theta$ function, as shown in Figure 2 of our paper, and manually design a MDP to make CVaR and EVaR algorithms incur arbitrary loss. \n\n**Are there specific coherent metrics where the discretization could still be valid?**\nThat is a good question, but we are unaware of ***coherent*** risk measures for which this type of decomposition would work. Given that the robust representation of all coherent risk measures involves a minimization, the same problem is likely to be present.  Note that the decomposition works for VaR, but that is not a coherent risk measure. \nThe decomposition of Bauerle \\& Ott (2011) and Hau et al. (2023) for CVaR and EVaR, respectively, is done in the primal form of the risk measures and therefore does not suffer from the duality gap which we present in this paper.\n\n**Providing more intuition about the results**\nIn the revision, we will make sure to include additional discussion regarding the saddle point condition that is violated by faulty decompositions for CVaR and EVaR. In particular, in the context of convex (thus continuous) action space, it might be possible for some applications to exploit the concavity of the long-term reward function to establish the needed saddle point property. One example already appears in Min et al. (2022) under the shape of a portfolio management problem.\n\n**References**\n\n[1] Nicole Bäuerle and Jonathan Ott. Markov decision processes with average-value-at-risk criteria. Mathematical Methods of Operations Research, 74(3):361–379, 2011.\n\n[2] Jia Lin Hau, Marek Petrik, and Mohammad Ghavamzadeh. Entropic risk optimization in discounted MDPs. In Artificial Intelligence and Statistics (AISTATS), 2023.\n\n[3] Seungki Min, Ciamac C Moallemi, and Costis Maglaras. Risk-sensitive optimal execution via a conditional value-at-risk objective. arXiv preprint arXiv:2201.11962, 2022."}, {"review_id": "3MqbC8RlQU", "reviewer": "Reviewer_eWnC", "summary": "\nThe paper tackles the risk-level decomposition of risk measures in the finite Markov Decision Process (MDP). The work firstly points out the suboptimality of the decomposition proposed in prior works (Conditional-Value-at-Risk), by mathematically proving that the decomposition in CVaR does not maintain the equality to the optimal policy under policy optimization. \n\nThen the work mathematically proves the decomposition in Entropy-Value-at-Risk (EVaR) fails to find the minimum for the policy evaluation. Following that, the paper corrects the decomposition of EVaR and proposes a new dynamic program decomposition for Value-at-Risk (VaR). By avoiding the saddle-point gap in policy optimization, the new method remains optimal for both policy optimization and policy evaluation.\n", "questions": "N/A", "limitations": "Yes", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The method contributes to identifying the suboptimality in policy optimization and policy evaluation in prior methods (CVaR and EVaR). The paper points out the reason causing the suboptimality and proposes a new method for improvement. As the paper improves the correctness of the policy learning in risk-averse methods, the theoretical result can also be significant when people apply the risk-averse approach in practice.\n\nThe figures are clear and help with understanding the counterexamples.\n", "weaknesses": "I understand that the paper mainly focuses on theoretical analysis, and it makes sense to me that there is no empirical evidence for the correctness of the new method. One small suggestion is to add a numerical experiment. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and suggestions. Adding a numerical experiment is a good suggestion. In the final version of the paper, we will add a simple example that demonstrates how the duality gap translates into a sub-optimal policy. Please see the attached pdf with the global response, where we describe a small example that demonstrates numerically the gap in a simple MDP.  "}, {"review_id": "8mDujAQp1A", "reviewer": "Reviewer_tkg9", "summary": "The paper shows that the dynamic programming decomposition methods used in risk-averse MDP are suboptimal for CVaR and EVaR, but optimal for VaR. These findings seem important as such decomposition methods become increasingly popular recently. ", "questions": "- Please refer to the questions asked above.\n- Is there any way to numerically evaluate the suboptimality of the decomposition?", "limitations": "I do not see any negative societal impact from the paper. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The findings that the decomposition fails for CVaR and EVaR are of importance and interesting to see. ", "weaknesses": "The paper presents negative outcomes arising from the application of the decomposition method in CVaR and EVaR MDP. However, it does not offer a solution or rigorous analysis to address or evaluate these shortcomings. Particularly, in Theorem 3.2, the authors demonstrate that there exists a risk level where the equalities in (8) do not hold, indicating that the decomposition is suboptimal. While this finding is valuable, it raises crucial questions. For instance, under which parameter values does the optimality of the decomposition hold? If we randomly select a risk level from an interval, what are the chances of achieving optimal decomposition? Can we establish an upper bound on the loss incurred by using the decomposition? Is there an alternative form of decomposition that yields smaller losses? These questions hold significant relevance and would provide insights into handling the limitations.\n\nSimilar questions can be asked regarding the EVaR. Therefore, although the findings are noteworthy, the paper is not yet ready for publication. Further work on addressing the shortcomings of the decomposition method would significantly enhance the paper's quality.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive comments.\n\nFirst, we need to clarify a fact that the reviewer might have missed while reading the paper. Namely, both CVaR and EVaR do possess valid dynamic programming-based solution methods, as presented in Bäuerle and Ott. (2011) and Hau et al. (2023) respectively. We, therefore, disagree with the claim that the paper \"does not offer a solution\" to the identified shortcomings. In other words, a solution is to rely on alternative decompositions, which have strong theoretical foundations. We realize that this message might not have been clear and plan on reinforcing it in the conclusion of the revised paper.\n\nFor the case of VaR, we identified important technical issues with the analysis in Li et al. (2022) of its proposed dynamic programming decomposition. This is remedied in section 5 of our paper with a decomposition for the case $T=1$ that is rigorously supported. Based on the comments of reviewer bRij, we decided to include in the appendix of the revised version of the paper the implied theoretical result regarding the case of general $T>1$. This should provide a complete dynamic programming decomposition for the case of value-at-risk.\n\nBased on the discussion above, we therefore strongly disagree with the reviewer's claim that our \"paper is not yet ready for publication\". In its current form, our paper already demonstrates that a popular dual decomposition scheme that is used for CVaR and EVaR (and could continue to be deployed for other coherent risk functionals based on Pflug and Pichler (2016)) is suboptimal, thus encouraging the use of their alternate primal decomposition form, and rigorously identifies a decomposition scheme for VaR. Given the wide adoption of the problematic CVaR decomposition and the risk that reinforcement learning researchers or practitioners continue to incorrectly employ the decomposition presented in Pflug and Pichler (2016), this paper addresses important and timely objectives and successfully achieves them. Given that none of the reviewers has questioned the legitimacy of our mathematical claims, we can only conclude that it is indeed ready for publication.\n\nThis being said, we appreciate the constructive feedback that was provided and, while we believe some of the questions fall outside the scope of our work, we are happy to provide some high-level answers.\n\n**Under which parameter values does the optimality of the decomposition hold?**\nThe examples in Theorems 3.2 and 4.1 can be readily adapted to any risk level in $\\alpha \\in (0,1)$. In fact, the decompositions proposed by Chow et al. (2015) are only guaranteed to be optimal for $\\alpha = 0$ or $\\alpha = 1$, where the objective simply reduces to the expected value and the worst case, respectively. In contrast, the decomposition in Bäuerle and Ott. (2011) is optimal for all $\\alpha\\in[0,1]$.\n  \n**What are the chances of achieving optimal decomposition?** \nIt is not clear to us under what distribution the reviewer is interested in measuring a probability of optimal decomposition. One could, in fact, easily create a population of counterexamples for which the CVaR and EVaR decomposition would be sub-optimal with probability one. On the other hand, Min et al. (2022) claim to have identified a family of execution problems (a form of portfolio optimization) where the decomposition is exact (with probability one) due to the convexity of the objective with respect to the deterministic policy.\n    \n**Can we establish an upper bound on the loss incurred by using the decomposition?** \nUsing a simple scaling argument (on the rewards), the example in Theorem 3.2 shows that the error in worst-case risk estimation can be arbitrarily large, even when $T = 1$ Perhaps, one could establish an upper bound on the suboptimality error under a specific MDP structure, but it is not clear that this would be useful since the decomposition in Bäuerle and Ott. (2011) is exact. Please also refer to the example (Figure 2) in the attached pdf submitted along with the global response.\n    \n**Is there an alternative form of decomposition that yields smaller losses?**\nYes, see Bäuerle and Ott. (2011) and Hau et al. (2023) for CVaR and EVaR, respectively.\n    \n**Is there any way to numerically evaluate the suboptimality of the decomposition?**\nYes, by implementing the primal decomposition scheme presented in Bäuerle and Ott. (2011) and Hau et al. (2023). Note that in the latter, the authors provide a discretization scheme (for the continuous state variable) for which the estimation error can be bounded.\n\n**References**\n\n[1] Nicole Bäuerle and Jonathan Ott. Markov decision processes with average-value-at-risk criteria. Mathematical Methods of Operations Research, 74(3):361–379, 2011.\n\n[2] Yinlam Chow, Aviv Tamar, Shie Mannor, and Marco Pavone. Risk-sensitive and robust decision-making: A CVaR optimization approach. In Neural Information Processing Systems (NIPS),2015.\n\n[3] Jia Lin Hau, Marek Petrik, and Mohammad Ghavamzadeh. Entropic risk optimization in discounted MDPs. In Artificial Intelligence and Statistics (AISTATS), 2023.\n\n[4] Xiaocheng Li, Huaiyang Zhong, and Margaret L. Brandeau. Quantile Markov decision processes. Operations Research, 70(3):1428–1447, 2022.\n\n[5] Seungki Min, Ciamac C Moallemi, and Costis Maglaras. Risk-sensitive optimal execution via a conditional value-at-risk objective. arXiv preprint arXiv:2201.11962, 2022.\n\n[6] Georg Ch Pflug and Alois Pichler. Time-consistent decisions and temporal decomposition of coherent risk functionals. Mathematics of Operations Research, 41(2):682–699, 2016."}]

Author rebuttal:
We would like to take this opportunity to provide a holistic response to the reviewers' main questions and concerns below.

**Concern 1: Paper does not present a complete algorithm or numerical results**

This paper aims to correct the literature on risk-averse RL and retard the propagation of incorrect claims. As we discuss in detail in the introduction, numerous recent and well-cited papers in risk-averse RL are based on a fundamentally flawed technique; consequently, the central theorems of these papers are fundamentally incorrect. These fundamental errors that have been repeated in multiple papers are due to the fact that they devote only cursory attention to technical issues, which appear minor, but in the end, invalidate the approach. 

To achieve the paper's main goal, we decided to focus primarily on the errors in prior work for the following reasons. First, focusing on implementation concerns would limit our ability to discuss the technical flaws of prior work in sufficient detail. It would divert one's attention from the technical flaws that we are identifying. Second, the implementation concerns that we omit have been discussed widely in prior work. Finally, as we point out in the paper, we believe that the CVaR and EVaR methods we study here are fundamentally flawed, and our goal is to steer the community to more promising techniques based on the decompositions studied in Bauerle \& Ott (2011) and Hau et al. (2023).

We will make three improvements to address some of the concerns raised in the review. First, we will clarify some of the writing to more precisely point the interested reader where to find the implementation details. Second, we will include the general multi-stage version ($T > 1$) of the VaR Bellman function, which corrects for the incorrect definition of VaR in Li et al. (2022) and confirms that the supremum is both attained and deterministic in the optimal policy. 

**Theorem**. Given any finite MDP with horizon $T>0$ and $\alpha\in[0,1]$, we have 

$\max\_{\pi\in\Pi} \operatorname{VaR}\_\alpha^{\tilde a_t\sim\pi_t(\tilde s_t)}[\sum_{t=1}^T r(\tilde s_t, \tilde a_t, \tilde s_{t+1})]= \sup\_{\zeta\in \Delta(S)} (  \min_{s\in\mathcal{S}} \max_{a\in A } q_1(s,a,\alpha \zeta_s \hat p_s^{-1})  |  \alpha\cdot \zeta \leq \hat p )$.

with $q_{T+1}(s,a,\alpha) := 0$ if $\alpha<1$ otherwise infinity, and for all $1\leq t \leq T$:

$q_{t}(s,a,\alpha) :=  \sup_{\zeta\in\Delta(S)} (  \min_{s'\in\mathcal{S}} r(s,a,s')+\max_{a'\in A } q_{t+1}(s',a',\alpha \zeta_s p_{sas'}^{-1}) |  \alpha\cdot \zeta \leq p_{sa})$

Third, we will include a numerical example demonstrating the suboptimality of the decomposition. Please see the attached pdf for the diagram of the MDP and the plot of the CVaR returns of the optimal policy and the policy computed using the decomposition in Chow et al. (2015).

**Question/Concern 2: Is it possible to quantify the suboptimality of the decompositions for CVaR and EVaR?**

Our counterexamples indicate there is no immediate additive or multiplicative bound on the suboptimality in the CVaR and EVaR decompositions. This is analogous to the duality gap for non-convex optimization, which can be arbitrarily large, depending on the structure of the optimization problem. While the suboptimality gap of the methods may vanish for MDPs with some specific structure, we are not convinced that this question is worth pursuing at this point. We advocate in the paper for the use of algorithms proposed by Bauerle \& Ott (2011) and Hau et al. (2023), which do not suffer from the optimality gap issues and are conceptually and computationally simpler.

We concur with the reviewers that a numerical study of the decompositions would be valuable. However, given the number of implementation and domain choices one needs to make and analyze in the implementation of these algorithms, we concluded that a cursory numerical study would not add much value to this theoretical paper. The numerical performance of the risk-averse RL algorithms is driven by a large number of implementation decisions, such as how the augmented state space is discretized, what method is used to compute the decomposed Bellman update, which value function approximation technique is used (quantile regression or least squares on CDF).

Even though an extensive numerical is beyond the scope of this work, we hope that a small illustrative example can alleviate some of the reviewers' concerns. In the final version of the paper, we will add a simple example that demonstrates how the duality gap translates into a suboptimality of a policy. We attach the plot of the CVaR of the return for this simple MDP in the attached pdf.

**References**

[1] Nicole Bäuerle and Jonathan Ott. Markov decision processes with average-value-at-risk criteria. Mathematical Methods of Operations Research, 74(3):361–379, 2011.

[2] Yinlam Chow, Aviv Tamar, Shie Mannor, and Marco Pavone. Risk-sensitive and robust decision-making: A CVaR optimization approach. In Neural Information Processing Systems (NIPS), 2015.

[3] Jia Lin Hau, Marek Petrik, and Mohammad Ghavamzadeh. Entropic risk optimization in discounted MDPs. In Artificial Intelligence and Statistics (AISTATS), 2023.

[4] Xiaocheng Li, Huaiyang Zhong, and Margaret L. Brandeau. Quantile Markov decision processes. Operations Research, 70(3):1428–1447, 2022.

Meta-review: This paper deals with the sub-optimality of Dynamic Programming decomposition for risk measures like CVar and EVar.
The paper provides an interesting and significant contribution and is well-written and sound.
On the other hand, the reviewers raised some limitations about the limited number of risk measures considered and the lack of discussion about the scalability of the proposed decompositions.
The authors' rebuttals effectively solved most of the reviewers' issues, and even if they did not reach a consensus, there was a large support for accepting this paper.
The authors need to consider the reviewers' suggestions while preparing the final version of their paper.
Decision: Accept (poster)