Planning and Learning in Average Risk-aware MDPs
Authors: Weikai Wang
Erick Delage
Venue: NeurIPS 2025 poster ()
Keywords: average cost markov decision processes
dynamic risk measure
relative value iteration
Q-learning
reinforcement learning
Primary area: reinforcement_learning
TL;DR: This work presents planning and learning algorithms for average-cost MDPs with dynamic risk measures.

Abstract: For continuing tasks, average cost Markov decision processes have well-documented value and can be solved using efficient algorithms. However, it explicitly assumes that the agent is risk-neutral. In this work, we extend risk-neutral algorithms to accommodate the more general class of dynamic risk measures. Specifically, we propose a relative value iteration (RVI) algorithm for planning and design two model-free Q-learning algorithms, namely a generic algorithm based on the multi-level Monte Carlo (MLMC) method, and an off-policy algorithm dedicated to utility-based shortfall risk measures. Both the RVI and MLMC-based Q-learning algorithms are proven to converge to optimality. Numerical experiments validate our analysis, confirm empirically the convergence of the off-policy algorithm, and demonstrate that our approach enables the identification of policies that are finely tuned to the intricate risk-awareness of the agent that they serve.

Planning and Learning in Average Risk-aware MDPs
Weikai Wang!?
Erick Delage"?
GERAD & HEC Montréal (weikai. wang, erick. delake.ellge)@ihee @hec..a
Mila - Québec Al Institute
Abstract
For continuing tasks, average cost Markov decision processes have well- documented value and can be solved using efficient algorithms. However, it ex- plicitly assumes that the agent is risk-neutral. In this work, we extend risk-neutral algorithms to accommodate the more general class of dynamic risk measures. Specifically, we propose relative value iteration (RVI) algorithm for planning and design two model-free Q-learning algorithms, namely a generic algorithm based on the multi-level Monte Carlo (MLMC) method, and an off-policy algorithm ded- icated to utility-based shortfall risk measures. Both the RVT and ML. Q- learning algorithms are proven to converge to optimality. Numerical experiments validate our analysis, confirm empirically the convergence of the off- off-policy algo- rithm, and demonstrate that our approach enables the identification of policies that are finely tuned to the intricate risk-awareness the agent that they serve.
Introduction
For continuing tasks where there is need to optimize long term periodic payoff, such network control, supply chain designs, or maintenance problems (Puterman, 1994), average cost (or reward) Markov decision processes (MDPs) serve Barto, 2018; Naik et al., 2019) and can be solved using efficient algorithms. In the risk-neutral setting, different forms of value iteration algorithms co-exist (Puterman, 1994; Bertsekas, 2007) and some have been extended to model-free setting using Q-learning style algorithms (Abounadi et al., 2001; Wan al., 2021). The question of how formulate and solve average-cost MDPs however becomes challenging when the agent is considered risk sensitive. It originates from the pioneering work of Howard and Matheson (1972) and is covered in recent surveys such as Biswas and Borkar (2023) and Bäuerle and Jaskiewicz (2024).
crucial model in reinforcement learning (Sutton and
This work focuses average risk-aware MDPs, general formulation introduced in Shen et al. (2013) that attempts to find policy π that minimizes the long-term average of the risk of the cost process generated by æ. While the thcoretical foundations of this framework are well studied, find- ing efficient solution techniques to these problems remains a challenging task. To solve the average risk-aware MDP problem, one can apply the classic value iteration algorithm (Cavazos- Caninna and Montes-de Oca, 2003; Ruszczyriski, 2010; Shen et al., 2015). This approach relies on the iteration of the risk-aware Bellman operator and computes the average to obtain the optimal average risk. However, it is known to suffer from overflow issues when the number of iterations is large. In the resk-neutral setting, the relative value iteration (RVI) algorithm widely used (Bertsekas, 2007; Gupta et al., 2015), as it mitigates overflow issues during long iterations by subtracting a reference value for each state at every step. However, while some studies have explored RVI algorithms based on the entropic risk measure (Borkar, 2010; Arapostathis and Borkar, 2019; Hmedi et al., 2023), general formulation of the RVI algorithm for risk-aware MDPs remains missing in the literature.
Meanwhile, in practical applications, the environment is rarely known in full, highlighting the im- portance of developing model-free learning algorithms. To the best of our knowledge, extensions of the risk neutral Q-learnng algorithms to the average risk- setting appear to only exist for
39th Conference on Neural Information Processing Systems (NeurIPS 2025).

---

the case of entropic risk measure (see Borkar (2002), Borkar (2010), Moharrami et al. (2024) and the reference therein). This in sharp contrast to the extensive literature on algorithms for dis- counted or finite-horizon risk-aware MDPs, where many studies exist: for instance, see Chow and Ghavamzadeh (2014), Tamar et al. (2015), or Chow al. (2018) for conditional value-at-risk, see Huang and Haskell (2017), Köse and Ruszezyúski (2021), or Lam et al. (2023) for general coherent risk measures, Shen et al. (2014) or Marzban et al. (2023) for utility-based shortfall risk (UBSR), and see Hau et al. (2025) for quantiles. To conclude, the design of a model-free learning algorithm for average risk-aware MDPs with a general risk measure remains an open research field.
The literature most closely related to addressing this gap has focused on planning and learning al- gorithms for distributionally robust MDPs, leveraging the fact that coherent risk measures admit a worst-case expected value representation. Studies have explored the discounted case (Liu et al., 2022; Wang et al., 2023a, 2024) as well as the average case (Wang et al., 2023b,c), where an am- biguity set is constructed around the transition kernel to safeguard against potential distributional shifts. These results, however, do not apply to general classes of possibly non-coherent dynamic risk measures.
This paper presents planning and learning algorithms for average risk-aware MDPs with a general dynamic risk measure, We describe our contributions as follows:
1. Planning:
We propose a model-based RVI algorithm for average risk aware MDPs, which produces a policy that provably converges to the optimal policy for a general class of dy- namic risk measures. While existing studies on model-based algorithms for this problem focus either on the resk-neutral setting or the case of entropic risk, our work appears to be the first to consider such a general class of dynamic risk measures.
2. Learning: We introduce two novel model-free Q-learning algorithms for average risk- aware MDPs. The first one generalizes the multi-level Monte Carlo (MLMC) based Q- learning algorithm introduced in Wang et al. (2023c) for robust average MDPs to a broader class of dynamic risk measures, which may not necessarily be coherent, while ensuring provable convergence to optimality. The conditions that we impose for convergence weak and are satisfied by many popular risk measures such as UBSR, optimized certainty equivalent, and spectral risk measures. Additionally, we propose asynchronous algo- rithm that is specialized for UBSR and amenable to off-policy learning by waiving the need for resampling procedure. While the theoretical convergence remains open, we validate it empirically under different loss functions.
3. Empiries: We confirm empirically the convergence of all algorithms under different choice of risk measures and practically relevant sampling rates for MLMC Q-learning, and com- pare the sample efficiency. We also showcase how average risk-aware MDPs identify poli- cies that are tuned to the agents' preferences in popular environments from the literature.
The structure of the paper is as follows. Section 2 introduces average risk-aware MDPs. Section 3 introduces the model-based algorithms, including the risk-aware RVI and its generalization to Q- factors. Section describes the model-free algorithms, featuring a general Q-learning algorithm with MLMC and an asynchronous Q-learning algorithm specifically designed for UBSR. Section 5 presents the numerical experiments. Section concludes the paper and proposes further research. Pseudo-codes, proofs, and additional experiment details and results are provided in the appendix.
2 Preliminaries
Notations: Given any finite probability space (12, (92), P(-)). abbreviated as (2, P(-)), with Q finite set of outcomes, (I2) the power set of (sigma-algebra) and P(-) probability mass function in the probability simplex (S2), we denote by L()) the set of finite real-valued functions (a.k.a.
random variables) on Ω and [9] the cardinality of f2. For v, w E L()), the notation v 2 w refers to v(w)= 2 w(w) for all w E Ω and 2 w almost surely (a.s.) refers to v(w) 2 w(w) for all w E Ω such that P(w) > 0. The infinity norm of E L()) is |||||.0 == supwes |o(w)), while its span-seminorm is: ||ol|sp := max v(w:) min v(w). For A C Ω the indicator function I E A) equals if E and 0 otherwise. Finally, e and 0 represent the constant functions of one and zero respectively, while denotes the base of the natural logarithm.

---

2.1 Risk Maps
We begin by defining the notion of a risk measure following Shapiro et al. (2021).
Definition 2.1. Given finite probability space (S2, P()), a risk measure p: f((t) + R that maps random cost real value capturing its risk is said to be monetary it satisfies the following properties:
(1) (Monotonicity) p(u) S p(w) for all u, E ((2)) such that v S a.s.;
(2) (Translation invariance) p(u + X) = p(e) + for any R. v E C(N);
(3) (Normalization) p(0) 0;
further called convex if:
(4) (Convexity) For all a E [0, 11. E L(2), p(av + +(1 -1-a1 a))w z applv) + -a)p(w);
and coherent if
(5) (Positive homogeneity) For all X 2 0, e E C(9), p(xe)= Xp(e).
In the following, we introduce some popular kinds of risk measures that will be of interest.
Definition 2.2 (Definition 4.1 12, Föllmer and Schied (2016)). A risk measure on (S,, is called utility-based shortfall risk (UBSR) measure if it can be represented as:
SR(u) inf (m E R B(((v m)] 0} Ye L(2),
for some continuous non-decreasing convex loss function IR + R such that E(O) = 0.'
Example 2.3 (Expected value). When {(x) = æ, the UBSR measure reduces to the expected value, which we refer as the risk-neutral measure.
Example 2.4 (Entropic risk measure). When {(x) - with 3 representing risk sensi- tivity, the resulting UBSR measure is the entropic risk measure SR(v) log(BBeBer))
Example 2.5 (Expectile). Following Bellini and Bignozzi (2015). the expectile is the only coherent UBSR, defined using the loss function f(x) -ω. (1 ->>= where [0, 1] represents the degree of risk aversion. This measure spans from the essential infimum of the random cost at = 0 its essential supremum at 7 passing through the expected value 7 0.5.
Definition 2.6 (Definition 2.1, Ben-Tal and Teboulle (2008)), risk measure on (2, P(-) is called an optimized certainty equivalent (OCE) risk measure if it can be represented as
OCE(.) inf (E Bie(u E)},, EER.
Yu L(L),
for some nondecreasing comvex loss function E. R -> such that E(O) = O and E @E(O), where OE(0) is the subgradient of f at O.
Definition 2.7 (Definition 3.1, Acerbi (2002)). risk measure on (Ω, P(-) called a spectral risk measure associated to a risk spectrum fincctionn o : [0, > [0, oo) such that fo o(3)d3 = 1, if can be represented as
M*(N) = I ((3)F Vu E (()))
where F, the cumulative distribution function of and F.- (3) = inf(m E R F.()) 2 3).
Example 2.8 (Conditional -alue-at-Risk). When {(x) = (1 (1-a) (1--a)_121 -1,+ for a E (0, 1), the OCE risk
the conditional Value-at-Risk (CVaR) level a. CVaR is coherent and it is also spectral risk measure with risk spectrum x{3) = (1 -113
[ 2 a).
Example 2.9 (Mean-CVaR) When @(3) + (1 - m) - a) 1118 2 a} for some E (0, 1), the spectral risk measure defined as Mv)w) = T|][ + (1 Ca.R. (v) is referred to as the mean-CVaR risk measure.
Shen et al. (2014) employs equivalently Ble(v m)] < mo using the replacement f(z) == E(z) ma- We also focus normalized UBSR.
3

---

2.2 Average Risk-aware MDPs
We consider a finite MDP defined through the tuple AA c, zu), where X and AA are finite state and action spaces, denoting IC == X' x A for short. The transition kernel P : X' x A + (X)) specifies the probability P(y|z, a) of transitioning from state I state y given action a. The bounded cost function is defined as X' x A - [-C, CJ. For time / = 0. 0,1,..., the state and action are 3y and at, governed by a Markov policy π = (TT, TI,...), with each ne E == { X' + (AA), where Te (e(-(ara) denotes the probability of choosing given It. A policy is called deterministic if assigns a probability of one to specific action for each state, and is called stationary if ne = π for all é for some II.
In risk-neutral setting, the infinite horizon average cost MDP problem takes the form:
(ACMDP) J= inf lim limsup
7
Σ xH (X.)
TEll T-x
where X₂ is the state at stage and c" (z)x :- EnEA T (alx))((z, a). One seeks to identify stationary policy that minimizes the long term average expected total cost generated by the MDP, when starting from some initial state Xo and following policy π.
Following Shen et al. (2013), we consider the risk-aware version of the average cost MDP by placing E[-] with a class of dynamic risk measures that is specially designed for MDPs.
Definition 2.10. A risk map R is function that maps each state (x, a) K. to a monetary risk measure on the space (X, P(1æ2 a)). Furthermore, for any т E II we define R (vlz) := To simplify notation, sometimes write Rz,((v) == R(v|z,a) and
EeeA (r) = Rd (u/z).
We first consider risk-aware T-stage total cost problem and define our risk-aware objective as follows: JT(T) == e c=x((o (Xo) + Rxx (X1) + +... + Rx - (c (xx)) ...)) ). The infinite horizon average risk-aware MDP problem therefore seeks to find a policy π that minimizes
(ARMDP) J == inf Joo (TT)
#Ell
where Joo(T) := lim supr (T)). It is easy to see that ARMDP reduces to ACMDP when R.,a(1)) Ez,a [u] E[u(y)] with y a()
Remark 2.11. As argued in Shen et al. (2013), preserving the Markov property is essential to guarantee stationary optimal policies for infinite horizon objectives (Ruszczyúski and Shapiro, 2006; Shen et al., 2013). Therefore, we restrict our attention to Markovian risk measures that depend only on the current state. Readers refer to Ruszczyíski (2010) for broader framework.
2.3 Average Risk Optimality Equation
Shen et al. (2013) establishes several assumptions on the risk maps of an MDP guarantee the existence and uniqueness of the optimal average risk for ARMDP. Here, we modify and adapt these assumptions to suit our setting of finite MDP.
Assumption 2.12 (Doeblin type condition, Assumption 5.4, Shen et al. (2013)). There exists coherent risk measure v L(X) + R. and some constant E (0, 1) such that for all 2 o' L(X'), we have ex (R(u|z,a) ōv(() - R(v'(ar,) a) + av('') 2 0.
Assumption 2.12 defines form of ergodicity property of each state under the risk map. In Shen et al. (2013), v is not necessarily required to be coherent, whereas we impose this condition here for simplicity in the subsequent derivations.
From Shen al. (2013), if the risk maps satisfy Assumption 2.12, then there exists an optimal stationary deterministic Markov policy πt" such that J = (T)").). We restate the result as follows.
Theorem 2.13 (Theorem 5.9, 5.10, Shen et al. (2013)). Under Assumption 2.12, there exists unique 9 E TR. and an h² E L(x') satisfying the average risk optimality equation (AROE):
+ h(x)= min(c(=, R(hlz, a)}.
(2.1)
aEA
Moreover, 9" =-= J for the stationary deterministic policy nं (alar) = la = a" (x)),
where a" (x) minimizes c(2, a) R(h"" |x, a), and g" is independent of xo-

---

Remark 2.14. In Assumption 5.4 of Shen et al. (2013), an additional Lyapunov-type condition introduced, which imposes a growth constraint using a nonnegative weight function W. This condition can be dropped in a finite MDP, see Appendix B.1.
Remark 2.15. Assumption 2. is sufficient condition for the existence of an optimal average risk independent of the initial state and is stronger than the unichain assumption commonly used in risk- neutral average MDPs. It is well-known that for risk-aware MDPs, the unichain assumption alone does not guarantee this independence. For specific risk measures, such as the entropic risk measure, this condition can be relaxed to require only that the Markov chain is irreducible and aperiodic under all stationary policies (see Cavazos- of risk measures considered in this work, Assumption 2.12 is restricted to ergodicity condition on the underlying Markov chain, together with a condition on the loss function for UBSR and OCE, and the risk spectrum for the spectral risk measure (see Theorem 4.10).
and Fernández-Gaucheree Gaucherand (1999)). For the three types
3 Model-based Algorithms
In this section, we propose a risk-aware version of the RVI algorithm to solve the ARMDP problem. Additionally, lay the foundation for the Q-learning algorithm in the next section, we introduce risk-aware relative Q-factor iteration algorithm as generalization of the risk-aware RVI algorithm.
3.1 Risk-aware Relative Value Iteration
Following Abounadi et al. (2001), the risk-neutral RVI algorithm is defined
Vn+1 (x) == min E [c(2, + V.l - fVV),, Vx E X,
(3.1)
aEA
where V, E C(X) and Vo is arbitrarily initialized, and f L(x) - IR is a function that satisfies conditions discussed below, e.g. f(v) v2ro).² Using general function f(V.. instead of V (xx) allows the RVI algorithm to eliminate the need for a reference state, making it more flexible and efficient for computation (also see the discussion in Wan al. (2021) for the risk-neutral case). is known that under the unichain assumption, the rest-neutral RVI algorithm converges to a unique V and g" f(V*).
V*, which solves the resk-neutral version of the AROE using
We propose extending the RVI algorithm to the risk-aware setting by replacing the expected value operator with an appropriate risk map. This gives rise the following risk- RVI algorithm:
(x+1 = ((V f(W,), Va E X,
(3.2)
where 9 L(X) + ((X) is the awske Bellman optimality operator, defined as G(v)(x) (c(2, min ( + v) for all X and e E L(X).
=
To guarantee convergence of algorithm (3.2), we impose the following conditions on f-
Assumption 3.1. The function C(x) + R satisfies:
(1) For any X e R and E [(X). f(0) 0, f(u -)= f(v) X. (2) f is Lipschitz, i.e., 3ं. 0, such that [l - f(w)]l i.| w||o,, Vu, w E L(X).
Assumption 3.1 is equivalent to imposing that f is translation invariant and is naturally satisfied by f() == u(zo). Such extension for the RVI seems to be first proposed Abounadi et al. (2001) for the risk-neutral case, although the authors did not include proofs of their validity.
The following theorem confirms that convergence of RVI remains valid in the risk- setting.
Theorem 3.2. Under assumptions 2.12 and 3.1, the risk-aware RVI algorithm (3.2) converges to a unique fixed point V*, which identifies, using h² hx) (x) and g" == f(V"), a solution to the AROE (2.1).
Clearly, the risk-aware RVI algorithm (3.2) reduces to RVI algorithm (3. in the risk-neutral setting.
'The RVI algorithm in Bertsekas (2007), for example, replaces f(V.) with f(V.41) = Va (Zo) We adopt the formulation from Abounadi et al. (2001) as it better suited for designing Q-learning algorithm.
5

---

3.2 Risk-aware Relative Q-factor Iteration
The raske RVI algorithm (3.2) suggests that, when letting 12,1(2,0) a) == R2, ( a) + Vv,) f(V.), (3.2) can be reformulated as the following risk-aware relative Q-factor iteration (RQI):
Qu+I(E; a) = Razaa (c(x, a) min
Qn(;aa)) -
min a'EA
Qu( Qu(:.a)) V(z, a) E K.
a'EA
where Qn E ((K) and Qo is arbitrarily initialized. As suggested in Abounadi et al. (2001) for the risk-neutral case, this can more generally defined as:
Qu+1(2r a) H(Qn)(a, ((Qnn) V(r, E
(3.3)
where H. ((K) + C(C) is the risk-aware Bellman optimality operator for Q-factors, defined as (z))( a) == (c(a, a) + m a(), for all (z, a) X and g E C(C). With slight abuse of notation, here define f L(K) - IR and impose the following assumptions.
Assumption 3.3. The function f [(C) + R. satisfies:
(1) For any X E IR and q E [(K), f(0) 0, f(q + A) f(1)= A.
(2) f is Lipschitz, i.e., 3L such that llf(p) fl L|lp gl vp.q E C(K).
Common choices for f can be [(g
q( ao), f(4) min, g(z0, a), f(g)
[xT| Exo ((x,a) Similar to Theorem 3.2, we have the following convergence and optimality result for the risk-aware RQI algorithm.
Theorem 3.4. Under assumptions 2.12 and 3.3, the risk-aware RQI algorithm (3.3) converges to a unique fixed point Q2" which identifies, using h (x) m Q" (z, a) and g" f(Q"), solution to the AROE (2.1).
Theorem 3.4 also suggests that solution to the AROE (2.1) can be identified by solving the follow- ing average risk optimality equation based on the Q-factor:
d'EA (x a) Rz,0 (dls,a) min g(. o1) -((),, EK C(K).
(3.4)
Model-free Algorithms
In this section, we propose model-free Q-learning algorithms for solving the ARMDP We begin by showing that almost sure convergence can be achieved when an unbiased estimator of the risk- aware Bellman optimality operator is available. In particular, we describe how such an estimator can be constructed using the multi-level Monte Carlo method. In addition, we introduce Q-learming algorithm tailored UBSR that avoids the need for an estimator.
4.1 Risk-aware RVI Q-learning
Motivated by the risk-aware RQI algorithm (3.3), we can propose the following model-free risk- aware RVI Q-learning algorithm:
Q1+ a) = (n, a) + (()) ()) -(Qu)).))
(n( (x. EK, (4.1)
where 7l is an estimator for the awsk- Bellman optimality operator H. and 7(n) is some step size. We construct H()g) as estimator of H(gg) satisfying the following assumption.
Assumption 4.1. The estimator H is unbiased and has controllable variance: [[]A(1)] = H(g)
and there exists a C > such that VarlFi(g)(x; a)] S C(1 + IlllB)), V(s,a) E K. E L(K))
To guarantee the convergence for the risk-aware RVI Q-learning algorithm (4.1), we require that the risk map satisfies an assumption called "asymptotic coherence" and the function f is homogeneous. We also impose the Robbins-Moon Monro condition on the step size y(n).
Assumption 4.2 (Asymptotic coherence). The risk map R is asymptotically coherent, i.e., there exists a risk map R such that for all (x. a) E K, we have that lim RZza(sv) = R (v) for all E L(X) and uniformly on all compact subsets of L(X).

---

Assumption 4.3. The function f is homogeneous, i.e., f(Ao) = Xf(e). KA E, DE ((K). Assumption 4.4. The step size {r((n) satisfies 2n ((n = 2o and Σn (n)2 0c.
We then have the following convergence result.
Theorem 4.5. Under assumptions 2.12, 3.3, 4.1, 4.2, 4.3, 4.4, then almost surely, On converges some Q", and h² (z) m Q" a), 9" := f(Q*) identify a solution to the AROE (2.1).
The greedy policy, Tn Tn(a(x) == 1{a 0, ( with a (x) E arg minae Qu a), also converges almost surely an optimal stationary deterministic policy of ARMDP.
If the risk map R coherent, Assumption 4.2 is automatically satisfied. This assumption is made for technical reasons, as the convergence proof of the Q-learning algorithm for the average MDP relies on ODE-based stochastic approximation (see Abounadi et al. (2001) and Wan al. (2024) for a recent review). This approach requires the limit in Assumption 4.2 to exist for analyzing the almost sure boundedness of the iteration sequence. In the next subsection, we demonstrate that this assumption can be achieved for many risk maps that are not necessarily coherent.
4.2 Construction of an Unbiased Estimator H
In this subsection, we present an estimator H that satisfies Assumption 4.1 for specific risk maps using the multi-level Monte Carlo (MLMC) method, approach for unbiased statistical estimation using stochastic simulation (Blanchet and Glynn, 2015; Blanchet et al., 2019; Liu et al., 2022; Wang al., 2023a,c). We first impose the following assumption on R. which enables the possibility of estimating a random variable using its empirical distribution.
Assumption 4.6 (Hölder continuity). There exists an & 0 such thatfor all v, E L(X), we have (Rz,((v) - Re (w) < Ldw (Wes (w), V(z, a) E K., where pv- pw are the probability distributions o and w on (X, P(-1z, a)) and dw )) is the I-Wasserstein distance between two distributions.
We first generate N according each (x,aa) E K. we take action a at state x for 2 times and observe the i.i.d. transitions {=()==1 2 These 2 samples are then divided into two groups: samples with odd indices and samples with even indices. We calculate the empirical distribution of x' using the even- even-index sam- ples, odd-index samples, all the samples, and the first sample: i (y)x, a) == E 1
geometric distribution with parameter r (0, 1). Then, for
y). Po P (w|x, a) = I Din 1 = y}. P a) = अपFT Σi=1 1( = v). PN+10112, 22 a) 1( v}. For notation simplicity, we denote the resulting empirical transi- PN+1 and Pk respectively. Then, we use these estimated transition
tion kernels as + Po+1. kemells as nominal kernels to calculate H. Namely, Hp, is the Bellman optimality operator under the empirical transition kernel PN. The multi-level estimator of H is then defined as { (M (g) - 1
{
(Hig (4) + Hpp {
:(()) = H Hpp... (q) + PN
Vq E C(K), (4.2)
where P.v := -11-r)
We present the following result on the unbiasedness and controllable variance for risk maps satisfy- ing Assumption 4.6.
Theorem 4.7. Assumption 4.1 holds if the risk map satisfies Assumption 4.6 and r E (0,
As shown in Section 3 of Prashanth and Bhat (2022), several popular risk measures, including UBSR, OCE and spectral risk measures, satisfy Assumption 4.6 with proper parametrization. Below, we demonstrate that under suitable conditions, the average risk-aware MDP that incorporates UBSR, OCE, or spectral risk measure satisfies all the assumptions required for Theorem 4.5 to apply.
Assumption 4.8 (Strong ergodicity). Under any stationary policy, the resulting Markov chain is irreducible and there exists a state X such that P P(ž|z, fe)zzo a) > 0, V(z, a) E K.
Assumption 4,9 (Bounded slope). The loss function E(x) is strictly increasing on RR and there exist & > 0 such that 0 < 5 f(z)-fly) < L1, Vx y R. x-y Theorem 4.10. Under Assumption 4.8, the risk map employs UBSR or OCE satisfying Assump- tion 4.9 4.9, or a spectral risk measure with 0 < e2 S x(-) S To2 < 0o, then assumptions 2, 12, 4.2 4.2, and 4.6 hold. Consequently, Theorem 4.5 applies.
7

---

We note that CVaR does not satisfy the condition in Theorem 4.10. However, the mean- -VaR risk measure. which mixes expectation and CVaR, does and hence Theorem 4.5 applies for mean- CVaR. Also, although our definitions of UBSR and OCE assume a convex loss function, Theorem 4.10 holds more generally for loss functions that are convex (concave) for x > 0 and concave (convex) for x < 0, reflecting different risk attitudes toward gains and losses (see Appendix B.4). Finally, the entropic risk measure does not satisfy Assumption 4.9, but it still meets Assumption 2.12 (Proposition 5.7, Shen et al. (2013)). Borkar (2002) proposed Q-learning algorithm for average risk-aware MDPs with an entropic risk measure, which is derived from the multiplicative Poisson equation and does not rely on MLMC. For further details, readers may refer to Borkar (2002).
4.3 An Off-policy Q-learning Algorithm for UBSR Measures
An important practical concern of our MLMC Q-learning algorithm is the necessity for a resampling procedure for each (ar, a) pair, which prevents the algorithm from being adapted for off-policy learn ing. This can be addressed when the risk map employs a UBSR measure using an approach proposed in Shen al. (2014) for risk-aware discounted MDPs. Namely, Proposition 4.113 in Föllmer and Schied (2016) establishes that for any E [(²', the risk map SR (v) is the unique solution of E levo SR (v))] = O. This implies that the AROE (3.4) can be equivalently rewritten as:
E & (((x,a) + min q( f(a) f(a) q( -(2)) a(2,a)) .)
a))] =0, V(x, (x
d'EA
This motivates the following off-policy algorithm that seeks to identify the root of this AROE using stochastic approximation (see Borkar (2008)). Specifically, given any sequence {(xps Onz on, z²,)), ). with
I'n ~ P(- a), the asynchronous UBSR- basee Q-lcarning consists in applying the updates:
Qn+1(En, am) = Qu (n)) +n)+ ((ll)))(((((nnn))) an) min Qn (n(2',, f(Q)))(())))))))))))))))))))))) -(Q))))(nnn an)) (4.3)
min a'EA
where each subsequence (y(m)) mnd (x,,)) indexed by (x, E KC, satisfies Assumption 4.4. The synchronous algorithm can also derived if all (xr, a) pairs are updated within one iteration.
It shall be noticed that the thcoretical convergence of this algorithm remains an open question. Drawing from the ODE analysis used in the risk-neutral case, the corresponding ODE for (4.3)
involves a high-dimensional, nonlinear system that is difficult to analyze for stability. Additional discussion on this problem can be found in Appendix C.2.
Experiments
In this section, we provide numerical experiments confirming the convergence of our MLMC-based Q-learning algorithm (MLMC Q-learning), comparisons to the off- off-policy Q-learning algorithm for UBSR (UBSR Q-lcarning), and upply our algorithm (see pseudo-codes in Appendix A) to real-life problems to showcase its potential. Further details and experimental investigations are also presented in Appendix C. namely regarding the sensitivity of MLMC Q-learning to r, the convergence of UBSR Q-learning, and the effect of risk-awareness in long term performance of policies.
5.1 Convergence of MLMC Q-learning
We begin by validating the convergence of the risk-aware RVI Q-learning algorithm (4.1) using a randomly generated MDP with 10 states and 5 actions per state. The nominal transition kernel P is generated from a uniform distribution over [0, 1] and subsequently normalized. The cost function
sampled from a normal distribution N(1, 1). We choose 7(n) == (1/(n + 1))2/3 and f(4)) =
[x|| Ex, q(2;, a). Due to space limit, only show the convergence results for two special cases
of UBSR and OCE: the expectile with 5 = 0.75 and OCE with loss function {(x) == 2 72 where 7/1 2 and 7/2 0.5.
We run the MLMC Q-learning algorithm 100 times independently with r = 0.49 and plot the mean value of f(Qx) in Figure 5.1, with the 95th and 5th percentiles as the confidence interval (CI). For comparison, trajectories from value iteration and the risk-aware RVI algorithm (3.2) are shown together with the true optimal risk (via value iteration). It is evident that the MLMC Q-learning
8

---

Expecill T- 0.7.,
HINC OCT 95 2,10 0.5.
6.-
3.8
GE: by Helidio
0.8
Di Oelern mo
Dri by Giiamm eg ICE
02
0.2
0.0
14
Figure 5.1: Convergence experiments for risk-aware RVI (3.2) and MLMC Q-learning (4.1).
algorithm converges to the true optimal average risk almost surely. As model-based approach, the risk-aware RVI achieves convergence to the optimum at a significantly faster rate.
It is worth noting that selecting r E (0, 1/2) does not ensure finite sample guarantees based on The- orem 4.7, as each iteration requires an average of infinitely many samples when S 1/2. However, for some E (1/2, 3/4), both asymptotic and finite sample guarantees may still be achieved as ob- served empirically
additional experiments presented in Appendix C.I. These empirical findings coherent with the guarantees identified in Wang et al. (2023a) for special class of distribution- ally robust discounted MDPs.
5.2 Comparisons of MLMC and UBSR Q-learning Algorithms
Figure 5.2 presents the convergence of the synchronous and asynchronous UBSR Q-learning al- gorithms for the expectile in the same setting outlined in Section 5.1. For comparison, we also include the results of the MLMC Q-learning algorithm (4.1)) with r = 0.6, which uses an expected 6,000 samples per state-action pair over 1,000 iterations, corresponding to 300,000 iterations of the asynchronous UBSR Q-learning algorithm (4.3) and 6,000 iterations for the synchronous version.
Bat ti 201
Moard
40.0
Figure 5.2: Comparison of MLMC and UBSR Q-learning with equivalent number of samples.
Further experiments with different loss functions along with a detailed discussion and comparison to the MLMC Q-learning algorithm (4.1) are provided in Appendix C.2. While the MLMC Q- learning algorithm offers provable convergence to optimality, the two UBSR Q-learning algorithms (4.3) demonstrate both faster convergence and lower variance compared to the MLMC Q-learning algorithm (4. Investigating the almost sure convergence and optimality of this algorithm remains an interesting direction for future research.
5.3 Applications
To illustrate the practicality of our risk-aware algorithms, we tested them on three popular average- cost MDP problems: machine replacement (MR), water reservoir management (WR), and inventory management (IM) (e.g. Puterman (1994), Hernández-Lemme
(1989).. Each problem is evaluated under four risk measures: expectile (EX, r 0.9), OCE (71 2, 72 0.5), mean-CVaR (1) = 0.1,a a 0.2) and risk-neutral (RN). The optimal policies for each risk measure are obtained using the risk-aware RVI algorithm. Experimental details are provided in Appendix C.3.

---

Table 5.1 reports the optimal average risk for the three applications across the four risk measures, as well as the average risk of the four awsk- policies when evaluated under the expectile risk measure with = 0.9, i.e., the average risk computed under the expectile risk measure using the optimal policies derived for the other risk measures. It can be observed that the policies produced by our algorithms successfully attain their respective optimal average risks under difference application settings. Appendix C.4 explores risk differences across т values, showcasing UBSR's s flexibility in risk preference design. These results confirm our theory, proving the effectiveness of our algorithms in computing optimal risk-aware policies tailored to an agent's risk preferences.
Table 5.1: Average risk under different risk measures for three experimental setups: machine re- placement (MR), water reservoir management (WR), and inventory management (IM)
Optimal Risk
Expectile Risk
Risk Measures
MR
WR
IM
MR
WR
IM
EX
68.7499
20.2541
24.8694
68.7499
20.2541
24.8694
OCE
63,9291
14.1389
23.7330
68.9323
20.3239
25.2908
Mean-CVaR RN
59.5244
9.9319
22.8955
69.3343
20.6413
26.5721
54.4233
7.6174
20.1345
69.9359
20.6413
28.1901
Conclusion and Future Research
In this paper, we introduced the first aisk- RVI algorithm and two novel model-free risk-award RVI Q-learning algorithms for average-cost MDPs. MLMC Q-learning can be applied with a more general class of risk measures, while requiring access to repeated samples of transitions from a given state-action pair. UBSR Q-learning more closely aligns with the traditional setting of Q-learning yet dedicated to the class of UBSR measures.
Several research directions are worth exploring. First, we conjecture that the strong ergodicity As- sumption 4.8 could be weakened. Second, establishing sinite-sample guarantees for MLMC Q- learning remains an open problem. It would be interesting to examine whether the conditions in Wang et al. (2023a) for a specific class of distributionally robust discounted MDPs and the variance reduction techniques in Wang et al. (2024) can be extended to our framework. Third, the almost sure convergence of UBSR Q-Jearning should be addressed. Finally, exploring the applicability to large-scale problems and designing other types of reinforcement learning algorithms for average risk-aware reinforcement learning constitute important directions for future research.
Acknowledgments
The authors are grateful to the anonymous reviewers for their valuable feedback and insightful com- ments. Erick Delage was partially supported by the Canadian Natural Sciences and Engineering Research Council [Grant RGPIN-2022-052611 and by the Canada Research Chair program [950- 230057]. We are also thankful to Esther Derman, Marek Petrik and Xian Chen for valuable discus- sions on related topics.
References
J. Abounadi, D. Bertsekas, and V. S. Borkar. Learning algorithms for Markov decision processes with average cost. SIAM Journal on Control and Optimization, 0ttt:taaioooo43338811111---111 40(3)x681-698, 2001.
C. Acerbi. Spectral measures of risk: A coherent representation of subjective risk aversion. Journal of Banking & Finance, 1505):1555-151 2002.
A. Arapostathis and V. S. Borkar. On the relative value iteration with risk-sensitive criterion. arXiv preprint arXiv:1912.08758, 2019.
N. Bäuerle and A. Jaskiewiez. Markov decision processes with risk-sensitive criteria: an overview. Mathematical Methods of Operations Research, 191171141-178 2024.
10

---

F. Bellini and V. Bignozzi. On elicitable risk measures. Quantitative Finance, 15(5):725-77) 733, 2015.
A. Ben-Tal and M. Teboulle. An old-new concept of convex risk measures: The optimized certainty equivalent. Mathematical Finance, 17(2):449-4y) 476, 2008.
D. P. Bertsekas. Dynamic Programming and Optimal Control, 3rd Edition, Volume II. Athena Scientific, Belmont, MA, 2007.
A. Biswas and S. Borkar. Ergodic risk-sensitive control a survey, Annual Reviews in Control, 55:1 2023.
H. Blanchet and W. Glynn. Unbiased Monte Carlo for optimization and functions of expecta- tions via multi-level randomization. In 2015 Winter Simulation Conference (WSC), pages 3656- 3667. IEEE, 2015.
H. Blanchet, P. W. Glynn, and Y. Pei. Unbiased multilevel Monte Carlo: Stochastic optimization, steady-state simulation, quantiles, and other applications. arXiv preprint
2019.
V. S. Borkar. Q-learnig for risk-sensitive control. Mathematics of Operations Research, 27(2): 294-311, 2002.
V. S. Borkar. Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge University Press, 2008
V. S. Borkar. Learning algorithms for risk-sensitive control. In Proceedings of the 19th International Symposium on Mathematical Theory of Networks and Systems-MTNS, pages 1327-1332, 2010.
V. S. Borkar and S. Meyn. The O.D.E. method for convergence of stochastic approximation and reinforcement learning. SIAM Journal Control and Optimization, 38(2):44-469) 2000.
V. S. Borkar and K. Soumyanatha. An analog scheme for fixed point computation. I. TTheory IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, 44(4):351-355, 1997.
R. Cavazos-Cadena and E. Gernannez-Gaucchaaadd Controlled Markov chains with risk-sensitive criteria: Average cost, optimality equations, and optimal solutions. Mathematical Methods of Operations Research, 49:299-324, 1999.
R. Cavazos-Cadena and R. Montes-de Oca. The value iteration algorithm in risk-sensitive average Markov decision chains with finite state space. Mathematics of Operations Research, 28(4):752- 776, 2003.
Y. Chow and M. Ghavamzadeh. Algorithms for CVaR optimization in MDPs. In Advances in Neural Information Processing Systems, volume 27, 2014.
Y. Chow, M. Ghavamzadeh, L. Janson, and M. Pavone. Risk-constrained reinforcement learning with percentile risk criteria. Journal of Machine Learning Research, 18(167):1-51, 2018.
N. Fournier and A. Guillin. On the rate of convergence in Wasserstein distance of the empirical measure. Probability Theory and Related Fields, 162(3):077773, 2015. 2015.
H. Föllmer and A. Schied. Stochastic Finance; An Introduction in Discrete Time, 4th Edition. Walter de Gruyter & Co., Berlin, 2016.
A. Gupta, R. Jain, and P. W. Glynn. An empirical algorithm for relative value iteration for average- cost MDPs. 2015 54th IEEE Conference on Decision and Control (CDC), pages 5079-5084, 2015.
I.. Hau, E. Delage, E. Derman, M. Ghavamzadeh, and M. Petrik. Q-learning for quantile MDPs; A decomposition, performance, and convergence analysis. In International Conference on Artificial Intelligence and Statistics, 2025.
O. Hernández-Lerma. Adaptive Markov Control Processes. Springer Science Business Media, 1989.

---

H. Hmedi, A. Arapostathis, and G. Pang. On the global convergence of relative value iteration for infinite-horizz risk-sensitive control of diffusions. Systems Control Letters, 171:105413, 2023.
R. Howard and J. Matheson. Risk-sensitive Markov decision processes. Management Science, 18(7):356 369, 1972.
W. Huang and W. B. Haskell. Risk-aware Q-learinn for Markov decision processes. In 2017 IEEE 56th Annual Conference on Decision and Control (CDC), pages 4928-4933. IEEE, 2017.
U. Köse and A. Ruszezyúski. Risk-averse learning by temporal difference methods with Markov risk measures. Journal of Machine Learning Research, 22(38):1-34, 2021.
T. Lam, A. Verma, B. K. H. Low, and P. Jaillet. Risk-aware reinforcement learning with coherent risk measures and non-linest function approximation. In The Eleventh International Conference Learning Representations, 2023.
Z. Liu, Q. Bai, Blanchet, Dong, W. Xu, Z. Zhou, and Z. Zhou. Distributionally robust Q- learning. In Proceedings of the 39th International Conference Machine Learning, pages 13623.13643. PMLR, 2022.
S. Marzban, E. Delage, and J. Y. Li. Deep reinforcement learning for option pricing and hedging under dynamic expectile risk measures. Quantitative Finance, 23(10): 1411-1411,, 2023.
M. Moharrami, Y. Murthy, A. Roy, and R. Srikant. A policy gradient algorithm for the risk-sensitive exponential cost MDP. Mathematics of Operations Research, 0(0), 2024.
A. Naik, R. Shariff, N. Yasui, H. Yao, and R. S. Sutton. Discounted reinforcement learning is not an optimization problem. arxiv preprint arXiv: 1910.02144 2019.
L. A. Prashanth and S. P. Bhat. A Wasserstein distance approach for concentration of empirical risk estimates. Journal of Machine Learning Research, 23(238):1-61, 2022.
M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley- Interscience, 1994.
A. Ruszczyíski. Risk-averse dynamic programming for Markov decision processes. Mathematical Programming, Series B, 125:235-261, 2010.
A. Ruszczyúski and A. Shapiro. Conditional risk mappings. Mathematics of Operations Research, 31(3):544-561, 2006.
A. Shapiro, D. Dentcheva, and Ruszezynski. Lectures on Stochastic Programming: Modeling and Theory, 3rd Edition. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2021.
Y. Shen, W. Stannat, and K. Obermayer. Risk-sensitive Markov control processes. SIAM Journal on Control and Optimization, (((5):3652-3677 2013.
Y. Shen, M. Tobia, T. Sommer, and K. Obermayer. Risk-sensitive reinforcement learning. Neural Computation, 26(7):1298-1322 2014.
Y. Shen, K. Obermayer, and W. Stannat. On average risk-sensitive Markov control processes. arXiv preprint 403 2015.
R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA, 2018.
A. Tamar, Y. Glassner, and S. Mannor. Optimizing the CVaR via sampling. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
Y. Wan, A. Naik, and R. S. Sutton. Learning and planning in average-reward Markov decision processes. Proceedings of the 38th International Conference on Machine Learning, pages 10653-10662. PMLR, 2021.
12

---

Y. Wan, H. Yu, and R. S. Sutton. On convergence of average-reward Q-learning in weakly commu- nicating Markov decision processes. arXiv preprint arXiv:2408. 16262, 2024.
Wang, N. Si, J. Blanchet, and Z. Zhou. A finite sample complexity bound for distributionally robust Q-learning. In International Conference Artificial Intelligence and Statistics, pages 1370-3398, PMLR, 2023a.
S. Wang, N. Si, J. Blanchet, and Z. Zhou. Sample complexity variance-reduced distributionally robust Q-learning Journal of Machine Learning Research, 25(341):1-77, 2024.
2024.
Y. Wang, A. Velasquez, G. K. Atia, A. Prater-Bennetee and Zou. Robust average-reward Markov decision processes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 15215-15223, 2023b.
Y. Wang, A. Velasquez, G. K. Atia, Prater-Bennette, and S. Zou. Model-free robust average- reward reinforcement learning. In Proceedings of the 40th International Conference on Machine Learning, pages 36431-36469. PMLR, 2023c.
13

---

Appendices
A Algorithm Pseudo-codes
Algorithm 1 Risk-aware Relative Value Iteration
Input: Vo. f. T. O;
2: while n < ' do
3: for all x E X do
4: Vn+1 + (z) f(V,), where G defined in (3.2);
5: end for
6: n 4- n2 + 1;
7:
end while
Algorithm 2 Risk-aaare Relative Q-factor Iteration
Input: Qo. f.T." 2: while n < do
0;
3: for all x E X. a E A do
4: Qn+1(2,a) a) + H(Q,) (x. f(Qn), where H defined in (3.3);
5: end for
6: n 4- n + 1;
7: end while
Algorithm 3 Risk-aaarre RVI Q-learning with MLMC (MLMC Q-learning)
Input: Qo. (m), E 10, 0:
2: while n < T do
3: for all x E X, a E do
4: Sample N ~ Geo(r);
5: Independently draw 2 samples xf ~ P(+x,a))
6: Qn+1(2,a) + Qn(x, a) +)(n)) (P((Qn((e,)) f(Q,) an(o,a)): where H is defined
in (4.2);
7: end for
8: n + 1;
9: end while
Algorithm 4 Off-policy (asynchronous) RVI Q-learning for UBSR (A-UBSR Q-learning)
1: Input: Qo. f, ((),, T, 0;
2: while n < T do
3: Observe one transition (x, a, 2²);;;
4: Qn+1 (x, a) Qn a) + (n)) (c(x,a) + ming'ed Qn(x', f(Q.) an(
5: n 4 n +
6: end while
Algorithm 5 Synchronous RVI Q-learning for UBSR (S-UBSR Q-lenniing)
Input: Qo. f, (n), T, + 0;
2: while n < 7 do
3: for all x E X2, a E A do
4: Observe one sample r';
5: Q a) + Qn( a) + (n)) ()(x,a) + minaeA Qn(x', - f(Q.) Qx(xxa))
6: end for
7: TI 4- n 1;
8: end while
14

---

B Proofs
B.1
Proof of Theorem 3.2 and 3.4
From the definition of the risk-aware RQI algorithm (3.3), it is evident that the risk-aware RVI algorithm (3.2) can be considered a special case of RQI by defining V(z) == minge Q(2, a). Consequently, if the risk-aware RQI algorithm converges, then it follows that the risk-aware RVI algorithm also converges.
In order to study the Q-factor iteration, we make use of an augmented risk map R, on the outcome space, using
min a(, ( Vy L(K).
(x) = R
(B.1)
a'EA
The risk map R implicitly reduces the average aisk- control problem average risk eval- uation on a cost generating Markov chain. We thus invoke a general Doeblin type condition for average risk evaluation Markov chain.
Markov chain as follows, where see K. as the set of states of the
Assumption B.1 (Assumption 3.1, Shen et al. (2013)). There exists a function w K - [0, +o0), monetary risk measure L(C) -> IR, and some constants K > 0, 9 E (0, 1), and E (0, 1) such that:
(1) Let (q) == sup SUPpEC(X) (Ra,a + p) (D)3 and R# (,) = supx _ We have that
R# 2,a(( S 550(I, + K, V(z,a)
(2) For all 2 p C(K), we have that:
inf (#.0)EKnn(0.005$R
( a) a))((( Ri(p,, + aā((p) 2 0,
for some R> 2k/(1-1)
Lemma B.2. R satisfies Assumption 2.12, then R. satisfies Assumption B.
Proof. For the ā and y satisfying Assumption 2.12, define w 0. K == 1, 0.5, ā 0.5, R = 5> 2K (1 7), and monetary risk measure ((g) == v(miDaEd a)). We have
R th (AO)
R (
0
R# n. (0)
sup X
sup X
sup X
0 < 0.5 ())( K,
X
where we exploited the fact that:
R#
sup (R Rx)a( =0, ((x,a) EK.
(EC(K)
Moreover, for all 9 2 E L(K)), we have
min
[R(glz, a) - aU(g) - RRpp2z a) + av(p))
min ( - aï(4) - R(plo, a) + a((p))
(e.0)Ek
min (R,, (R.0)E o' 20
(min ((-, a')) av(min a'))) Re, (minp(())) av(min
a'
where the last inequality follows from Assumption 2.12 using v(-) == min a(,,aa and v'(-) min p(,, d'). The result follows.
We now list the properties of span-seminorm contractive operators that will use later
15

---

Lemma B.3 (Theorem 6.6.2, Puterman (1994)). Let T L(S)) - [(9)), for some finite space Q, be an operator that span-seminorm contractive, i.e,, there exists an [0,1) such that
IT - sww)llsp S a+lv w w|ssp for all
L( Then the followings are true:
(1) There exists v" E L(S2) such that [[T((²) seminorm fixed point of the operator T.
v²'1 llsp 0. Such of is called the span-
(2) For all 0, [v)
sp α" 1| u 00 1lap-
(3) For any E L())), we have lim (TT
1p -ppp0.0.. 0.
(4) Any two span-seminorm fixed points Tf must differ by constant.
In our proofs we will exploit the fact that is non-expansive and span-seminorm contractive. Lemma B.4. If the risk map R. satisfies Assumption 22, then both R and H (from equation (3.3)) are non expaxssansiv under the infinity norm and span-semine seminormi contractive.
Proof. From Proposition 3.6 in Shen et al. (2013), for any risk map R, which satisfies Assumption B.I based on Lemma B.2, we have a + p) - Rz (p) - R# 2,9(19)), where (q((2) := lq(x)]-
Since R z.a is a coherent risk measure (see Proposition 3.5 in Shen et al. (2013)), we have for all 4,P E L(K):
(R) - Rp) & R## 2.a - pl) - R## ,,a plaxe) = 114 - pllxe
where the second inequality follows from monotonicity of R# 2,00 while the last equality comes from translation invariance and normalization of R z,a-
The span-seminorm contraction straightforwardly follows from Theorem 3.11 1 in Shen et al. (2013) given the fact that satisfies Assumption B. as established in Lemma B.2.
These properties carry directly to H. since
[[H(q) H(p) ao [| R(pl-)1lo S |1q pllccs
and
[7(g)) - H(p)llep = - R(p)) S ā pleep
some E 1). This completes the proof.
We now ready prove the convergence of the risk-aware RQI algorithm (3.3).
Vo E X. Taking minimum over a on Proof of Theorem 3.4. Define (x) = minac,4 both sides of (3.3), obtain
Vn+1
min(c(æ,a) + R2 f(Qm) G f(Qn), Va X, a
where G is the risk-aware Bellman optimality operator. Qn converges to some fixed point Qoc of (3.3) under the infinity norm, we have
min Qxx (mx( f(Qxx), Ve E X. a'EA
min Q0o a) min c((x a) Rz,0 aEA
(B.2)
aEA
Notice that min.e (.) (min.g.A Q=)(-,a), (((Qx))) is a pair of solution to the AROE (2.1). By Theorem 2.13, f(Q.x) =
L(X), f(Qx)) E R and Qoo satisfies B.2, conclude that
g". Therefore, We are left with the task to show that Q, converges to some unique fixed point Qoc of (3.3).
To analyze the convergence, consider the augmented risk map defined in (B.1). Then algorithm (3.3)
can be equivalently written as:
Qu+1(x, a) = c(x, a) ) + R..o (Q.) f(Qw), V(z,a) K.
given the translation invariance of Rz,a- Its convergence can be associated to the convergence of an average risk estimator on Markov chain, with K. as the state space, under the risk map R. on
16

---

the K outcome space. which is studied in Section 3 of Shen et al. (2013). Indeed, given that R satisfies Assumption B.I, Theorem 3.14 (i) in Shen et al. (2013) already establishes that the Poisson equation,
c(z, a) Rz,a(4) = g + q(2,a), ((z,a) EK,
(B.3)
has a solution (4",9") where 5" is unique.
By Lemma B.4, the risk-aware Bellman optimality operator H (see (3.3)) is span-seminorm contrac- tive. This implies, based on Lemma B.3, that H has upan-seminorm fixed point, i.e, there exists q² L(K) and 1j" E such that [7((')) "011sp and q" + g" H(g"). The latter implies that (q"."") satisfies the Poisson equation (B.3) and that - 17 (q) q" llsp = 0, for any
q E L(K), due the span-seminorm contraction property of H (Lemma B.3).
One can further show that H=+ (g) H²)g) + g. for any E ((C), using
11H (q) - (q) - 0e
-inf -inf]|H(q"" + 11th (1) 9 9-) (q" + + (g) 9¹) g" 1l
=inf ||H((q" + (4) - 9- 1¹) + q- 9 - H² + q' - g" 1000
inf (1171((" + (2)
(²) H(q")((lll)))))) + [1H(1") q- 1c + (4) g 9'00
inf (g) - g - q'1lx + 114 + 9" - "-" l' ||H
- -101
= inf [1" - - q- o0 = (q) lepp -
where the second equality comes from translation invariance, the first inequality comes from the triangular inequality, the second inequality follows from H being non-expansive (see Lemma B.4), and finally the last equality is proved as Lemma 3.9 in Shen et al. (2013). Hence, we must have that lim,-+0 || (q) H1t (q) - 9" ll I lim,-+oo I|H (q) - q d0plap== =0, 0.
We now wish analyze the convergence of the process (Qn nm produced by our algorithm. To do so, consider the process Un+1 := H(U,,) with Un == Qo. for which we know that ll - - xc, where On == Un+1 Un. for 2 0. One can actually establish by induction that Qn - Un s(Un-1) for all n 2 1. Namely, start at n = where
Q1 H(Q))) f(Qu) H(U,) fU,) U1 f(U)).
Then iteratively assuming that On Un f(Un-1), 1),
confirm that:
Qu+1 - - = H(UU, - f(Un-1)) - f(Un f(Un-1)) -HUU)) - ((Un-1) [(U)) + 1(Un-1)=
= H(U,n) - ((U,)) Un+1 ((Un)-
This relation can be used to establish that
||Q++1 - 2ulloc = ||n++1 - f(U,) - Un + f(Un-1)lle
0 f(U,)) f(U 9²) f(U,, f(Un-1 9") f(Un-))llo
1 - g" - -((U)) + f(Unn1+
I 1lăn 3"ll 501oo X [lf(UU)) f(Un-1 +0)""")) blc
S 1 g" l X i.U, Un-1- 9'
11 001 + i - l*
where the third equality follows from the translation invariance property of f imposed in As- sumption 3.3 (i), while the final inequality arises from the Lipschitz property of ʃ in in As- sumption 3.3 (ii). with i, > 0 as the Lipschitz constant. When n + co, we have shown that I|ón O |0o = 1 (Q)) (Q,) ~" - O. Therefore we can conclude that Qn con- verges to some Q and f(Q.. converges to ğ" as - co, i.e., ((Q.o) satisfies the Poisson
equation (B.3). Finally, we show that such Qoe is independent of Qo for a fixed f. Since Qn + Qoo as n + cc, from (3.3), we obtain that
(x, -z, f(Qw)), v(z,a)
(B.4)
17

---

Notice that f(Qx)= g" is a constant, this implies that Qxc is a span seminorm fixed point of H. Suppose 20 is another solution (B.4). Then by Lemma B.3(iv), 2 and Q only differs by constant. Yet, we know that π" f() f( + f(Qx) ) + pr= g + r, which implies that r = and that Q = 20. We therefore conclude that Qoo is unique.
From the analysis in the first part, we conclude that h- min Qo) and g" f(Q identify a solution pair to the AROE (2.1) and thus f(Q =g".
We now turn to establishing Theorem 3.2.
Proof of Theorem 3.2. Let f _(X) + I be function satisfying Assumption 3.1. Define function C(C) R as f(Qn) = f a Qn(:,a)). easy to verify that f satisfies
Assumption 3.3.
Consider the risk-aware RQI (3.3) with function f starting with Qu. Define Va(x)) = min Qu (I, a). for all N. Taking minimum over a both sides of (3.3), we obtain
Va+i(1)) min a) + Ra,a (V.)) - f(Qn) G(V.)()) f(Q.)
aEd
= -v(,)(()) f(Vv). Vz E X,
where G is the risk-aware Bellman optimality operator defined in (3.2). This is exactly the risk-aware RVI algorithm with initial value function Vo(x) minaeA Qo(2, for all X.
By Theorem 3.4, the RQI algorithm converges, i.e., Qn converges some unique fixed point of (3.3) called Q" Hence, V, converges some V min (* a). Since a Qo such that min.e.A (z a) = Vo(x) for any Vo E L(x)) We conclude that for any initial value Vo. the risk-aware RVI algorithm (3.2) converges some V*.
always design
Using the same reasoning as Lemma B.4, we can conclude that the risk iis-ewware Bellman optimal- ity operator G is non-expansive under the infinity norm and contractive with respect to the span- seminorm. Based on Assumption 3.1 and the preceding derivation, taking the limit on both sides of (3.2) yields the equation V (x) = (z) - f(V*) for all x E X. This implies that (V*, J(V")) identifies a pair of solution to the AROE (2. 1), leading to f(V*) = g" and V serves as a fixed point of (3.2). The uniqueness of V follows from the same argument used to establish the uniqueness of Q" in the proof Theorem 3.4. This completes the proof.
B.2 Proof of Theorem 4.5
In this section, the ODE analysis of stochastic approximation to prove the convergence of the risk-aware RVI Q-learning algorithm.
Define operator H L(K) L(K)
H(q)(z,)) = = (<(o, a) + min a(:,a') f(() (x, Vq L(K).
a'EA
Then the update of the risk-aware RVI Q-learning be written
Qn+1= = Qn + -
Qn)
Q (2)) + +(Q..)))+)))))))))))))))))))(()) H(Q,) -(Qn)-Qu))
Hence we have the stochastic approximation iteration:
Qn+1 Qn + (QQ) + Ma+1),
(B.5)
where Ma+1 = A(Q.)) H(Q,) is the noise term.
The classical approach to analyzing stochastic approximation using ODEs involves examining the stability of the equilibrium of corresponding ODE related to (B.5):
H (pr).
(B.6)
18

---

If the ODE (B.6) has a unique globally asymptotically stable equilibrium point p.. then under certain conditions, the stochastic approximation (B.5) converges, with Qn - Q* = p" almost surely (see
Theorem 2.2 of Borkar and Meyn (2000)). Notice that if such p exists, then Q is solution to the AROE (3.4), which implies that (ming p" (,,a') a'), ("") is pair of solution to the AROE (2.1). Then the result of Theorem 4.5 follows easily.
Analyzing the stability of the equilibrium point of ODE (B.6) can sometimes be challenging. A common approach is to employ a time-averaging technique to smooth out perturbations and examine the stability of the origin in the limiting ODE. Namely, we define an operator H, L(K) L(K) as H (Q) == (sQ), with 2 and consider the ODE:
b. H.())).
(B.7)
Following Borkar and Meyn (2000), establish the convergence of the stochastic approximation (B.5), we outline the sufficient conditions that are needed to be verified:
The function H is Lipschitz.
The sequence FM : 2 1) with Fr == a (Q;, M,, S n) a martingale difference sequence. Moreover, there exists some Co and for any initial condition Qo E L(K) we have almost surely,
M S (6(1+112n13) n 2
(iii) The step size satisfies the Robbins-Mont condition (see Assumption 4.4).
(iv) For any initial condition Qo E [(K)) the iteration bounded almost surely, i.e.,
sup,, |1Q |l oo, almost surely.
(v) The ODE (B.6) has a unique globally asymptotically stable equilibrium point.
(vi) The limit H (Q) limg-+00 (Q) exists and the convergence is uniform compact
sets, and the ODE
Φ. Ho
(B.8)
has the origin as an asymptotically stable equilibrium.
Following Theorem 2.2 of Borkar and Meyn (2000), if conditions (i), (ii), (iii), (iv) and (v) hold, then the stochastic approximation (B.5) converges almost surely to the unique globally stable equilibrium point of the ODE (B.6), which is a solution to the AROE (3.4), thus confirming our theorem.
The Lipschitz property (i) is straightforward to verify, the risk measure Rz,a and the function are both Lipschitz (see Lemma B.4 and Assumption 3.3). As stated in Theorem 2.1 of Borkar and Meyn (2000), the almost sure boundedness condition (iv) follows from conditions (i), (vi), (ii) and (iii), where condition (iii) is automatically satisfied by Assumption 4.4. Thus, the remainder of this section focuses verifying conditions (i), (ii), (v) and (vi).
B.2.1 Condition
Lemma B.5. H, H, and Hox if exists, are Lipschitz and have the same Lipschitz constant.
Proof. Following Lemma B.4, R is non-expansive. Hence, for any Q1, Q2 L(K), with Assump- tion 3.3, we have
((Q0)((.a) (Qi) - (Qx) - -0)))(()))())))(())))))))) Q2(2,a)
-1((x,))
5 - Q21 LllQi Q211x + || - Q211o
(2 + 1)1l1 Q2lloo.
where Ż is the Lipschitz constant for f. Similarly, we obtain H(Qz) a) H(Q:)(z, a) $ (2+ D)ll2² Qillo Hence H is Lipschitz with Lipschitz constant 2 + L.
19

---

Meanwhile,
H. -
1 Rr, ( a) + min sQ (2, a)) RR (c(2,a)
min sQ2(2, a))
a'EA
a'EA
- -((sQ) + f((02) sQi a) + +sQ2(x,
$ 1 (s|1Q Q21loo + +1111 Q21lo + +l1Q1 - Q21la)
(2 + L)IlQ: Q21lx.
Similarly, obtain H, (22))( (Q)Q)) with Lipschitz constant 2 3- Similarly, if Hox (Q) = lim,- (Q) exists, Ho is also Lipschitz
< (2+ -2+ Qilloo Hence H3 is Lipschitz
with Lipschitz constant 2 + L.
B.2.2 Condition (ii)
We check that Mn. is martingale difference sequence that satisfies (ii).
Lemma B.6. Under Assumption 4.1, for all = 0,1,.., we have [E[ [r = almost surely
and there exists some Co such that for any initial condition Qo (KK) have
B|| I1 [Fm] S Co(1 + Co(1+11Qn113))
T 0, a.s.
Proof. By Assumption 4.1, it is easy to see that E E(H(Q,))F,)) H(Qn),
(a,, 101++10u V(x,a) E K,
for some constant C > 0. Then by definition,
= (), - = -
a.s.
Meanwhile, for any (x, a) E K. from the definition variance, we have for all (x, a) K. that almost surely
=[(())))))a[][[((.eeeee -(Q.)....))
E((H((Qn)z,) a) - ()) (a)
C(1 11
This implies that
1| 111FF < ICC((1 + 11x11))) a.s.
From the norm inequality, have
M|| 11 [F]] S Ma + [1 < |C|C(1 + (())) =: Co(1 1(Q,)))), a.s.,
for some constant Co < co. This completes the proof.
B.2.3 Condition (v)
In this subsection, we always assume Assumption 3.3 holds for the lemmas. To prove (v), we need to analyze the stability of the equilibrium of ODE (B.6), which is quite difficult as there exists nonlinear terms Rr, and f. Following Abounadi et al. (2001), we also analyze the behavior of an ODE where replace f f(Q) with constant g":
(gt),
(B.9)
- 9" -q. -9, Vq E L(C). Clearly, the fixed point g ODE (B.9), together with g", is a solution to the AROE (3.4). Hence, under Assumption 22, the set of fixed point of (B.9) not empty and by lemmas B.3 and B.4, the fixed points differ by constant. We conclude on the characteristic of the set of the equilibrium points of ODE (B.9) using the following lemma.
where H(g) := -
20

---

Lemma B.7. The set G of equilibrium of ODE (B.9) satisfies G = {q q q" +r, E R}. where qº is the only solution to the AROE (3.4) that satisfies f(q*) = =g"
Proof. It is evident that any solution q" to the AROE (3.4) satisfies 0 = H (q)). indicating that qº an equilibrium point for the ODE (B.9). According to Theorem 2.13, under Assumption 12, the set equilibrium points is non-empty. Similarly, for any equilibrium point ÿ E G. we have 0 = (T), which satisfies the AROE (3.4), implying that q is a solution to the AROE (3.4), i.e, span-seminorm fixed point of H. By Lemma B.3, each fixed point differs only by a constant. Therefore, we conclude that G = (q q = + r, E R for some equilibrium point q.
Now suppose f(ī) for some constant m. Then by Assumption 3.3, [( + g" m) = f(ā) +
9º m = 9" Hence, we can always find a q7" := g + g satisfying f(7") = g" By definition,
G, therefore is solution the AROE (3.4).
For notation simplicity, define
H(4) == H(q) - f(a), H((g) = H(g) - -g;, q L(K).
Then for the two ODEs (B.6) and (B.9), we have
Pr = (p:)) = -H(pe) pt. de = ((:) = H((gt) gt-
Since H is non-expansive (see Lemma B.4), H is also non-expansive. From Theorem 3.1 of Borkar and Soumyanatha (1997) (also see Lemma 3.1 of Abounadi et al. (2001)), the ODE (B.9) has unique trajectory that may depend on the initial point qo and converges to some equilibrium point q². We conclude as the following lemma.
Lemma B.8. Let qi be solution of ODE (B.9). Then qi - q'' as t + for some equilibrium point q" of (B.9) that may depend on Qo. Moreover, qi = q + F for some F E I, where i is defined in Lemma B.7.
Proof. The convergence result follows from Abounadi et al. (2001) Lemma 3.1. Then the result follows by applying Lemma B.7.
Following the property of f. we can show that the equilibrium point of ODE (B.6) is unique and is also included the set of equilibrium points of ODE (B.9).
Lemma B.9. The point q' is the unique equilibrium point of ODE (B.6).
Proof. Based on Lemma B.7, since [(T) = we have H(T") = H(( = = which means that q² is an equilibrium point for (B.6). Conversely, if there exists some á such that Hp p. by definition, the solution of the above equation satisfies the AROE (3.4). By Theorem 3.4, ff) g". Therefore, we have p = H()p) Hl))), which means is also equilibrium for (B.9). By Lemma B.7, p q"' + F for some E Then we have g" [f) f(g + +r) g" +r. This implies that r == 0. Therefore, q" is unique equilibrium point for ODE (B.6).
The next result shows that the trajectory of ODE (B.6) and ODE (B.9) differs only by a constant function.
Lemma B.10. Let Pt and qe be the solutions the ODEs (B.6) and (B.9), with the same initial value Po (x, a) = (0, a) Qo(I, a). Then we have
pr(x, a) qe(20 a) +r,, V(x.a) K.
where Te a scalar function satisfying
i, = -- 9" f(gc).
21

---

Proof. Notice that H(Q) H(Q) + (g" f(Q)). Then from the variation of constants formula, we have that
/ 0 ((p a)) I (g ff(a)dss
(ll,)))00(2;0)))))) a) a) (0 + / ((q. o))ds.
The maximal and minimal components of pt yt be bounded by
max (pr(2, a) (x(2, -9((xa))) v (x,a)eK.
(1 max
a))ds
0
(5,0)EK
#ff e e-((s)) f(ps))ds,
min (pe(e, -0( (((( (x,a)EK
e(((a)) min (Hi(p))(x, a) (xr a))ds (5.0)EK
L c -t(r-)) (g" - f(p.))ds.
+
Hence, we have
(" e (1--)) (((())) ) -F((q,) Ilspds
lp: - 4: lep S
$ c (-(1-s))1p lp. -gllaads.
The inequality is from the fact that H is span-seminorm contractive (see Lemma B.4), By the Gronwall inequality, we have ||p, - gellep 0. This implies that there exists some scalar function such that Pr(a, a) (x a) + r() for all (I, a) E K. with r(0) = O.
Since H((p)) H((q: + +r) = H())) + r, and f(p)) = f(a + rt) = =[(e)) +re Then the differential of rr is
te Pt àt H((p)) ) + f(p)) -M(()) + (-ri + g" f(
This completes the proof.
The following lemma shows that is the unique globally asymptotically stable equilibrium point of ODE (B.6).
Lemma B.11. 7"t is the unique globally asymptotically stable equilibrium point of ODE (B.6).
Proof. From Lemma B.10, by the variation of constant formula, we have rt J0d (1( dss By Lemma B.8, we have dr - g" G. Then have т. gg" flg") that + q" + (g" - -f("))) which must coincide with q" since by Lemma B.9, it is the only equilibrium point of ODE (B.6). Next we show the Lyapunov stability of q* Notice that
||p: q'dl 100 S ||ge 1o + |ncl
$ 1190 - q" 1000 + {/' e -((0o)) fdg
< [po - 10 + / ((((-s) (f(()) f(g))((
< (1 + i(1 - { q" 1mo
Hence for any fixed f > 0 and any 0. we can always make [po -7'l < 8 where <
i+1(----() to guarantee that ||p, 7"d 1o00000 < c. The Lyapunov stability holds, completing the proof.
22

---

B.2.4 Condition (vi)
We now look at condition (vi).
Lemma B.12. Under assumptions 2.12 and 4.2 on R, the risk map R also satisfies Assumption 2.12.
Proof. Following Assumption 2.12, there exists a coherent risk measure v and â E (0, 1) such that for any 2 o' E [()), we have
min (R(ulz,a) - -vll() - (x a) + ar((')) 0. (æ,0)eR
Substituting and o' with and st' respectively, where s > and then dividing both sides by 8. we obtain
1 min (R(sulo, a) av(st) R(sv' (a, a) av((s')) O.
8 (x,a)EK'
Since is coherent and by Assumption 4.2, lim ( Rg (u), taking the limit, obtain
_ a) - (vv(() - 1 R( a) + av((?)
0 s lim min
s-000 (m.a)EK:
= min (R (v) - -a((v) - R2z (v') + au(())) (2.0)EK:
This implies that 8 satisfies Assumption 2.12 with coherent risk measure and E (0,
Lemma B.13. Under assumptions 2. 3.3, 4.2 and 4.3, the limit Ho) == limy-roc Hg) exists for all Q E [(K), and convergence is uniform on any compact sets. Furthermore, the ODE (B.8) has the origin unique globally asymptotically stable equilibrium.
Proof. Under Assumption 4.3, we have
Hz(g)(z, 8 Rxa (clz, min sq() f((g) sq(2,a)
a'EAA
c(x, a) + RI, (s min a( (()) f(()) - q(x,a).
min d'EA
Hence, by Assumption 4.2:
Hxo())zz = lim H,(q)(x,a) R
min g(: f(g) ((2 a). a'EAA
+
Since R2C exists and the convergence is uniform all compact subsets of L(X), the first part follows. Clearly, the origin is an equilibrium point of the ODE (B.8). Following Lemma B. R satisfies Assumption 2.12, then by Lemma B.11, the origin is also the globally asymptotically stable equilibrium for ODE (B.8). Hence condition (vi) holds.
B.2.5 Convergence of RVI Q-learning
We now ready to prove Theorem 4.5.
Proof of Theorem 4.5. The almost sure boundedness condition (iv) is derived from Theorem 2.1 of Borkar and Meyn (2000), which necessitates verifying conditions (i), (vi), (ii) and (iii). These conditions are confirmed using Lemmas B.5, B.13, B.6, and Assumption 4.4. The convergence and optimality of the stochastic approximation then follow from Theorem 2.2 of Borkar and Meyn (2000), where conditions (i), (ii), (iii), and (v) are validated through Lemmas B.5, B.6, B.1,, and Assumption 4.4.
Regarding the almost sure convergence of क. + =", one can first observe that : - C R, for some discrete set C with [C < [C]. Letting
min
(z, (²
(ze (x',) (aao
23

---

the almost sure convergence of Qn + Q" implies that there is probability one set of trajectories
2, with each trajectory {Qn} E Q having the property that there exists N 2 such that 1Q2, Q" Io I e/2 for all n 2 N. This implies that for any 2 N,
Q² o) Q" (z a') = Qn(o,a) Qn(x', d'), V(r,)), (z',d') E eK.
We can therefore conclude that for all a E X' and for all n 2 N, we have
argmin Qn(I, argmin Q" (z, te X. aEA
aEA
Thus the policy nn converges some n" for all (Qn) Q almost surely.
B.3
Proof of Theorem 4.7
For notation simplicity, we write (4.2) as
Ax(1) PN
H(()) HHpz1, (1)
where
Ax(g) == pp (4) (Mpg,, (4) + Hpp (9)), ba E L(K).
To prove Theorem 4.7, we invoke the concentration results under the I-Wasserstein distance from Fournier and Guillin (2015). The 1-Wasserstein distance between probability measures f and on is defined as
/ | yloldr,
dw (n, v) = inf
sld, dy),
+EV(a.))
where (p, 1/) is the set all joint probability distributions va(2, y) with marginals and v. Lemma B.14 (Concentration inequalities). Given any E L(X) and P E (XX), let g be the empirical distribution from k realizations {2 , drawn ii.d from p. Then,
x'/.
E Σ (ad' Emde)obtrrr ) z'EX
EE
dw
< e1llollook-112
x'E
and
E
dw
Σ WEE
5t (2'))o(ur) Σ IlorVoilees < Cellu|Batt
EEX
for some constant E₁, C2 >> O independent of u. D, ls and 8e(u) is the Dirac measure of v(x)).
Proof. To simplify notations, we use pi-) to denote 1² (-). The first bound follows from Theorem of Fournier and Guillin (2015). Namely, there exists a e > O such that:
1/2
E dw ((x'))o(())
Σ Maae)oucz)))
< 2é,
Σ o(oo)) Z'EX
/k1/2
26, 11:loocck-2///
By Lemma 5 and Proposition 10 in Fournier and Guillin (2015), we have that for all L(X) with ||w]loo < 1, there exists constants εz2 Eg > such that for all À 2 0:
dw ((xx)) E(x')) wre
Σ p(a' (uute) x'EX
22) < E, exp((((())))
24

---

given the fact that p is distribution on a finite set. We can thus derive that:
2
E
dw
Σ
IEE
27
S
E
111u112o dw
Σ
p(xx Dulto))
E
Wee
x'Ex
2
= =1|0012
P dw
Σ
E
p(x' ((ulor)))))
_ dd
F'E
/
41/01130 C2
S 4||0|133
E2
Ezk
(1/2)//|/oll where w. = (1/2)u/ ||llo a is such that |/ $1/2<1
Proof of Theorem 4.7. Assumption 4.6 implies that Ra,, is law invariant, that Ru,,(v) o P(x'|2r a))o(e)), with 2z,a as the distribution-based risk measure associated to Ry Let R capture the empirical risk map that employs the same distribution-based risk measure Cx.o of Rg but on Ex'xx Ps (x'lxx a)do(zr) instead of Ex'ex P(x' [x, a)0e(rr)) where Ps stands for the empirical distribution using 2 number of samples. We start by establishing two important properties how H (q) differs from H(g).
The first property consists of a bound on the expected absolute difference between Hpp (g) and H(q), where the expectation taken with respect to the sampling process. Namely, for g L(K),
[p (z) H(1)(,,))) mi]]
E
= R
+ wex mex
Rzza (atz,aa) + max (exxa( d'Ed
Σ P(r'lar )]
< WF
Ldw Σ
Pa pc, a
w'ex
x'Ex'
< -C, [eC]lc(æ,,0 a) + max
g(: a d')ll
k/2
< LC, (2C' + 12 k/2
d'EA
where u(x') == c(r, a) max. A Q(x', a'). The first inequality follows from Assumption 4.6, and the second one from Lemma 1.14.
Following a similar procedure, we have the second one, which bounds the expected square differ- ence:
E
H (00((,)))H(((())))
27
E
Ret (c(x, maxgl: d')) Ro,o((I, +max
max g(, a'EA
a'EA
<
E
Lddw Σ
P2
Σ
P(x' (ar a))
W'E
#'E
< 2d E2 + maxq(; a 2 C2C + 11a11b0)2-
d'EA
where the second inequality is from Lemma 1.
25

---

We are now ready to show that E[H(g)) = H(g)). for all [(K), which goes as
Av(g)
[(H())] =E
Hppy1 (9)
PN
AR(a)
= =E[H p (2))
P(N = K)R
N = k
Pk
k=0
= =E|H (1) +
[+)+((0]
Pe (q) - (Mpg, (q) + Hpp, (i)
1
= (E(H)((9)) +
k+1
13 Patt (4)] - [BH pe (4)] + 10H po (1))
p4 (4)) +
P (4)] - B[H (9)1
k=0
lim p.pp (q)l H(g). k-000
where the limit is known to exist and identified as H(4) since for all (z, a) E K. we have
(1)x,, a)] (2))
(1I s <EI (0) a) H2))(z
$ SE, + 14 k/2
thus implying that || (4) -
- 0 = k + oc.
We turn bounding (arlH(() a)}. Since for all (z, K. have
= 1|
and it is known that |(HH(g)) - (2C + ) +2lggl23. The remaining question is to
bound (x, =))
We first give bound on (1) a)) Notice that
()) [ (Mo_ 2
(Npp, (1)(z.))+ + +Mpo ()) k+l
=E (C (g)(z - H(g)(z,a)) - (HiE (g) + H (1) (2))))))) 27
(22HH , (g)(z, a) H(g)(z, a))² + (Hpe ++1 (g)(z, - (z,
+ (Mpp, (g)(z.a) H(q)(x,a))) a))²
=2E[(HA (0)22,, - H(g)(x, o)) 2E p. (1, - H(g)(z,)))
12
22 22 + || ) 2-
3320,220' |1
2- )2-
26

---

Now we are ready to derive the bound for (() a)) for any fixed (æ, a) E K. Namely, from definition, we have
(Avla)esa) 27
)
(((())2)))) (,))))) 2E
PN
(Av(oVera)) N
= 2(2C + =1111l002 2 + 2E
Σ P
PN
k=
=
+
Pk
k=0
20 s 222C + o0 +
35 C2( + 1191 22
Ph.
2(2 |1 C2 [0 Σ (2(1 r))
k=
2(2C + 12
[1g1 (2(1 -r)) 1
= (2 + 63 (2)))((())))) + 2l11)
I (2 + e,r -
where to ensure Σ 0
k= 2(1 - r) is finite, we requirer (0, This implies that there exists
uniform bound C such that Var (f(()) (((R(g)(=,a))) (H(()((z, a)) - C(1 + 11q
This completes the proof.
B.4 Proof of Theorem 4.10
We impose the following general assumption on the convexity of the loss function l. Assumption B.15 (Convexity). The loss function E(x) is either corvex or concave on x 2 and either convex or concave on S 0.
We prove Theorem 4.10 by proving lemmas B.16, B.21 and B.22.
Lemma B.16. A risk map R that employs UBSR measure satisfies assumptions 2.12, 4.2 and 4.6, if the Markov chain satisfies Assumption 4.8 and the loss function satisfies assumptions 4.9 and B.15.
The following property of UBSR is useful as it establishes connection between the UBSR measure and the expected utility.
Lemma B.17 (Proposition 4.113, Föllmer and Schied (2016)). Given some random variable u and some E R. the following statements are equivalent: (i) SR(v) = m²; (ii) Elé(v m²)] 0.
Lemma B.18. Under assumptions 4.8, 4.9, the UBSR satisfies Assumption 2.12.
Proof. By Assumption 4.8, there exists a state ă E X such that P(z|z, a) > for all (x, E K. Let v(v) == v(z), which trivially satisfies r0) = 0 and is coherent. Mcanwhile, choose ā < 61 min P(ā a) E (0, 1).
L
Given any v 2 E C(X') Lemma B.17 implics that Evex similarly for v'. We therefore have
SRz, (v)) 0, and
0 = Σ Plyla, (((((() - SRz, ((v'(v) SR
NEX
Plyla, ()0, o' o,, (,(())(((())) (R))(v)) (v' (v) (R,raa')))), NEX
Σ
27

---

for some 6(0, a,,,,, E [e1, L1] due to Assumption 4.9. Hence,
(SRr,( (v) - a (v'))
Σ
P(ule, a)0(,,
yER
Σ NEX
e')))
Therefore, we have
EvEr P(yl ()((o)) o'(v))
(Rz,a(v) 100--hh -S)z
inf (
8 ( (saa))xXxa
ΣvEx a( a.
Σ VEX
Plulz,a)(v(v) - -(()
given that v 2 v.. Hence, we have for all (I, a) KC,
SRa,( av(r) SR (v") + av(r)
1
Σ Plylz,a)(u()) v'())) - (v(v - v(1'))
L1
yEX
61
Σ Plylz,a)(v(y)) v'(v)) -
L1 VEX
E1
min a() - 0' (3)) (v( (1))
Ti (2.0)EX
C1
min a(z a (v(*) - o' (z)) 2
L1
(2.0)EK
This proves that Assumption 2.12 holds.
Lemma B.19. For any loss function E IR + R with {(0) = 0 satisfying assumptions 4.9 and B.15, define to(x) == =((x). We have f, (x) + Lox (x) uniformly on compact sets as s - co, for some loo that satisfies assumptions 4.9 and 1.
Proof. By Assumption 4.9, E(x) is strictly increasing. We consider the case where (xx) is con- vex. In this setting, the right derivative is non-decreasing and bounded above hence the monotone convergence theorem implies that e (z) + L < L1 (=(x) + L 2 c as x - -00, where we slightly abuse the notation and use E' (z) and & {_(x) to denote the left and right derivative of l at x. Without loss of generality, we assume that L = L1 and <1. Define (ar) == I.2 for x 2 and (x) = f1 for < O. Remember that (x) := 1 (sx). We start by demonstrating that lim l, (x) foo (x) pointwise and will follow with confirming uniform convergence on compact sets using Ascoli-Arzelà theorem.
20, and similarly the left derivative
Clearly, lim (0) = 0 = (0). Now consider the case of some F > 0. Based on Assump- tion 4.9, for all >> 0, must have (1/))((s)) < LI lim (z( < _ = foe (T). On the other hand, by convexity of E(xx over x 2 O, for any ε > O. one can identify some è > such that L1 #/27) [e_ (.), E, (+) and therefore for all 0,
0) L Hence have
{(x) 2 ((t) + (L1 - (27) (x 2). Thus we must have that
1 {(sT)) 1 (e(i) + (Li - =/(22)) - 4))
(e(()) + LisT L₁ (E/ + (#/(2z))a)
L (e/(27)) 1 (l(i)) (h (e/(27)))G)
L - E, 2
28

---

as long as 2 2/{(2) - (L1 - - Hence lim,-+0 (z(Ø) 2 600 (z). Combining the two
results, we conclude that lim (z) pointwise for x 2
The case where I < 0 is treated similarly. Namely, letting g(x) == -((-x), we wish to 6 for all S (g(v) ( (y - x) S L1 and (x) = (-(xx) + as + oc. We can start with (1/s)e1(sž -0) Ej The upper bound is consequence of the concavity of implying the existence of some & > such that él + (e/(2z) belongs to the interval [g'_ (#). 94 (+)), where g'_ (x) and 94 (z) denote the left and right derivatives of g at x, respectively. This observation leads to the subsequent argument:
show that (1m))
0, with g(x) concave function such that
lower bound argument (1/))g(sž)
1 g(5)) - (9(#) (e1 + e/(2 -a)
1
= (e/ (c/(2z)) 1 (0(3) (c1 + (e/(27)))
< t
for large enough This let us conclude that for a < 0 it must hold that lim,- (1ms)=)01ss)((s))) = lim -11)))g(-sz) E
Concerning the uniform convergence on compacts set, we first observe that f, (x) is uniformly bounded on compact sets. Specifically, for æ E [ we have [x]] =1 [=x(s)
1 (s(x=))) S
L1 maax[|zal, [ma]] < oc. Moreover, by Assumption 4.9, both and l, are Lipschitz, ensuring equicontinuity. Given the equicontinuity and uniform boundedness of (xx) compact sets, along
with pointwise convergence, the Ascoli-Arzelà theorem guarantees that (x) + (x) uniformly on compact sets. To see this, the Ascoli-Arzelà theorem provides subsequential convergence f,, - uniformly for some function É, where 8; oo is subsequence index. Since we also have point- wise convergence f, -> loo- it follows that i = foo. implying uniform convergence of l., to loo- Repeating this argument, we show that every subsequence { of {6e} has a further subsequence that uniformly converges to loo. By the subsequence principle, conclude that La converges to Loo uniformly on compact sets.
The cases where f(r) is concave or combines convex (or concave) on x 2 0 and concave (or convex) on < are derived using a similar approach. Therefore, we conclude that under assumptions 4.9 and B. 15, l, converges to lop uniformly on compact sets.
Lemma B.20. Under assumptions 4.9, B.15, the UBSR risk map satisfies Assumption 4.2.
Proof. We start with establishing that for all (x, E K. all v E L(X), and for all > O, we have
SR (sv)
inf(( E (((0 [)] < 0}
inf(t' Ez,0 [((0 st') s 0}
inf(t'
f()) 0} inf(t' Er lo f)] <0}
-SR& (v),
where (v(y) = (1y)) Showing that the UBSR risk map is asymptotically coherent therefore
reduces to showing that SR (v) converges uniformly to SR. 2,0 (v) on compact sets.
(R We start with pointwise convergence of SR (v) to SR (v) after recalling that by Lemma B.17,
[e,a SR (v)) 0,
Er.aleso SR (v)) 0, L(X', (H, E
Specifically, given any e E L(X), we can define the compact set V = |- 2 loo] The uniform convergence of E, to Eo on compact sets (see Lemma B. 191 implies that for any arbitrarily small 0, there exists sufficiently large 3 such that we have [ex Lx(y) se1, for all
29

---

E V. Given that |SR (T) - | for all (I, E K. denoting E(v) := (x) - Ez((), we have
Exale SR (J))
Σ
P(zllz,a)les SR =((((x' -RR (8))
x'EX
Σ P(ello,
SR (6) + εE1]
Σ P(e/Iz,a)(ss(((a)) SR (0) c)] x'EX
- S (7) + E))]
where the last inequality comes from the fact that lz(x + + - lz(2) = (f(sx + 8E) {(sx)) 2
EEsE E₁ε due to Assumption 4.9, Similarly, we have
= Ez,alLa - (7)) 2 Els
SR z.0
(8) E)].
This implies that
ll SR fo (0) =)] s 0 S 15 SR (T) + =))].
By the monotonicity of and Lemma B.17, conclude that
SR (V) E [SR (v) - s, SR (0) + a].
This implies that SR (v) - SR (v) as s + oc. Using the same argument as Lemma B.19, the convergence is also uniform compact sets.
Therefore, we conclude that the UBSR is asymptotically coherent, i.c. Assumption 4.2 holds.
Proof of Lemma B.16. The result follows by directly applying lemmas B.18, B.20 and Lemma 15 of Prashanth and Bhat (2022).
Lemma B.21. A risk map R that employs an OCE risk measure satisfies assumptions 2.12 and 4.2, 4.6, if the Markov chain satisfies Assumption 4.8 and the loss function satisfies assumptions 4.9 and B. 15.
Proof. To prove Assumption 2.12 notice that for any v 2 v/ E L(X)) we have
(v) - OCE,, (e')
inf + Er, Er,al((v -]]} inf (t' + Ez,a - HeR
FER
inf
(E (e(1 -t) E(o' -)]}
ER
Σ P(y a)((, d. (o)))) -
DEX
2 Σ
- (v)),
yEX
for some v',, E [c,, L1] whose existence guaranteed by Assumption 4.9. We choose the coherent risk measure v(v) := v(z) and 0 < min P(z a) E (0, 1), since é1 < E (0) < 1 from the definition of OCE. By Assumption 4.9, for any (I, K,, we have that for all (z. a) E K.
OCE - ār(u) OCE,,a(E)) av(1')
2 E Σ
- o' (v)) a(v(() v'()))
DEX
2 min P(ī(r, à (o(3) o v'(x)) > 0, (x,a)eK
This proves Assumption 2.12.
30

---

To prove Assumption 4.2, we start with establishing that for all (æ,a) E K, all v E ((X) and for all
>> 0 have
OCE,
(sv)
inf (5 + -
8 EER
inf 15' + (l/ sE')]}
E'ER
inf (5' + BB -
S'ER
=OCE (v),
where (v()) == (1/s)E(sy). Showing that the OCE risk map is asymptotically coherent therefore reduces to showing that OCE",, converges uniformly to OCE (v) on compact sets.
Notice that from Proposition 2.1 in Ben- Tal and Teboulle (2008), the infimum in the representation of aC (e) can be attained on a member of the bounded interval supporting of the distribution Ex. P(x' (x. a)ou(e)) This implies that for any fixed e E (()), there exists optimal 5 E V == [mingrex v(2",, max, v(x')l such that OCE = {" E [E(v - {*)]- Hence for any fixed L(X), we can let & and foo E be the optimal & for the OCE with loss function &, and loo such that:
OCE = E- + Eo [.),. OCE (T) Ex + Ex. E.)1, (x,a) E
Following Lemma 1.19, we have (x(x) fx (a) uniformly on compact sets. Hence for any arbi- trarily small & > 0, there exists a sufficiently large such that (exo(y) - (a(v) S e, for all y E V.
Denoting E(y) =- fx (v) Ez(),, we have
OCE (v) = E + (u
E Σ P(rl(a,a)((s(((() Exo) + =(((x') [x)
s'EN'
2 Ex
Σ
- -
F'EX
2 c + Exalls(v-
{ - OCE (v)
Similarly,
OCE
= + Fx +1
= Σ P(x' (l(l - - - E(v(x') -3)
2 3
Σ allo0 -E3) -
F'EX
2 E00 + Ez,a 1oo [x0 - = OCE (v)
Hence we have
OCE (v) - OCEE (v) & OCE/,- +E,
which means that JOCE f (v) OCE pointwise. Since OCE is Lipschitz continuous and uniformly bounded on compact sets, can apply a similar reasoning as Lemma B.19 to establish Assumption 4.2.
s. (v) < E. This implies lim OCE, (v) = OCE`> (v)
Assumption 4.6 follows from Lemma 12 of Prashanth and Bhat (2022).
Lemma B.22. risk map R that employs spectral risk measure satisfies assumptions 2.12, 4.2, 4.6, if the Markov chain satisfies Assumption 4.8 and the risk spectrum ((3) E [E2, Lg] for some < > and T < 0o for all B E 10.
Proof. Since spectral risk measures are coherent, Assumption 4.2 holds automatically. Assumption 4.6 follows from Lemma 13 of Prashanth and Bhat (2022). We are left with Assumption 2.12.
31

---

Notice that
(v) /. (6(3) - -2) t // F. (3)
= c2BBuu| + /.
= + (M))),
where ((3) := : 62 [0, Eo| for all [0, 1]. Therefore, for any 2 v' L(X), choosing the coherent risk measure (()) = vz) and setting 0 < ā < 62 (a,e) P() E (0, 1), since 62 $ So o(B)dB = 1, we have for any (z, a) E K,
M (v) āv(u) M (t') + av((')
c2 (EE,ral (z M M (v') a(v(v)- v(())
Σ P(ulz,a)(v(v)) - -v())) a(v(T) v()))
62
yEX
min (x,a)EK:
P(aaa, - (2)())) v' (T) 2 0,
where the first inequality follows from the fact that spectral risk measures are monotone. Therefore, Assumption 2.12 holds.
worth noting that for the widely used OCE measure CVaR, the corresponding loss function, given by {(x) = (1 - (z)+ has a minimum slope of O; its risk spectrum, defined as 6(B) = (1- ar) 1113 2 a). attains a minimal value of
result, CVaR does not satisfy the condition required in Theorem 40 However, when mixed with the expectation, the mean-CVaR risk measure
with v) 0 fulfills the necessary condition for spectral risk measure Theorem and hence satisfies Assumption 2.12.
Proof of Theorem 4.10. The result follows directly by applying lemmas B.16, B.21 and B.22.
32

---

C
Additional Details and Results of Experiments
This section presents further experiments on the convergence of the MLMC Q-learning algorithm (4.1), along with statistical experiments on its sample efficiency. In addition. we conduct further experiments regarding the convergence of synchronous and asynchronous UBSR Q-eaaning with different loss functions, along with statistical results comparing this algorithm to the MLMC Q- learning algorithm (4.1). Furthermore, we provide details on the application setups used in the main text. We also include risk analysis based the expectile parameters across different application scenarios. All the experiments were carried out using Python 3.9 on a Linux server equipped with a 64-core AMD EPYC 7763 processor.
C.1 Statistical Experiments on MLMC
Although Theorem 4.7 ensures controllable variance for r E (0, 1/2), it requires an infinite number of samples in expectation per iteration achieve this. However, our experiments indicate that controllable variance can still be attained for some r E (1/2, 3/4), as demonstrated in Wang et al. (2023a) for special case of distributionally robust discounted MDP.
Table C.1 shows the statistical results (average number of samples, average estimated optimal risk and standard deviation of estimated optimal risk) from 100 simulations, each consisting of 1,000 iterations of the MLMC Q-learning algorithm (4.1) based on MLMC, for different values of the geometric parameter r changing from 0.49 0.9, under randomly generated MDP with 3 states and 3 actions, following the generation procedure outlined in Section 5.1. We observe that for small values of r. the number of samples required estimate the risk measure quite large, but decreases as increases. Additionally, the final estimated optimal average risk closely approximates the true average risk, which is 0.2968, computed via risk-aware RVI, suggesting that the MLMC Q- learning algorithm indeed converges to the right value. The standard deviation of estimated optimal risk initially decreases starting at r 0.49, but begins to rise again at r 0.70. This supports the findings in Wang et al. (2023a), indicating that MLMC could offer finite sample guarantee and controllable variance for some r E 31/2,3/4).
Table C.I: Statistical properties of the MLMC Q-learning algorithm for different r
Average Number of Samples
Average Estimated Optimal Risk
Standard Deviation of Est. Opt. Risk
0.49
202615.68
0,2956
0.0159
0.50
174297.02
0.2973
0,0163
0.55
92635.72
0.2976
0.0153
0.60
52500.64
0.2974
0.0164
0.65
39152.40
0.2963
0.0157
0.70
31476.86
0.2983
0.0188
0.75
26955.32
0,3002
0.0210
0.80
23967.84
0.2966
0,0221
0.90
20257.32
0.2902
0.0326
C.2 Additional Experiments for UBSR Q-learning Algorithm
For completeness, we present the synchronous version of UBSR Q-learning algorithm follows: for (x,a) IC,
Qn+1(I,a) Qn(z, (())((((z,a)) min Qn(x', f(Qn) Qu(2,))).
(C.1)
a'eA
where x' ~ P(-la, a), 7(n) is the step size satisfying Assumption 4.4 and f(Qn) serves as the relative value satisfying Assumption 3.3 and 4.3.
In addition to the expectile experiment presented in Section 4.3, we also provide the convergence results for the special case of the synchronous UBSR Q-learning algorithms with polynomial mixed
utility (also referred to as the S-shape utility, as discussed in Shen et al. (2014)) and the soft quantile (as discussed in Hau al. (2025)). The polynomial mixed utility function, derived from prospect
33

---

theory, is defined as follows:
(x) = 1
x 2 0,
-k2(-1))
I <<0 0,
where k1; h2 > O, bi b2 2 0. The soft quantile, used as approximation for the quantile, is defined as follows:
(1 - a)(r + +
x < -R, 1); 1);
x,
-K S x < 0, 0 < K, x 2 R.
(sQ(a)= =
22,
a(nx
162 +
with a E [0, 1] and i: >> 0. We choose hi =1 -1 0 4 b2 0.5 for the polynomial mixed utility and a = 0.2, x = 2 for the soft quantile, It is worth noticing that both two loss functions are generally neither convex nor concave on the whole domain.
Under the same MDP and step size settings in Section 5.1, we run our algorithm 100 times inde- pendently and plot the trajectory obtained from the value iteration, risk-aware RVI algorithm (3.2), mean value of f(Q) across all 100 trajectories from the synchronous UBSR Q-Jearning algorithm (C.1) and 95th and 5th percentiles as the upper and lower bound of the 100 trajectories as the con- fidence interval. The results are presented Figure C.I. appears that our synchronous UBSR Q-learning algorithm successfully converges to the true optimal average risk with high probability under both instances of the loss functions.
Synctronous UBSR PM i, =1 -y- 0.3, Dy 0g-0.55 0.5
Synchronous S0
A
0.
0.1
b. Vakee lieration
Est Vakao
0.
The
ESt corn (P0011
Est. O cariin (moan)
Dat. by Q carn rg (C)
Eat. by O carning (CB
-01
-02
-03
-05
-06
-07
Figure C.I: Convergence of the synchronous UBSR Q-learing algorithm (C.1) for polynomial mixed utility and soft quantile.
Asynchronous UBSR
fer Rebin
0.0
For Reber
Tue
Bal by G sur ng Imeant
Det. by O eumh ng
-01
Eal. by D sumnin Iniaan
Ext. O eomiing (CD
-02
-0.4
-0.4
-0.
-0.6
-02
-07
Kumber
Figure C.2: Convergence of the asynchronous UBSR Q-learning algorithm (4.3) for polynomial mixed utility and soft quantile.
Figure C.2 presents the convergence experiments for the asynchronous UBSR Q-learning algorithm (4.3) under the same settings as in Section 5.1, with polynomial mixed utility parameters hr
34

---

1- = 0.3. bj = by = 0.5 and soft quantile parameters a = x 2, under 300,000 iterations. The results provide evidence that the asynchronous algorithm also converges with high probability, confirming the applicability of the off-policy UBSR Q-learning algorithm (4.3).
Table C.2 shows the statistical properties (average number of iterations, average estimated optimal risk, standard deviation of estimated optimal risk and average risk of estimated policy) of 100 sim- ulations comparing the MLMC Q-learning algorithm (4.1) with the synchronous UBSR (S-UBSR) Q-learning algorithm (C.1) and asynchronous UBSR (A-UBSR) Q-learning algorithm (4.3) under the same settings in Section 5.1. All the algorithms are using the equivalent number of sam- ples. The total sample size for the MLMC-based and A-UBSR Q-learning algorithms is 300,000, equivalent to 1,000 iterations for the S-UBSR Q-learning algorithm since the S-UBSR Q-learning generates one sample per state-action pair during each iteration. For the MLMC Q-learning algo- rithm, we select r > 0.5 to ensure a finite average number of samples per iteration. The optimal average risk, computed through the risk-aware RVI (3.2), is -O. 1076. Additionally, we compare the mean average risk derived from the policies produced by the algorithms to assess whether the algorithms provide the optimal policy.
Table C.2: Statistics of solutions from risk-aware RVI Q-learning algorithms after 300,000 (x, a, x') observations in setting where the true optimal average risk is -0.1076.
Algorithm
r
Average Number of Iterations
Average Estimated
Standard Deviation of Est. Opt. Risk
Average Risk of Estimated Policy
Optimal Risk
0.55
729.16
-0.1086
0,0137
+0.1552
0.60
1039.22
-0.1099
0,0103
+0,1060
0.65
1396.86
-0.1067
0,0104
-0,1060
MLMC
0.70
1731.77
-0.1096
0,0099
-0,1065
0.75
2000.43
-0.1097
0,0089
-0,1053
0.80
2250.29
-0.1113
0.0114
-0.1059
0.90
2667.43
-0.1165
0.0206
+0.1050
S-UBSR A-UBSR
6000
-0.1076
0.0030
-0.1076
300000
-0.1074
0.0029
10.1076
Figure C.3 illustrates the convergence rate of the synchronous UBSR Q-learning algorithm under the expectile risk measure for different values of T. The y-axis denotes the absolute error between the current value and the optimal average risk. Recall that under the expectile risk measure, 7 0.5 represents a risk-neutral agent, > 0.5 corresponds to a risk-averse agent, and T < 0.5 to a risk- seeking agent. The results show that convergence occurs faster for risk-neutral agent and more slowly as the agent becomes more risk aware. This suggests that incorporating risk-awareness in way that is more sensitive to the tail events (i.e. т going towards or 1) increases the computational effort required.
Convergence Rate Synchronous UBSR Expectile
1.0
T-02
T=0.3
t=0.6
c-0.5
--0.6
0.8-
T-07
1-02
T-0.9
0.4
0.0
Figure C.3: Convergence rate of synchronous UBSR Q-learning for expectile under different
From the experiments, we conclude that although constrained to the UBSR class of risk measures, the UBSR Q-learning algorithm shows significantly higher computational efficiency. achieves notably lower standard error, faster convergence, and greater case of implementation.
35

---

Although the convergence experimental results are promising, analyzing the almost sure conver- gence of the UBSR Q-learning algorithm (C.1) remains major challenge. The standard approach for proving the almost sure convergence of the average cost Q-learning algorithm relies on the ODE analysis of stochastic approximation (Abounadi et al., 2001; Borkar and Meyn, 2000). In this case, the analysis leads to a high-dimensional nonlinear ODE system, which lacks the desirable property observed in the risk-neutral setting and our MLMC-based approach, where the difference between the reference ODE q and the target ODE p. when starting from the same initial point, remains scalar function over time, Consequently, Lemma B. 10 does not hold.
C.3 Application Setups
The machine replacement problem (e.g. Section 6. 10.4, Puterman (1994)) involves managing a machine that deteriorates over time, with the goal of minimizing the long-term average cost. The machine can be various states representing its condition, ranging from new to totally break down. At each time step, the agent chooses between two actions: keep operating the machine replace it with a new one. Operating the machine incurs maintenance and operational costs, which increase as the machine deteriorates, while replacing it incurs a significant one-time cost but resets the machine to its best condition.
For the parameters, we define scenario with 30 degradation states, where state 0 represents a fully new machine and state 29 corresponds a failure. The degradation probabilities are generated randomly, with a decreasing probability of transitioning to higher degradation states as the machine's condition worsens. Additionally, there is always a positive probability of transitioning to the failure state. The replacement cost is set to 302.5, the operating cost is 1 8, and the maintenance cost is 0.5 x s1.5, where s denotes the current state level. Additionally, the failure cost is twice the replacement cost, ensuring significant penalties for machine failure.
The water reservoir management problem (e.g. Section 1.3, Hernández-Lemm (1989)) involves managing a reservoir to balance water supply, demand, and the risk of overflow or shortage. The reservoir has discrete states representing water levels, and at each time step, the decision-maker chooses how much water to release. The goal is to minimize the long-term average cost, which includes penalties for water shortages, overflows, and operational costs.
For the parameters, we define the maximum water level as 19 and the maximum release as 5. The demand is set to 4, with a shortage cost of 15 per level shortage, an overflow cost of 20 per level overflow, and an operational cost of 2 per unit of water released. The probability of the incoming water level is randomly generated, with a decreasing probability of transitioning higher water levels, reflecting the natural variability of inflows. However, there is always positive probability of reaching the maximum water level, ensuring that the risk of overflow accounted for in every state.
The inventory management problem (e.g. Section 1.3, Hernández- Lerma (1989)) involves managing stock levels to meet stochastic demand while minimizing long-term average costs. The system has discrete states representing inventory levels, and at each time step, the agent chooses how much to order to replenish stock. Costs include holding costs for inventory, ordering costs for placing orders, and shortage costs for unmet demand.
For the parameters, set the maximum inventory level to 9 and the maximum demand to 9, The probability of the incoming demand is generated randomly with lower probability for higher de- mand. The holding cost per unit of inventory is 1, the ordering cost per unit is 5, and the shortage cost per unit of unmet demand is 10.
C.4 Risk Analysis Based on Parameter of Expectile
We visualize the results of the machine replacement and water reservoir management problems under different 7 parameters of the expectile in Figure C.4. This figure illustrates the difference between the r-optimal average risk and the average risk evaluated under the risk-neutral policy. The findings confirm that for 0.5, the agent exhibits risk-seeking behavior, whereas for 0.5, the agent becomes rvsk-averse. Notably, when 7 > 0.3. the r-optimal policy achieves a lower average risk than the risk-neutral policy, reaching the minimum average risk at the corresponding 7.
In Figure C.5, we present 30 simulation trajectories for both the risk-neutral policy and the risk- averse expectile policy (with = 0.9) across 1,000 iterations for the inventory management prob-
36

---

Risk aifference optimaal policy rak noutral policy (MR)
Rick differencce of optimal policy rak neutral policy (WR)
0-0.3
-05
142.5
702.0
2-24
5.0
6.1
0.3
6.5
07
03
6.0
6.2
6.8
0.5
6.7 0.5
Figure C.4: Risk difference between 7-optimal policy and risk-neutral policy under different т- values for MR and WR.
lem. The risk-ncutral policy results in optimal policy of (5,4.332. while the risk-averse policy yields an optimal policy of (2.11000.000000000000) with the first element of the vector represent- ing zero inventory. It is evident that the risk risk-averse policy produces trajectories with lower variance, suggesting that could offer greater stability when observed over a shorter time frame.
Inital state
In tal stare
in state
10:
107
12:
10
121
107
10'
Figure C.5: Simulation trajectories of risk-neutral policy and risk-averse policy under the risk- neutral setting for IM.
37

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Theoretical results are provided in Sections 3 and 4 with complete proofs in the Appendix B. These results are verified numerically in Section 5 and Appendix C.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
Justification: The limitations are discussed in Section 5.1 and further experiments address- ing these issues are provided in Section C. Future research directions are discussed in Sec- tion 6.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-er system might be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community, Reviewers penalize honesty concerning limitations.
will be specifically instructed
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: Yes]
Justification: Assumptions are stated and justified in Sections 2, 3, 4. Proofs are in the Appendix.
38

---

Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Experiment details are well documented in the paper. We provide the pseudo code for the algorithms in Appendix A and the setup of the application environments in Appendix C.3.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurlPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
39

---

We provide the code for implementation in the anonymous repository: https: prrps://anonymuus Guidelines:
Justification:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cr cc/
http://guiide//oeeeubiiii wow.soooossooooooiooooocoooc..cc for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /nips... cc/ htt//ublic/guuu wttgguuie////// /eoeeee//ooebbiteeeeeeeee ssi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The details are described Section 5.1 and Appendix C.3. Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We report standard errors for the experimental results in Appendices C. and C.2.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of emors is not verified.
40

---

For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative enror rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources Question:
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: The information is provided in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: ht///nuurpp...e wwtppcccc//ptcciieeeeeeeeeeeette iat.bliiccchhiiccccddeeeiieee Answer:
[Yes]
Justification: We have reviewed the NeurIPS Code and Ethics and confirm that our paper conform with it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is a theoretical paper that presents foundational research in reinforce-
ment learning algorithms. We do not see a direct path to any negative societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
41

---

If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: This is a theoretical paper that presents foundational research in reinforce- ment learning algorithms. It does not involve any high-risk data or model.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
Licenses existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We properly cite the papers which research is built Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswi wwwoeehoode..c com/datased has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification: The paper does not present new assets. Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/cooe/mmodll part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
42

---

At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsoureing experiments and research with human subjects, does the pa- per include the full text instructions given to participants and screenshots, applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects. Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects. and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects. Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if upplicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy atttps://neurrs cc/Conferencee//0000 (ttpeeenncee//2/////e/ for what should or should not be described.
43


Reviews:
[{"review_id": "qi28z24wUt", "reviewer": "Reviewer_RUxx", "summary": "This paper studies the problem of solving Markov Decision Processes (MDPs) under average cost criteria when using general dynamic risk measures. In the planning setting, the authors introduce a relative value iteration (RVI) algorithm that accommodates an extremely broad class of one-step risk mapping. In the learning setting, they extend both multi-level Monte Carlo (MLMC) techniques and an asynchronous simulation-based algorithm tailored to the UBSR (Upper Bound on Sample Risk) framework. The theoretical developments are supported by a set of computational experiments showing the practical behaviour of these methods.", "questions": "- The results are heavily on Doeblin condition. Is there any intuition beyond this assumption?\n\n- The results are based on time-consistent, monetary risk measures assumption. What challenges arise if one tries to handle more general, possibly time-inconsistent objectives (e.g. mean–variance)?\n\n- The objective is designed with dynamic risk measures, which quite differs from the usual static risk measures. The dynamic versions are known to provide poor approximations of the static one and is generally harder to interpret [1]. Have you tried to evaluate this in the setting of average reward MDPs, in the environment you consider?\n\n- How does the convergence speed compares to risk-neutral setting?\n\n[1]  D. A. Iancu, M. Petrik, and D. Subramanian. Tight approximations of dynamic risk measures. Mathematics of Operations Research, 40(3):655–682, 2015.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**:\n- Well written paper with a comprehensive review of the literature.\n- Strong theoretical contribution with rigorous proofs.\n- Detailed experiments that support the relevance of the algorithms.\n\n**Weaknesses**:\n- The experiments only consider relatively small scale MDPs.\n- The convergence of one algorithm (UBSR Q-learning) is not addressed.\n\n**Minor remarks**:\n- On page2 (introduction), it would be beneficial if the authors explicitly mentioned that their planning contributions (Section 3) involve model-based algorithms. The current wording might lead readers to think previous work was model-based, and this paper only introduces model-free methods.", "was_revised": true, "final_justification": "The theoretical contribution is strong and relevant for NeurIPS.", "rebuttal": "We sincerely thank the reviewer for their thorough review of our paper and for acknowledging our contributions. We are truly grateful for the constructive feedback and thoughtful questions. Please note that, unless otherwise indicated, the references mentioned in our responses align with those listed in the appendix.\n\n1. Response to the reviewer's concerns in the \"Weaknesses\" section:\n\n(a) Handling large-scale MDPs remains a central challenge in reinforcement learning, primarily due to the well-known \"curse of dimensionality\" that limits the scalability of dynamic programming approaches. Although the instances considered in our experiments are relatively modest in scale, we believe that the selected number of states and actions is sufficient to illustrate the validity of our theoretical findings. For example, in the convergence study, we employ randomly generated MDPs with 10 states and 5 actions per state; in the machine replacement setting, we consider a system with 30 degradation states. Developing approximate dynamic programming and deep reinforcement learning frameworks capable of handling significantly larger state and action spaces remains an important direction for our future research.\n\n(b) As noted in the paper, establishing a theoretical convergence guarantee for the UBSR Q-learning algorithm remains indeed an open problem. Resolving this question will require further investigation and the development of new mathematical tools.\n\n2. Response to the reviewer's concerns in the \"Minor remarks\" section:\n\nWe will follow the reviewer's advice and clarify this aspect by changing line 56 as: \"We propose a model-based RVI algorithm for average risk-aware MDPs\".\n\n3. Response to the reviewer's concerns in the \"Questions\" section:\n\n(a) The Doeblin-type condition imposes joint restrictions on both the underlying Markov chain and the chosen risk measure. Intuitively, it ensures that certain states are visited infinitely often from any other state under all transition kernels induced by the risk map. For the three classes of risk measures considered in this work, this condition can be decomposed into two parts: Assumption 4.8, which requires a form of strong ergodicity of the Markov chain, and Assumption 4.9, which imposes boundedness on the slope of the loss or spectrum function. While this Doeblin-type condition is sufficient to guarantee the validity of the AROE, it is not necessary.  We conjecture that the weaker conditions needed in the risk neutral setting might be sufficient for a broader class of risk measures.\n\n(b) It has been established that more general time-inconsistent risk measures can give rise to optimal policies that are history-dependent and potentially stochastic. This significantly complicates the analysis, as it is unclear how an AROE of the type used in this work could hold in such settings. Addressing this issue remains an open question in the study of average risk-aware MDPs.\n\n(c) To begin with, based on our understanding of the risk-aware RL literature, we respectfully disagree with the claim that static risk measures are the commonly used approach. Static risk measures, such as CVaR and VaR, exhibit time inconsistency, which often make the optimal policy history-dependent and unexplainable at a future point in time (see, e.g., section 2.2 in Marzban et al., 2023). In contrast, dynamic risk measures offer a principled framework for constructing time-consistent formulations; see Ruszczynski 2010 for further elaboration. For this reason, our analysis is grounded in the dynamic risk measure framework, and we do not aim to address problems defined under static risk objectives.  As you have noted that dynamic risk measures are generally not suitable as approximations of static risk measures.  For this reason, we have not tried comparing the values obtained from the two types of risk measures but agree that the question is worth further investigation.\n\n(d) Following the reviewer's advice, we will include a figure and a discussion in the appendix comparing the convergence speed of our algorithms in the risk-aware versus risk-neutral setting. For the UBSR Q-learning, we remark that the risk neutral setting exhibits faster convergence rate."}, {"review_id": "QEpghXWSC6", "reviewer": "Reviewer_mTEH", "summary": "This paper addresses the problem of planning in average-cost MDPs with general dynamic risk measures. The authors propose three algorithms: a model-based risk-aware relative value iteration (RVI) algorithm, a model-free Q learning algorithm generalizing MLMC, and a model-free asynchronous off-policy algorithm for UBSR measures. The authors show theoretical convergence for RVI and MLMC-based, while the last algorithm is evaluated empirically on three problems: machine replacement, water reservoir management, and inventory management.", "questions": "- Could you clarify under which practical conditions each algorithm is most applicable? For example, when should one prefer the MLMC Q-learning algorithm over the UBSR algorithm?\n- How limiting is Assumption 2.12 in real applications? Can it be weakened or checked easily?\n- Which algorithm was used to produce the values shown in Table 1?\n- In Table 1, what exactly is meant by \"optimal risk\" and \"expectile risk\"? Are these computed under the same policy or under different ones?\n- Is there a plan or path to proving convergence for the UBSR Q-learning algorithm?\n- Do your algorithms scale to real-world application systems?", "limitations": "Some limitations are very briefly discussed in the conclusion section, others (such as limitation to low-dimensional systems) are not.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "*Strengths:*\nThe paper addresses an important problem by addressing average-cost MDPs with a broad class of dynamic risk measures. The introduced algorithms are novel and of practical relevance. For two algorithms, there are rigorous formal proofs for convergence (I could not verify them in detail, though). Generally, the paper is well-written and organized.\n\n*Weaknesses:*\nConvergence of the UBSR algorithm is only shown empirically, though this seems to be the most important one. The differences in applicability between the proposed algorithms could be stated more clearly in the introduction (under which circumstances, which algorithm should one use). Assumptions 2.12 and 3.1 seem quite restricting to me. While the paper presents one model-based and two model-free algorithms, section 3 \"model-based algorithms\" introduces two algorithms, section 4 \"model-free algorithms\" just one algorithm, which is confusing to me.\nI see the main issue with this paper in the evaluation. The application to practical problems (machine replacement, water reservoir management, inventory management) is only briefly discussed, and all these systems are very small (and this limitation is not discussed). I do not understand which of the algorithms is applied for the results in Table 1 and why not all of them are applied. The results are not discussed at all, just some numbers are stated that \"confirm [their] theory, proving [their] effectiveness\". There is (almost) no qualitative discussion of the results, showing that the problem formulations and the solutions provided by the algorithms are sensible. At least, in C4 there are average costs of simulated trajectories for the inventory management problem provided, but this also lacks a detailed discussion besides stating that \"the risk-averse policy produces trajectories with lower variance\". It is also not clear there how the risk-averse policy is computed. There are no comparisons to existing risk-sensitive RL algorithms. Furthermore, the numerous abbreviations are confusing, e.g., for tasks. In many places, such as the discussion in the appendix, there would be enough space to state the full task title, which would enhance comprehensibility.\n\n*Minor Issues / Typos*\n- L. 8 \"utility-based\"\n- L. 24 \"MDPs\"\n- L. 81 \"the the\"\n- L. 101 \"in the follows\"\n- L. 147 \n- L. 248 \"a\"", "was_revised": true, "final_justification": "The authors have adequately clarified my questions. While I still see the main weakness in the presentation and discussion of the evaluation results, I believe the paper offers valuable contributions, so I am keeping my current rating. I encourage the authors to use the additional page in the camera-ready version to improve the experiments section, especially the discussion of the results.", "rebuttal": "We sincerely thank the reviewer for their careful reading of our paper and for recognizing our contributions. We deeply appreciate the constructive feedback and insightful questions provided. Please note that, unless otherwise specified, the references cited in our responses are consistent with those listed in the appendix.\n\n1. Response to the reviewer's concerns in the \"Weaknesses\" section:\n\n(a) We understand the reviewers concern and will clarify the differences in applicability between the two Q-learning algorithms in the revised version of the paper (also see our response to \"Question.(a)\").\n\n(b) Assumption 2.12 is the Doeblin-type condition. Intuitively, it ensures that certain states are visited infinitely often from any other state under all transition kernels induced by the risk map. For the three classes of risk measures considered in this work, this condition can be decomposed into two parts: Assumption 4.8, which requires a form of strong ergodicity of the Markov chain, and Assumption 4.9, which imposes boundedness on the slope of the loss or spectrum function. While this Doeblin-type condition is sufficient to guarantee the validity of the AROE, it is not necessary. We conjecture that the weaker conditions needed in the risk neutral setting might be sufficient for a broader class of risk measures.\n    \nOn the contrary, Assumption 3.1 is a standard and relatively mild condition commonly used in the context of average-cost problems, see e.g. Abounadi et al., 2001; Wan et al., 2021. Note that Assumption 3.1 is not about the MDP itself, but rather provides flexibility in how the algorithm is implemented.\n\n(c) In the model-based setting, we introduce the risk-aware RVI algorithm as a special case of the more general risk-aware RQI algorithm, differing only in that the value function is replaced by the Q-factor and we directly establish the proof of the risk-aware RQI. Consequently, we treat them as one algorithm.\n\nIn the model-free setting, we present a natural extension of the risk-aware RQI in the form of a MLMC-based Q-learning algorithm, for which we also established the convergence to optimality. As for the UBSR Q-learning algorithm, due to the lack of a theoretical convergence proof, we regard it as a heuristic approach. We assess its empirical performance by comparing it with the risk-aware RVI and MLMC Q-learning algorithms in the experimental section.\n\nTo avoid confusion, we will revise the introduction to clarify which three algorithms are being referred to.\n\n(d) We wish to first respond to the comment \"There are no comparisons to existing risk-sensitive RL algorithms.\" To the best of our knowledge, the only prior work proposing Q-learning algorithms for average risk-aware MDPs with dynamic risk measures has either focused on the risk-neutral setting, the entropic risk measure (Borkar, 2002), or indirectly addressed coherent risk measures (Wang et al., 2023c), as noted in our introduction. None of these prior works can be used as a benchmark when using the risk measures employed in our numerical study. We encourage the reviewer to further comment on potential benchmark that they might have in mind. As a side note, following reviewer RUxx's comment, we plan to add a comparison of the convergence speed of our algorithms with those used in the risk-neutral setting, which may address the reviewer's interest.\n\nRegarding the source of confusion in the presentation of our result, we will make sure to address this issue in the revised version of the paper. \n\n2. Response to the reviewer's concerns in the \"Minor Issues / Typos\" section:\n\nWe adopt the corrections, thank you for pointing out!\n\n3. Response to the reviewer's concerns in the \"Questions\" section:\n\n(a) MLMC Q-learning can be applied to a broad class of dynamic risk measures, while requiring access to repeated samples of transitions from a given state-action pair (i.e. a simulator). In contrast, UBSR Q-learning more closely aligns with the traditional setting of Q-learning, but is dedicated to the specific class of dynamic UBSR measures.\n\nWe note that the convergence of UBSR is not formally proven compared to MLMC, although its rate of convergence appears faster empirically. As a result, UBSR Q-learning may be used to potentially achieve faster computation with dynamic UBSR, whereas MLMC Q-learning is recommended for broader applicability and theoretical guarantees.\n\n(b) As discussed in our response to the \"Weaknesses\" section, Assumption 2.12 can be decomposed into two parts for the three classes of risk measures considered in this work: Assumption 4.8, which entails a form of strong ergodicity for the Markov chain, and Assumption 4.9, which requires boundedness of the slope of the loss or spectrum function. Assumption 4.8 might be considered the most limiting of the two. In an application, it can easily be satisfied by selecting a state as the reference state, and modifying the transition kernel so that any state action may lead to this reference state with $\\epsilon>0$ probability. \n\nWe also conjecture that weaker conditions may suffice for particular types of risk measures. For instance, in the risk-neutral case, the AROE holds under the milder unichain assumption on the underlying Markov chain.\n\nIn terms of checking these assumptions in an application, Assumption 4.9 can be verified based on the definition of the risk measure. Assumption 4.8 would be problem dependent. For example, in a machine replacement problem, it is usually reasonable to assume that the machine always has a positive probability of reaching the failure state. In an inventory problem, it is usually reasonable to assume that inventory could run out during any time step. Now it is true that both verifying or rejecting this assumption with confidence based on data could present a statistical challenge. We expect future research to further explore how ergodicity in Markov chains applies statistically in real-world settings.\n\n(c) We use the risk-aware RVI algorithm. The risk-aware MLMC algorithm would produce similar results. Following your notice, we will add a line in the application section specifying the algorithm being used.\n\n(d) The term \"optimal risk'' refers to the risk value obtained by applying the algorithm aligned with the corresponding risk measure, whereas \"expectile risk'' denotes the evaluation of policies generated under various risk measures using the expectile objective. Table 1 demonstrates that our algorithm successfully achieves the optimal risk under each respective risk measure, highlighting its effectiveness and consistency across different objectives.\n\n(e) We attempted to establish the convergence of the UBSR Q-learning algorithm but encountered significant obstacles. The analysis appears to fall outside the scope of standard ODE-based stochastic approximation techniques. Further discussion of these difficulties can be found in the last paragraph of Section C.2.\n\n(f) We believe that our algorithm holds potential for broader real-world applications. However, as is well known, the \"curse of dimensionality'' poses significant challenges to the scalability of dynamic programming methods. As a direction for future work, we aim to develop approximate dynamic programming and deep reinforcement learning techniques to address this limitation.\n\n4. Response to the reviewer's concerns in the \"Limitation\" section:\n\nFollowing your advice, we will add a discussion of extension to high-dimensional cases as a future work in our conclusion part."}, {"review_id": "PGZ32iOU2G", "reviewer": "Reviewer_DGDL", "summary": "This paper studies the risk-aware average-cost MDPs, including the formulation of the Bellman equation, the required assumptions for the problem to be well-posed, and the formulation of the Q-function to be used for model-free reinforcement learning. Essentially, these are the theoretical foundations for RL algorithms to be used in risk-aware average-cost MDPs. \n\nThere are papers studying a special type of risk-aware measures in average-cost MDPs, and this paper generalizes the risk measures that can be used.", "questions": "I have one question: in the analysis of average-cost MDPs, many of the studies use a limit argument. That is, use the discounted formulation and then take the discount factor to 1. This paper doesn't use this type of analysis. Why is that and what type of results would need such an analysis?", "limitations": "- The paper doesn't investigate other types of RL algorithms and discuss their applicability in the risk-aware average-cost setting.", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- I enjoy reading the paper because it is very well written. The concepts, notation, analyses, and results are clearly presented. \n- The discussion on the connection to the literature is very thorough. My understanding is that risk-aware finite-horizon or discounted MDPs have been studied; risk-neural average-cost MDPs have been studied; and this is one of the first papers that studies the general risk-aware average-cost MDPs. \n\nWeaknesses\n- I wish there are more discussions on the challenges in the formulation and analyses of risk-aware average-cost MDPs. It is understood that the average-cost formulation is harder to analyze than the discounted, due to a lack of contraction. What additional difficulties are introduced when risk-aware objectives are introduced versus the risk-neutral version? Will the challenges persist for other classes of RL algorithms such as value/policy approximation, policy gradient, etc? Such a discussion can help position this paper and its contribution.", "was_revised": true, "final_justification": "I thank the authors for their response. My score remains.", "rebuttal": "We are sincerely grateful to the reviewer for the thorough reading of our paper and for acknowledging its contributions. We greatly appreciate the constructive feedback and thoughtful questions. Please note that, unless otherwise specified, the references cited in our responses correspond to those included in the appendix.\n\n1. Response to the reviewer's concerns in the \"Weaknesses\" section:\n\nIncorporating risk measures introduces additional challenges beyond the risk-neutral setting, particularly in establishing a seminorm contraction property. To address this, Shen et al., 2013 proposed a Doeblin-type condition (Assumption 2.12), which provides a theoretical foundation for ensuring such seminorm contraction. However, these difficulties remain when extending the AROE framework to other classes of dynamic programming and RL algorithms. In response to your suggestion, we will include a more detailed discussion of the Doeblin-type condition in the next revision of the paper.\n\n2. Response to the reviewer's concerns in the \"Questions\" section:\n\nThe treatment of discounting differs significantly depending on whether the discount factor $\\gamma$ is applied directly to the cost function or to the risk measure. The former leads to a time-inconsistent dynamic risk measure and may induce non-stationary optimal policies, thereby complicating the analysis (also see the discussion in Section 5.1 of Shen et al., 2013). In contrast, applying discounting to the risk measure results in a time-consistent formulation. However, unlike the risk-neutral case, even for well-studied risk measures such as the entropic risk, the vanishing discount approach may fail to converge or may produce a different limit, as discussed in Jaskiewicz 2007. That work also provides sufficient conditions under which the vanishing discount method is valid for entropic risk measure. We conjecture that similar results may hold for other classes of risk measures under appropriate assumptions, but a thorough investigation is beyond the scope of this paper and is left for future research.\n\nReferences: \n\nA. Jaskiewicz. Average optimality for risk-sensitive control with general state space. *The Annals of Applied Probability*, 17(2): 654-675, 2007.\n\n3. Response to the reviewer's concerns in the \"Limitations\" section:\n\nFollowing your suggestion, we will include a discussion on potential extensions to other RL algorithms as part of our future work in the revised version."}, {"review_id": "e9o3d29swS", "reviewer": "Reviewer_DpJC", "summary": "The paper addresses risk-aware average MDPs. First, the authors propose a risk-aware relative value iteration algorithm (model-based) to solve average risk-aware MDPs when considering dynamic risk measures. Then, the authors introduce two model-free algorithms and theoretically analyze them. The authors empirically show the algorithms converge to the right quantities and run them in three environments considered by previous works in the field of risk-aware MDPs.", "questions": "- What does the paragraph that starts in line 48 has to do with the present work? One thing is risk-awareness (risk-aware MDPs), other thing is robustness to unknown dynamics (distributionally robust MDPs). Please clarify it as it is not clear why such cited works matter for the context of risk-awareness.\n\n- Maybe the authors could add a bit more about the differences between the dynamic risk measures considered in this work and standard risk measures applied to the random return yielded by the interaction between a given policy and the MDP. In the later setting it is known that Markovian policies do not suffice for optimality, so I was wondering if the authors could provide more details regarding the difference between the two formulations and why they decided to go with the former (i.e., why do they decided to consider dynamic risk measures).\n\n- \"Remark 2.15. Assumption 2.12 is a sufficient condition for the existence of an optimal average risk independent of the initial state and is stronger than the unichain assumption commonly used in risk neutral average MDPs.\" - How easy is it to verify whether this assumption holds in practical problems? I ask this question because even verifying whether the MDP is unichain is already a hard task.\n\n- In Tab. 1, I did not understand what is the exact difference between the \"optimal risk\" and the \"expectile risk\" column. Could the authors clarify? \n\nMinor comments/typos:\n- \"The condition we impose for convergence are weak\" -> \"conditions\"? (line 65); \"In the follows, we (...)\" (line 101).", "limitations": "The authors discuss the limitations of their assumptions throughout the work. Some of them are standard (e.g., step size assumptions), while others seem more stringent. Unfortunately, I lack the background knowledge to assess the impact of some of the assumptions used.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The clarity of the paper could be improved, particularly in the introduction. There are some sentences that are a bit unclear. E.g. \"(...) the randomness of the environment is usually unknown, highlighting the importance of developing model-free learning algorithms.\" (line 37-38). However, I do not believe this should be a reason to reject the paper, but I ask the authors to review their introduction. The contributions are clearly stated. The assumptions are stated and discussed thoughout the document.\n\nThe organization of the paper could be slightly improved. In particular, I suggest moving Sec. 5.2 (which introduces a new method) to Sec. 4, and keep only the experiments in Sec. 5.\n\nThe experimental section of the paper (and respective discussion) should be further extended. First, in Tab. 1, I did not understand what is the exact difference between the \"optimal risk\" and the \"expectile risk\" column. Could the authors clarify? Maybe this should be made clearer in the text. Second, since the authors propose multiple algorithms, why don't the authors run them and show that they achieve similar performances?\n\nThe paper seems original, though I am not familiarized with the previous works cited.\n\nRegarding the quality and correctness of the paper, I cannot provide an accurate assessment of them as I am not familiarized with the previous works cited by the authors. The paper is quite technical and, here and there, I got a bit lost reading it, but I believe it was likely because I miss some background knowledge regarding some of the concepts used by the authors.", "was_revised": true, "final_justification": "The authors addressed my main concerns in the rebuttal. I strongly encourage the authors to revise the manuscript following the suggestions provided. I am keeping my score and leaning towards acceptance of the paper.", "rebuttal": "We sincerely thank the reviewer for carefully reading our paper. We greatly value the constructive feedback and insightful questions. Please note that, unless otherwise specified, the references cited in our responses align with those provided in the appendix.\n\n1. Response to the reviewer's concerns in the \"Weaknesses\" section:\n\n(a) In response to your suggestion, we will revise the introduction in the next version of the paper to make it clearer.\n\n(b) As we do not have a convergence proof of the UBSR Q-learning algorithm, we initially decided to present UBSR Q-learning as a heuristic in Section 5. Following your suggestion, we will consider presenting all model-free algorithms in Section 4 when preparing the revision.\n\n(c) The term \"optimal risk'' refers to the risk value obtained by applying the algorithm aligned with the corresponding risk measure, whereas \"expectile risk'' denotes the evaluation of policies generated under various risk measures using the expectile objective. Table 1 demonstrates that our algorithm successfully achieves the optimal risk under each respective risk measure, highlighting its effectiveness and consistency across different objectives. In line with your suggestion, we will include a detailed explanation of Table 1 in the revised version of the paper.\n\nThe comparative performance of the algorithms proposed in this paper under a common setting is presented in Section 5.1 (for RVI and MLMC Q-learning) and Appendix C.2 (for RVI and UBSR Q-learning). It is important to note that the OCE risk measure used in Section 5.1 is not a UBSR measure, which is why the UBSR Q-learning algorithm is not included in Figure 5.1. The comparisons involving MLMC and UBSR Q-learning algorithms are provided in Figure 5.2 and Table 3 (in Appendix C.2). We believe that these results clearly highlight the distinctive behaviors and strengths of our proposed methods.\n\n2. Response to the reviewer's concerns in the \"Questions\" section:\n\n(a) It has been established in the literature (see e.g Artzner et al., 1999) that coherent risk measures can be interpreted as distributionally robust optimization problems, and vice versa. This connection links our work to the distributionally robust MDP literature. We will rewrite this paragraph to clarify the connections with distributionally robust MDPs.\n\n(b) Yes, it is well known that MDPs with static risk measure objectives suffer from time inconsistency, often resulting in optimal policies that are history-dependent. In contrast, the framework of dynamic risk measures provides a systematic approach to constructing time-consistent risk formulations, under which optimal stationary policies can be derived; see Ruszczynski 2010 for further details. This is the primary motivation for our focus on dynamic, rather than static, formulations of risk measures in this work.\n\n(c) Assumption 2.12 (the Doeblin-type condition) imposes joint restrictions on both the underlying Markov chain and the chosen risk measure. This condition can be decomposed into two parts: Assumption 4.8, which requires a form of strong ergodicity of the Markov chain, and Assumption 4.9, which imposes boundedness on the slope of the loss or spectrum function when employing one of the three classes of risk measures considered in this work.\n\nIn applications, Assumption 4.9 can be verified based on the definition of the measure. Assumption 4.8 would be problem dependent. For example, in a machine replacement problem, it is usually reasonable to assume that the machine always has a positive probability of reaching the failure state. In an inventory problem, it is usually reasonable to assume that inventory could run out during any time step. Now it is true that both verifying and rejecting these assumption with statistical confidence could present a practical challenge. We expect future research to further explore how ergodicity in Markov chains applies statistically in real-world settings.\n\nWe finally note that one way of ensuring that 4.9 is satisfied consists in selecting a state as the reference state, and modifying the transition kernel so that any state action may lead to this reference state with $\\epsilon>0$ probability. \n\n(d) The term \"optimal risk'' refers to the risk value obtained by applying the algorithm aligned with the corresponding risk measure, whereas \"expectile risk'' denotes the evaluation of policies generated under various risk measures using the expectile objective. Table 1 demonstrates that our algorithm successfully achieves the optimal risk under each respective risk measure, highlighting its effectiveness and consistency across different objectives. Following your suggestion, we will add a detailed clarification of Table 1 when preparing the revision.\n\nReferences:  \n\nP. Artzner, F. Delbaen, J. M. Eber, D. Heath. Coherent measures of risk. *Mathematical Finance*. 9(3):203-28, 1999.\n\n3. Response to the reviewer's concerns in the \"Minor comments/typos\" section:\n\nWe implement the corrections, thank you for pointing out!"}]

Author rebuttal:

Meta-review: This paper makes significant contributions on an underexplored problem of risk-aware average-cost MDPs. The key highlight is in rigorous and nontrivial proofs on the convergence of the proposed algorithms for this problem. The reviewers unanimously give positive ratings, and some of them highly value the theoretical results. A weakness is in the limited empirical support, but the strengths outweigh weaknesses.
Decision: Accept (poster)