Risk-Aware Reinforcement Learning with Coherent Risk Measures and Non-linear Function Approximation
Authors: Thanh Lam
Arun Verma
Bryan Kian Hsiang Low
Patrick Jaillet
Venue: ICLR 2023 poster (2023)
Keywords: Risk-Aware Reinforcement Learning
Coherent Risk Measures
Non-linear Function Approximation

Abstract: We study the risk-aware reinforcement learning (RL) problem in the episodic finite-horizon Markov decision process with unknown transition and reward functions. In contrast to the risk-neutral RL problem, we consider minimizing the risk of having low rewards, which arise due to the intrinsic randomness of the MDPs and imperfect knowledge of the model. Our work provides a unified framework to analyze the regret of risk-aware RL policy with coherent risk measures in conjunction with non-linear function approximation, which gives the first sub-linear regret bounds in the setting. Finally, we validate our theoretical results via empirical experiments on synthetic and real-world data.

Published as a conference paper at ICLR 2023
RISK-AWARE REINFORCEMENT LEARNING WITH COHERENT RISK MEASURES AND NON-LINEAR FUNCTION APPROXIMATION
Thanh Lam!
Arun Verma" Bryan Kian Hsiang Low
Patrick Jaillet
'Department of Computer Science, National University of Singapore, Republic of Singapore *Department of Electrical Engineering and Computer Science, MIT, USA (chithanb, arun, lowkh) @comp nus edu.sgt jaillet@mitt.e edu
ABSTRACT
We study the risk-aware reinforcement learning (RL) problem in the episodic finite-horizon Markov decision process with unknown transition and reward functions. In contrast the risk-neutral RL problem, we consider minimizing the risk of having low rewards, which arise due to the intrinsic randomness of the MDPs and imperfect knowledge of the model. Our work provides a unified framework to analyze the regret of risk-aware RL policy with coherent risk measures in conjunction with non-linear function approximation, which gives the first sub-linear regret bounds in the setting, Finally, validate our theoretical results via empirical experiments on synthetic and real-world data.
INTRODUCTION
Reinforcement learning (RL) (Sutton & Barto, 2018) is control-theoretic problem in which an agent interacts with an unknown environment and aims to maximize its expected total reward. Due to the intrinsic randomness of the environment, even a policy with high expected total rewards may occasionally produce very low rewards. This uncertainty is problematic many real-life applications like competitive games (Mnih et al., 2013) and healthcare (Liu et al., 2020). where the agent (or decision-maker needs to be rvsk-everse For example, the drug responses to patients are stochastic due to the patients' varying physiology genetic profiles (McMahon & Insel, 2012); therefore, it is desirable to select a set of treatments that yield high effectiveness and minimize the possibility of adverse effects (Beutler al., 2016; Fatemi et al., 2021). The existing RL policies that maximize the risk-neutral total reward can not lead to an optimal risk-aware RL policy for problems where the total reward has uncertainty (Yu al., 2018). Therefore, our goal is to design an RL algorithm that learns a risk-aware RL policy to minimize the risk of having a small expected total reward.
Then, how should we learn risk-aware RL policy? natural approach is to directly learn risk-aware RL policy that minimizes the risk of having a small expected total reward (Howard & Matheson, 1972). For quantifying such a risk, one can use risk measures like entropic risk (Föllmer & Knispel, 2011), value-at-risk (VaR) (Dempster, 2002), conditional value-at-risk (CVaR) (Rockafellar et al., 2000), or entropic value-at-risk (EVaR) (Ahmadi-Javide 2012). These risk measures capture the total reward volatility and quantify the possibility of rare but catastrophic events. The entropic risk measure can be viewed as a mean-variance criterion, where the risk is expressed as the variance of total reward (Fei et al., 2021). Alternatively, VaR, CVaR, and EVaR use quantile criteria, which are often preferable for better risk management over the mean-variance criterion (Chapter 3 of Kisiala (2015)). Among these risk measures, coherent risk measures' such as CVaR and EVaR are preferred as they enjoy compelling theoretical properties such as coherence (Rockafellar et al., 2000).
The risk-aware RL algorithms with CVaR risk measure (Bäuerle & Out, 2011; Yu al., 2018; Rigter et al., 2021) exist in the literature. However, apart from being customized only for CVaR, these algorithms suffer two significant shortcomings. First, most of them focus on the tabular MDP setting and need multiple complete traversals of the state space (Bäuerle & Oit, 2011; I; Rigter et al.,
Apart from CVaR and EVAR, the risk measures like g-entropic risk measures, Tail value-at at risk, Proportional Hazard (PH) risk measure, Wang risk measure, and Superhedging price also helong to the coherent risk family. More details about various coherent risk measures are given in Appendix C.

---

Published as a conference paper at ICLR 2023
2021). These traversals prohibitively expensive for problems with large state space and impossible for problems with continuous state space, thus limiting these algorithms' applicability in practice. Second, the existing algorithms considering continuous or infinite state space assume that MDP is known, i.e., the probability transitions and reward of each state are known a priori to the algorithm. In such settings, the agent does not need to explore or generalize to unseen scenarios. Therefore, the problem considered in Yu et al. (2018) is planning problem rather than a learning problem. This paper alleviates both shortcomings by proposing new risk-aware RL algorithm where MDPs are unknown and uses non non-linear function approximation for addressing continuous state space.
Recent works (Jin et al., 2020; Yang et al., 2020) have proposed RL algorithms with function approximation and finite-sample regret guarantees, but they only focus on the risk-neutral RL setting Extending their results to risk-aware RI. setting is non-trivial due two major challenges. First, the existing analyses heavily rely on the linearity of the expectation in the risk-neutral Bellman equation. This linearity property does not hold the risk-aware RI. setting when coherent risk measure replaces the expectation in the Bellman equation. Then, how can we address this challenge? We overcome this challenge by the non- non-trivial application of the super-additivity property² of coherent risk measures (see Lemma 3 and its application in Appendix 4).
The estimate of the Bellman update (Yang et al., 2020) as the risk-neutral Bellman equation with a single sample. However, this does not hold in the risk-aware RL setting. Furthermore, whether one can construct an unbiased estimate of arbitrary risk measure using only one sample is unknown. This problem leads to the second major challenge: how can we construct an unbiased estimate of the risk-aware Bellman update? ? To resolve this challenge, we assume access to a weak simulator' that can sample different next states given the current state and action and use these samples to construct an unbiased estimator. Such an assumption is mild and holds in many real-world applications, e.g., player can anticipate the opponent's 's next moves and hence the possible next states of the game. After resolving both challenges, we propose an algorithm that uses a risk-aware value iteration procedure based on the upper confidence bound (UCB) and has a simile sub-linear regret upper bound. Specifically, our contributions are as follows:
RL algorithms only need one sample of the next state to construct an unbiased unbiasedly estimate the expectation in
We first formalize the risk-aware RL setting with coherent risk measures, namely the risk-aware objective function and the risk-aware Bellman equation in Section 3. We then introduce the notion of regret for a risk-aware RL policy.
We propose a general risk-aware RL algorithm named Risk-Aware Upper Confidence Bound (RA-UCB) for an entire class of coherent risk measures in Section 4. RA-UCB uses UCB-based value functions with non-linear function approximation and also enjoys a finite-sample sub-linear regret upper bound guarantee.
We provide a unified framework to analyze regret for any coherent risk measure in Section 4.1. The novelty in our analysis is in the decomposition of risk-aware RL policy's ssicy's regret by the addiiivddy property of coherent risk measures (shown in the proof of Lemma 4 in Appendix D.2).
.
Our empirical experiments on synthetic and real datasets validate the different performance aspects of our proposed algorithm in Section
1.1 RELATED WORK
Risk-aware MDPs first introduced in the seminal work of Howard & Matheson (1972) with the use of an exponential utility function known as the entropic risk measure. Since then, the aisk- MDPs have been studied with different risk criteria: optimizing moments of the total reward (Jaquette, 1973), exponential utility or entropic risk (Borkar, 2001; 2002; Bäuerle & Rieder, 2014; Fei et al., 2020; 2021; Moharrami et al., 2022), mean-variance criterion (Sobel, 1982; Li & Ng, 2000; La Ghavamzadeh, 2013; Tamar et al., 2016), and conditional value-at-risk (Boda & Filar, 2006; Artzner et al., 2007; Bäuerle & Mundt, 2009; Bäuerle & Ott, 2011: Tamar et al., 2015; Yu ct al., 2018; Rigter et al., 2021). Vadori et al. (2020) focuses the variability or uncertainty of the rewards.
auppr--aditiiitt in the reward maximization setting becomes sub-additivity in the cost minimization setting. Note that the weak simulator can only sample possible next states and returns no information regarding the rewards. In this sense, our simulator weaker than the archetypal simulators often assumed in the RL. literature.
2

---

Published as a conference paper at ICLR 2023
Many of these existing works assume the MDPs are known a priori (known reward and transition kernels) (Yu et al., 2018), focus on the optimization problem (Bäuerle & Ott, 2011: Yu et al., 2018) or asymptotic behaviors of algorithms (e.g., does an optimal policy exist, and if so, is it Markovian, etc.) (Bäuerle & Ott, 201 I; Bäuerle & Rieder, 2014). The closest works to ours are Fei et al. (2021); Fei & Xu (2022), which consider the risk-aware reinforcement learning in the function approximation and regret minimization setting. However, they use the entropic risk measure. In contrast, our work considers a significantly different family of risk measures, namely the coherent risk measures. They are preferable and widely used for risk management (Kisiala, 2015). The analysis in Fei et al. (2021); Fei & Xu (2022) utilizes technique called exponentiated Bellman equation, which is uniquely applicable to the entropic risk measure (or more generally the exponential utility family) and cannot be readily extended to coherent risk measures. Therefore, our analysis differs significantly from that in Fei et al. (2021); Fei & Xu (2022). Tamaa et al. (2015) proposes an actor-critic algorithm for the entire class of coherent risk measures but does not provide any thcoretical analysis of the regret.
Safe RL and constrained MDPs represent parallel approach to obtaining risk-aware policies in the presence of uncertainty. Unlike risk-aware MDPs, safe RL does not modify the optimality criteria. Instead, the risk-aversion is captured via constraints the rewards risks (Chow & Pavone, 2013; Chow et al., 2017), or as chance constraints (Ono et al., 2015; Chow et al., 2017). Compared with risk-aware MDPs, the constrained MDPs approach enjoys less compelling theoretical properties. The existence of a global optimal Markov policy using the constrained MDPs is unknown, and many existing algorithms only return locally optimal Markov policies using gradient-based techniques. makes these methods extremely susceptible to policy initialization (Chow et al., 2017), and hence the best theoretical result one can get in this setting is convergence locally optimal policy (Chow et al., 2017). In contrast, our result in this paper considers the regret (or sub-optimality) with respect to the global optimal policy.
Distributional RL (Bellemare et al., 2022) attempts to model the state-value distribution, and any risk measure can be characterized by such distribution. Therefore, distributional RI. represents more ambitious approach in which the agent needs to estimate the entire value distribution. Existing distributional RL algorithms need to make additional distributional assumptions to work with distributional estimates such quantiles (Dabney et al., 2018) empirical distributions (Rowland et al., 2018). In contrast, our risk-aware RL. framework only considers the risk measures that apply to the random state-value, As trade-off, the demand for data and computational resources to estimate the value distribution at every state can be prohibitively expensive for even moderate-sizer problems. We establish more detailed connections between risk-aware RL and distribution RL in Appendix A.
COHERENT RISK MEASURES
Let Z E (0, be a real-valued random variable with a finite mean and the cumulative distribution function F2(2) = P(Z < 2). For Z' e (R, TP), function p (2, R U {+o0} is a coherent risk measure it satisfies the following properties:
1. Normalized: p(0) = 0.
2. Monotonic: If PP2 < Z') = 1, then p(Z) S p(Z').
3. Super-additive: p(Z + Z') 2 p(Z) p(Z').
4. Positively homogeneous: For 2 0, we have p(aZ) ap(Z).
5. Translation invariant: For constant variable A with value a, we have p(Z + A) +(Z)+++ +a.
Since our reward maximization setting contrasts with the cost minimization setting often considered in the literature, we aim to maximize the risk applied to the random reward, i.e., maximizing (Z). Consequently, the properties of risk measure are upended compared to those usually presented in cost minimization setting (Föllmer & Schied, 2010). For example, super-additivity in the reward maximization setting becomes aoddtiiitittty in the cost minimization setting.
Empirical estimation of the risk. The risk of random variable p(Z) is completely determined by the distribution of (F2). In practice, we do not know the distribution Fz; instead, we can observe
In our risk-aware RI setting, the random variable Z represents the random total reward of the agent.
3

---

Published as a conference paper at ICLR 2023
independent and identically distributed (IID) samples {Zr from the distribution Fz. Then can use these samples to get an empirical estimator p(Z), which denoted by 1( 1....... Zm).
3 PROBLEM SETTING
We consider an episodic finite-horizon Markov decision process (MDP), denoted by a tuple M (S, A. H. P,r),, where S and A are sets of possible states and actions, respectively. H E 24 is the episode length, IP = ( he(m are the state transition probability measures, and r = {rr. S S A [0. [[rr)[FF= are the deterministic reward functions. We assume is measurable space of possibly infinite cardinality, and A is finite set. For each h E [H]] Pr,, (-|r, a) denotes the probability transition kernel when the agent takes action at state x in time step h.
An agent interacts with the MDP as follows. There are T episodes. In the t-th episode, the agent begins at state æi chosen arbitrarily by the environment. In each step /t E [f]] the agent observes a state 2) E S, selects an action d A, and receives a reward rAA (21 o.).. The MDP then transitions to the next state following the probability transition kernel x hh11 ~ Pt. ( af). The episode
terminates when the agent reaches state ##+1 at time step + 1. In the last time step, the agent takes no action and receives no reward.
policy и of an agent is sequence of functions, i.e., ग (TA ]e[H], in which each TA (-1ar) is a probability distribution over A. Here, TA (a(z) indicates the probability that the agent takes action at state in time step h. Any policy and an initial state determine a probability measure P and an associated stochastic process {(2,, az), h E [H]] Let Ey, [-] denote the expectation operator with respect to P The standard risk-neutral MDP objective is
E Σ (a an)
3.1 RISK-AWARE EPISODIC MDP
The risk-neutral objective defined in Eq. (1) does not account for the risk incurred due to the stochasticity in the state transitions and the agent's policy. Markov risk measures (Ruszczyński, 2010) proposed to model and analyze such risks. The risk- MDP objective is defined
max (x1), where (²1(z) = (1 a1) + p(r2 02) + p(ra(13, 0a) + +...)), (2) 7
where P is coherent one-step conditional risk measure (Ruszczyński, 2010, Definition 6), and {21, 01 Z2, o2....} }o is a trajectory of states and actions from the MDP under policy æ. Here, J is defined as nested and multi-stage composition of p. rather than through single-stage risk measure on the cumulative reward p( Σ Th (I ax)).
The choice of the risk-aware objective function in Eq. (2) has two advantages. Firstly, it guarantees the existence of an optimal policy, and furthermore, this optimal policy Markovian. Please refer to Theorem 4 in Ruszczyúski (2010) for rigorous treatment of the existence of the optimal Markov policy. Secondly, the above risk-aware objective satisfies the time consistency property. This property ensures that we do not contradict ourselves in our risk evaluation. The sequence that is better today should continue to be better tomorrow, i.c., our risk preference stays the same over time. Note that in standard RL, where the risk measure is replaced with expectation, this property is trivially satisfied. In contrast, a single-stage risk measure (i.e., static version) applied on the cumulative reward p( " (2h, an)) does not enjoy this time consistency property (Ruszczyfiski, 2010).
More detailed discussions about this are in Appendix B.
3.2 BELLMAN EQUATION AND REGRET
The risk-aware Bellman equation is developed for the risk-aware objective defined in Eq. (2) (Ruszczyúski, 2010). More specifically, us define the risk-aware state- and action-value functions with respect to the Markov risk measure p
V (Ir) = ra(a, (x(x)) + p (TTNt (IN41, That (In+1)) + e(rn 220 +((n-22200nnp ( +...),
4

---

Published as a conference paper at ICLR 2023
(E(z,))=T(x.,) + pl (f ( + p Th+2(2n+2)) + +...))
We also define the optimal policy nt to be the policy that yields the optimal value function [ (z)
sup, Vi," (x). The advantage of the formulation given in Eq. (2) is that one can show that the optimal policy exists, and it is Markovian (Theorem 4 of Ruszezyúski (2010). For notations convenience, for any measurable function V S - |0, H), we define the operator Dj, as
(z,)) p
(3)
where the risk measure p is taken over the random variable x' ~ PP,(-12,, a). Bellman equation associated with a policy æ takes the form
Then, the risk-aware
(T, (rx + VVV (z, (z) (QT -), (+1=)) v
0,
where (A denote the inner product' over A and (f + (1) = f(x) g(x)) for function f and g-
Similarly, the Bellman optimality equation is given by
(2 a) (rn + 1
Vi max Q7 (2,, a), (x+ 0.
(4)
aEA
The above equation implies that the optimal policy n¹ is the greedy policy with respect to the optimal action-value function {Qi, he|H)-
In the episodic MDP setting, the agent interacts with the environment through T episodes to learn the optimal policy. At the beginning of episode i, the agent selects a policy x", and the environment chooses an initial state xf. The difference in values between V (z]) and (zf)) quantifies the
sub-optimality of T², which serves as the regret of the agent at episode The total regret after T episodes is defined as
T
Rp) = Σ - (z1) [=1
(5)
We use the widely adopted notion of regret the risk-neutral setting (Jin et al., 2020; Yang et al., 2020)
and risk-aware setting (Fei et al., 2020; 2021). Here, the policy's 's regret depends on the risk measure via the optimal policy x² A good policy should have sub-linear regret, i.e., limy- R = 0. which implies that the policy will eventually learn to select the best risk-averse actions.
Remark 1. Given two risk measures P1 and P2 with (p1) < (p2),, does not imply P1 is a better choice of risk measure for the given problem. Because the optimal policies for P1 and p2 can be different, their regrets are not directly comparable. Therefore, we cannot use regret as a measure to compare or select the risk measure.
3.3 WEAK SIMULATOR ASSUMPTION
One key challenge for the risk-aware RL policy is that the empirical estimation of risk is more complex than the estimation of expectation in rest-nl RL (Yu et al., 2018). In this paper, we assume the existence of weak simulator that we can use to draw samples from the probability transition kernel (- a) for any h E [ x E S, S.a E A. This assumption is much weaker than the archetypal simulator assumptions often seen the RL literature, as they also allow query reward of given state and action (I, a). To the best of our knowledge, all existing works in risk-aware RL with coherent risk measures require some assumptions on the transition probabilities facilitate the risk estimation procedure. Among these assumptions, our weak simulator assumption is the weakest.
3.4 ESTIMATING NON-LINEAR FUNCTIONS
We use reproducing kernel Hilbert space (RKHS) as the class non-linear functions to represent the optimal action-value function Qi For notational convenience, let us denote = (xx, a) and Z = S A. Following the standard setting, we assume that Z is compact subset of Ed for fixed dimension d. Let H denote the RKHS defined on Z with the kernel function k : Z x Z + R. Let ) and || be the inner product and the RKHS norm H. respectively. Since H is an RKHS, there exists a feature map Ø: Z + H such that ((2) = k(z,) -) and f(z) = (o(=). f for all f E H and for all E 2, this is known the reproducing kernel property.
Since A is finite set, the inner product over is the canonical inner product on Euclidean vector space.
5

---

Published as a conference paper at ICLR 2023
4 RISK-AWARE RL ALGORITHM WITH COHERENT RISK MEASURES
We now introduce our algorithm named Risk-Aware Upper Confidence Bound (RA-UCB), which is built upon the celebrated Value Iteration Algorithm (Sutton & Barto, 2018). RA-UCB first estimates the value function using kernel least-square regression. Then, it computes an optimistic bonus that gets added the estimated value function to encourage exploration. Finally, it executes the greedy policy with respect to the estimated value function in the next episode.
RA-UCB Aware
ware Upper Confidence Bound
Input: Hyperparameters of coherent risk measure p (e.g., confidence level a E (0, 1) for CVaR)
2: for episode f 1,2..... .... do
3: Receive the initial state xf and initialize V as the zero function.
4: for step h = H ...., , do
5:
For T E [ - 1]. draw m samples from the weak simulator and construct the response vector Uf, using Eq. (7).
6:
Compute μ and of using Eq. (8).
7: Compute Q and V using Eq. (9).
8:
end for
9:
for step h = ...... do
10:
Take action aj. +- arg max 0% (1%) a). aEA
11:
Observe reward rı a and the next state 2
12:
end for
13:
end for
Recall that defined (xr, a) and 2 = S A in Section 3.4. We define the following Gram
matrix Kj E ()) and a function kt, Z - R--1 associated with the RKHS H. as
K [<<]] 2h 7,
kx (z) [k<2/, 2)..,, k(t (12/_1,,,
,=]]]
(6)
Given the observed histories and the weak simulator, we define the response vector yf E RR-1 as
will = (xx, aT) + p( (Z)
where (=(8) ym next states drawn from the weak simulator Pa(-10%, a.) This step contains of the key differences between RA-UCB and its risk-neutral counterpart, with the presence of the empirical risk estimator in the definition of the response vector yf. With the newly introduced notations, we define two functions p4
I and or + R as
(z) kg, (z) K + X vi.
(8) The terms p1,, and of, have several important connections with other literature. More specifically, it resembles the posterior mean and standard deviation of Gaussian process regression problem (Rasmussen, 2003), with ví. as its target. The second term of also reduces to the UCB term used in linear bandits when the feature map is finite-dimensional (Lattimore Szepesvári, 2020). We then define our estimate of the value functions Qi and VA as follows:
-=)== [k(2, 2) - kt. (2)
(K). + A1) -
Q (z. a) == min (1) a) + B B (x, a), H h h+1),
v=() max (z)a),
(9)
where 3 > 0 is exploration versus exploitation trade-off parameter.
To get some insights on the algorithm, notice that Eq. (7) implements the one-step Bellman optimality update in Eq. (4). To see this, let X' P& Pa a be the random variable representing the next state. Recall that V is the estimated value function by our algorithm at episode t. Thus, Vii(()) also a random variable, where the randomness comes from X'. Here, we can start looking at p ((ViL,(X') i.e., the risk measure P applied on the random variable V (X'). Intuitively, this can be interpreted as the adjjutedd value of the next state. The second term in Eq. (7) above, ((VV4 (V44z(1//)) (4((g) )m ) is empirical estimate of (V++t((X))

---

Published as a conference paper at ICLR 2023
The choice of the response vector in Eq. (7) represents the primary novelty in our algorithm design. This choice enables a new regret decomposition and an upper bound using the concentration inequality of the risk estimator. More details are presented in Appendix D.1.
4.1 MAIN THEORETICAL RESULTS
This section presents our main theoretical result, i.e., the regret upper bound guarantee of RA-UCB. We first outline the key assumption that enables the efficient approximation of the value function.
Assumption 1. Let R >> O be fixed constant, H be the RKHS, and ((r) = {f E H || N S r to be the RKHS-norm ball with radius r. We assume that for any [H] and any Q 8 x A - [0, H). we have Q E (RHH), where Tł, is the Bellman optimality operator defined in Eq. (4).
This assumption postulates that the risk-aware Bellman optimality operator maps any bounded action-value function to a function in an RKHS H with a bounded norm. This assumption ensures that for all h E [H] the optimal action-valle value function 2 lies inside (RHH) Consequently, there is no approximation eтror when using functions from H to approximate Qh- It can be viewed as equivalent to the realizability assumption in supervised learning. Similar assumptions are made in Jin et al. (2020); Yang et al. (2020); Zanette et al. (2020). Please refer to Du et al. (2019) for a discussion on the necessity of this assumption.
Given this assumption, it is clear that the complexity of H plays central role in the regret bound of RA-UCB. Following the seminal work of Srinivas et al. (2009), we characterize the intrinsic complexity of H. with the notion of maximum information gain defined as
[T A) 1/2
sup DEZ,IDIST
{ log det(I + Kp/A)]
(10)
where k is the kernel function, A > 0 is a parameter, and KD is the Gram matrix. The maximum information gain depends on how fast the eigenvalues of H decay to zero and can be viewed as a proxy for the dimension of H. when 7/ is infinite-dins dimensional. Note that T (T, A) is a deedlem-dependent quantity that depends on the kernel k, state space S, and action space A. Furthermore, let us first define the action-value function classes Quch (h, R, B) as
Quch (h, R B) = {Q:
Q(2) min 8- 1- f E 1lflll S R. R.33 E [0, DI TT)
k=(=) (KD+ ko) h 13+,
(11)
With the appropriate choice of R and B, the set Quch (h, R, B) contains every possible Q1 that can be constructed by RA-UCB. Therefore, the function class Queh resembles the concept of hypothesis space in supervised learning. And as we will see, the complexity of Queb, in particular, the covering number of Qucb. plays crucial role in the regret bound of RA-UCB.
Theorem 1. Let A = 1+ 1/T, 3 = BT in RA-UCB, and let [T, A) be the maximal information gain defined in Eq. (10). Define a constant BT > that satisfies BT =
- max+eH / /log Noc (c. BT))). Suppose that the empirical risk estimate P achieves the rate of 8(m,8), i.e., P[]p(Z) p(12, )mm 1) I 5(m, 2 1 5. Then, under Assumption 1, with
probability of at least (22 the regret of RA-UCB is
Ry S 5B (T,)) + 2TH E (m, (8T
The proof of Theorem 1 is in Appendix D.I. The regret upper bound consists of two terms. The first term resembles fisk-neutrll regret bound (Yang et al., 2020, Theorem 4.2). Interestingly, our bound distinguishes itself from the risk-neutral setting with the presence of the second term, which quantifies how fast one can estimate the risk from observed samples. It originates from the risk-aware Bellman optimality equation, in which the one-step update requires knowledge of the risk-to-go go starting from the next state (see Eq. (4) for more detail). This risk-to-go quantity is approximated by its empirical counterpart, and the discrepancies give rise to the second term in regret.
Due to the weak simulator assumption, we have good control over the second term. In the following result, we derive the number of samples sufficient to achieve the order-optimal regret for the Conditional Value-at-Re Risk (CVaR), which is one of the most commonly used coherent risk measures. More details on CVaR and its properties are given in Appendix C.I.
7

---

Published as a conference paper at ICLR 2023
Corollary 1. Let p be the CVaR measure defined in Eq. (13) and P be the CVaR estimator defined in Eq. (14). Then, under the same conditions Theorem 1, the algorithm RA- ACB achieves the regret of RT = O(Br (BBHHyTTA(T,N))) X)) with
(
Flog.og log (TTTT)B
total samples (across all T episodes) from the weak simulator.
The detailed proof of Corollary 1 is in Appendix D.5. As example, for the commonly used squared exponential (SE) kernel, get B1 O(H Vlog (TH) (log TY*) (Yang al., 2020, Corollary and (T, >) O ((log (Srinivas al., 2009), and thus RA-UCB incurs regret of Ri = [ (HH2vT((lg 1 This result leads to the first sub-linear regret upper bound of the risk- RL policy with coherent risk measures.
5 EXPERIMENTS
In this section, we empirically demonstrate the effectiveness of RA-UCB. We run different experiments on synthetic and real-world data with the CVaR as a risk measure, which is commonly used coherent risk measure. We analyze the influence of the risk aversion parameter (or confidence level for CVaR) on the total reward as well as the behavior of the output policies. The code for these experiments is available in the supplementary material.
5.1 SYNTHETIC EXPERIMENT: ROBOT NAVIGATION
The robot navigation environment is continuous version of the cliff walking problem considered in example 6.6 of Sutton & Barto (2018), visualized in robot must
Fig. 1. In this synthetic experiment, navigate inside a room full obstacles to reach its goal destination. The robot navigates by choosing from 4 actions (up. down, left, right). Since the floor is slippery, the direction of movement is perturbed by r Ø. where @ ~ U--x, T and r E [0, represent the angle and magnitude of the perturbation. The robot receives a positive reward of 10 for reaching the destination and negative reward for being close to obstacles. The negative reward increases exponentially as the robot comes close to the obstacle. We set the horizon of each episode to H = 30. The robot does not know perturbation parameters (r = 0.3) and the obstacles' positions, so it has to learn them online via interacting with the environment. We approximate the state-action value function using the RBF kernel and the Ke R dge regressor from Scikit-learn.
poston
Figure 1: Illustaaioon of the continuous
version of the cliff walking problem. The robot starts at (0, 0) and must navigate to the goal area (in green). The robot gets negative rewards for being close to the obstacles and receives reward of 10 upon reaching the goal.
Nererd
0.3
6.5
6:0
Back
Figure 2: Estimated distribution of the cumulative reward when following the learned policy for different risk parameters. For 0.9 (leftmost plot), the policy is more risk-tolerant, which causes the average reward be higher, but occasionally small. As we decrease a, the policy becomes more risk-averse, favoring safer paths with smaller average rewards and higher worst-case rewards.
8

---

Published as a conference paper at ICLR 2023
In Fig. 2, we show the histograms of the robot's cumulative rewards that it receives in 50 episodes by following the learned policy with different values of the risk parameter a E [0.9, 0.5, 0.1]. For smaller values of a, the learned policy successfully mitigates the tail risk in the distribution, illustrated by the rightmost histogram having the smallest reward of at least 3.0, whereas the reward could go as low near 0 for the remaining two policies. As increase a, the policy becomes more risk-tolerant, leading to a higher average reward at the expense of occasional bad rewards. In this experiment, we use m 100 samples from the weak simulator to estimate the risk in Eq. (7).
5.2 REAL-WORLD EXPERIMENT: TRADING
This trading setup is generalization of the betting game environment (Bäuerle & Ott, 2011; Rigter et 202,) This experiment considers simplified foreign exchange trading environment based on real historical exchange rates and volumes between EUR and USD in 12 months of 2017. For simplicity, fixed the trade volume for each hour 10000.
0.9
a 0.1
Probab it
There are two actions in the environment: buy or sell. The state of the environment includes the current position, which is either long or short, and vector of signal features containing the historical prices and trading volumes over short period time. We customize this environment based on the Forexšnv in the python package gym-anytradinng
-0.2
0.0
0.2
0.4
0.6
0.8
10
Rewards
Figure 3: Estimated distribution of the normalized terminal wealth following the learned policy for different risk parameters. The vertical lines represent the average rewards. When a 0.9 (the blue bar), the policy is more risk-tolerant, which causes the average reward to be higher at the expense of occasional low reward. The policy is more risk-averse as we decrease the value of a, favoring safe paths with lower average-case rewards and higher worst-case rewards.
In Fig. 3, show histogram of the cumulative terminal wealth achieved by the agents in 100 episodes with different risk parameters, plotted in different colors. Similar to the robot experiment, demonstrate that for smaller value of a, the policy is risk-averse and successfully mitigates the tail of the distribution. This can be seen that the worst-case wealth for = 0.1 (in green) is higher than for 0.5 (in red) a 0.9 (in blue). In this experiment, we use = 100 samples from the weak simulator to estimate the risk in Eq. (7). Additional experiments with other risk measures like VaR and EVaR are given in Appendix E.
We need to solve H kernel ridge regression problems in each episode. In the f-th episode, each regression problem complexity is dominated by two operations: First, the inversion of the Gram matrix Kj, of size (t 1) (t 1) in Eq. (8), which has O(t3) time complexity and (t²2) space complexity. Second, the construction of the response vector Eq. (7) has (mt) time and space complexity. Therefore, the time and space complexity of the t-episode is (H + md)) and O(H (t2 + mt)) respectively.
Computational complexity of RA-UCB:
CONCLUSION
proposed risk-aware RL algorithm named RA-UCB that uses coherent risk measures and non-linear function approximations. We then provided finite-sample regret upper bound guarantee for RA-UCB and demonstrated its effectiveness in robot navigation and forex trading environments.
The performance of the proposed algorithm depends profoundly on the quality of the empirical risk estimator. This paper assumes access to weak simulator that can sample the next states, thus effectively alleviating the need to estimate the risk from the observed trajectories. Therefore, potential future direction is to relax or weaken this assumption, allowing risk-aware RL algorithms to be useful in more practical problems. Another interesting direction is consider the episodic MDPs, where episodes can have varying lengths horizons or even infinite horizons.
'The package gym-anyt ng is available at

---

Published as a conference paper at ICLR 2023
7 REPRODUCIBILITY STATEMENT
In this paper, we dedicate a substantial effort to improving the reproducibility and comprehensibility of both our theoretical results and empirical experiments. We formally state and discuss the necessity and implications of our assumptions (please see Section 3.3 and the paragraph below Assumption 1) before presenting our theoretical results. We also provide 3-step proof sketch of our main theoretical result. For each step, we present the key ideas and high-level directions and refer the reader to more detailed and complete proofs the Appendices. For the experiments, we provide details different experimental settings in Section 5, and include our code in the supplementary material.
ACKNOWLEDGMENTS
This research is part of the programme DesCartes and is supported by the National Research Foundation, Prime Minister's Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme. C. T. Lam is supported by the Singapore-MIT Alliance for Research and Technology (SMART) PhD Fellowship.
REFERENCES
Carlo Acerbi and Dirk Tasche. On the coherence of expected shortfall. Journal of Banking & Finance, 26(7):1487-1503, 2002.
Amir Ahmadi-Javid. An information-theoretic approach constructing coherent risk measures. In 2011 IEEE International Symposium on Information Theory Proceedings, pp. 2125-2127. IEEE, 2011.
Amir Ahmadi-Javid. Entropic value-at-risk: A new coherent risk measure. Journal of Optimization Theory and Applications, 155(3): 1105-111, 2012.
Syed Mumtaz Ali and Samuel D Silvey. A general class of coefficients of divergence of one distribution from another. Journal of the Royal Statistical Society: Series B (Methodological) 28 (1):131-142, 1966.
Philippe Artzner, Freddy Delbaen, Jean-Marc Eber, David Heath, and Hyejin Ku. Coherent multiperiod risk adjusted values and bellman's 's principle. Annals of Operations Research, 152(1): 5-22, 2007.
Kazuoki Azuma. Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, Second Series, 19(3)33773377, 1967.
Dorian Baudry, Romain Gautron, Emilie Kaufmann, and Odalric Maillard. Optimal thompson sampling strategies for support-aware evar bandits. In International Conference on Machine Learning, pp. 716-726. PMLR, 2021.
Nicole Bäuerle and André Mundt. Dynamic mean-risk optimization a binomial model. Mathematical Methods of Operations Research, 70(2):219-25 2299, 2009.
Nicole Bäuerle and Jonathan Ott. Markov decision processes with average-valuu-attrisk criteria. Mathematical Methods of Operations Research, 74(3):361-379, 2011.
Nicole Bäuerle and Ulrich Rieder. More risk-sensitive markov decision processes. Mathematics of Operations Research, 39(1):105-120, 2014.
Mare G. Bellemare, Will Dabney, and Mark Rowland. Distributional Reinforcement Learning. MIT Press, 2022. http://wwww.iistriutttonlll....
Larry E Beutler, Kathleen Someah, Satoko Kimpara, and Kimberley Miller. Selecting the most appropriate treatment for each patient. International Journal of Clinical and Health Psychology, 16(1):99-108, 2016.
Kang Boda and Jerzy A Filar. Time consistent dynamic risk measures. Mathematical Methods of Operations Research, 63(1):169-186, 2006.
10

---

Published as a conference paper at ICLR 2023
Vivek S Borkar. A sensitivity formula for risk cost and the actor aitor-critic algorithm. Systems & Control Letters, 44(5):339-344 -36, 2001.
Vivek S Borkar. Q-learning for risk- control. Mathematics of operations research, 27(2): 294-311, 2002.
Yin-Lam Chow and Marco Pavone. Stochastic optimal control with dynamic, time-consistent risk constraints. In 2013 American Control Conference, pp. 390-395, IEEE, 2013.
Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone. Risk-constrained reinforcement learning with percentile risk criteria. The Journal of Machine Learning Research, 18(1):6070-6120, 2017.
Imre Csiszár. Information-type measures of difference of probability distributions and indirect observation. studia scientiarum Mathematicarum Hungarica, 2:229-318, 1967.
Will Dabney, Georg Ostrovski, David Silver, and Rémi Munos. Implicit quantile networks for distributional reinforcement learning. In International conference on machine learning, pp. 1105. PMLR, 2018.
Michael Alan Howarth Dempster. Risk management: value at risk and beyond. Cambridge University Press, 2002.
Simon $ Du, Sham M Kakade, Ruosong Wang, and Lin F Yang. Is good representation sufficient for sample efficient reinforcement learning? arXiv preprint arXiv:1910.03011 2019.
Mehdi Fatemi, Taylor W Killian, Jayakumar Subramanian, and Marzyeh Ghassemi. Medical dead-ends and learning to identify high-risk states and treatments. Advances in Neural Information Processing Systems, 34, 2021.
Yingjie Fei and Ruitu Xu. Cascaded gaps: Towards logarithmic regret for risk-sensitive reinforcement learning. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 6392-6417. PMLR, 17-23 Jul 2022.
Yingjie Fei, Zhuoran Yang, Yudong Chen, Zhaoran Wang. and Qiaomin Xie. Risk-sensitive reinforcement learning: Near-optimal risk-sample tradeoff in regret. Advances in Neural Information Processing Systems, 33:22384-22395, 2020.
Yingjie Fei, Zhuoran Yang, and Zhaoran Wang. Risk-sensitive reinforcement learning with function approximation: A debiasing approach. In International Conference on Machine Learning, pp. 3198-3207. PMLR, 2021.
Hans Föllmer and Thomas Knispel. Entropic risk measures: Coherence vs. convexity, model ambiguity and robust large deviations. Stochastics and Dynamics, 1((02003):333-355
2011. 2011
Hans Föllmer and Alexander Schied. Convex and coherent risk measures. Encyclopedia of Quantitative Finance, pp. 355-363, 2010.
Ronald A Howard and James E Matheson. Risk-sensitive markov decision processes. Management science, 18(7):356-369 1972.
Stratton C Jaquette. Markov decision processes with a new optimality criterion: Discrete time. The Annals of Statistics, 1(3):496-505, 1973.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137-2143. PMLR, 2020.
Ramtin Keramati, Christoph Dann, Alex Tamkin, and Emma Brunskill. Being optimistic to be conservative: Quickly learning cvar policy. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 1436-4443 2020.
11

---

Published as a conference paper at ICLR 2023
Jakob Kisiala. Conditional value-at-risk: Theory and applications. arXiv preprint arXiv:1511.00140 2015.
Solomon Kullback and Richard Leibler. mathematical statistics, 22(1):79-86, 1951.
On information and sufficiency. The annals of
Prashanth La and Mohammad Ghavamzadeh. Actor-critic algorithms for risk-sensitive mdps.
Advances in neural information processing systems, 26, 2013.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Duan Li and Wan-Lung Ng. Optimal dynamic portfolio selection: Multiperiod mean-variance
formulation. Mathematical finance, 10(3):387-406, 2000.
Friedrich Liese and Igor Vajda. On divergences and informations in statistics and information theory. IEEE Transactions on Information Theory, 52(10):439444412, 2006.
Siqi Liu, Kay Choong See, Kee
Yuan Ngiam, Leo Anthony Celi, Xingzhi Sun, Mengling Feng, al. Reinforcement learning for clinical decision support critical care: comprehensive review. Journal of medical Internet research, 2e 18477, 2020.
Andreas Löhne and Birgit Rudloff. An algorithm for calculating the set of superhedging portfolios in markets with transaction costs. International Journal of Theoretical and Applied Finance, 17(02): 1450012, 2014.
Francis J McMahon and Thomas R Insel. Pharmacogenomics and personalized medicine in neuropsychiatry. Neuron, 74(5):773-776, 2012.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013.
Mehrdad Moharrami, Yashaswini Murthy, Arghyadip Roy, and R Srikant. A policy gradient algorithm for the risk-sensitive exponential cost mdp. arXiv preprint arXiv:220..041557 2022.
Suresh H Moolgavkar, Ellen T Chang, Heather N Watson, and Edmund C Lau. An assessment of the cox proportional hazards regression model for epidemiologic studies. Risk Analysis, 38(4): 777-794, 2018
Xinyi Ni and Lifeng Lai. Policy gradient based entropic-var optimization in risk-sensitive reinforcement learning. In 2022 58th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1-6. IEEE, 2022a.
Xinyi Ni and Lifeng Lai. Evar optimization for risk-sensitive reinforcement learning. IEEE Transactions on Information Theory, 2022b.
Masahiro Ono, Marco Pavone, Yoshiaki Kuwata, and J Balaram. Chance-constrained dynamic programming with application to risk-aware robotic space exploration. Autonomous Robots, 39(4): 555-571, 2015.
Carl Edward Rasmussen. Gaussian processes in machine learning. In Summer school on machine learning, pp. 63-71. Springer, 2003.
Mare Rigter, Bruno Lacerda, and Nick Hawes. Risk-averse bdyesvad reinforcement learning. Advances in Neural Information Processing Systems, 34, 2021.
R Tyrrell Rockafellar and Stanislav Uryasev. Conditional value-at-risk for general loss distributions. Journal of banking & finance, 26(7):1443-144 2002.
Tyrrell Rockafellar, Stanislav Uryasev, et al. Optimization of conditional value-at-risk. Journal of risk. 2:21-42, 2000.
Mark Rowland. Mare Bellemare. Will Dabney, Rémi Munos, and Yee Whye Teh. An analysis of categorical distributional reinforcement learning. International Conference on Artificial Intelligence and Statistics, pp. 29-37. PMLR, 2018.
12

---

Published as a conference paper at ICLR 2023
Eliana Rulli, Francesca Ghilotti, Elena Biagioli, Luca Porcu, Mirko Marabese, Maurizio D' Innaalci, Rino Bellocco, and Valter Torri. Assessment of proportional hazard assumption in aggregate data: systematic review statistical methodology in clinical trials using time-to-event endpoint. British journal of cancer, 119(12)1456--1463 2018.
Andrzej Ruszczyúski. Risk-averse dynamic programming for markov decision processes.
Mathematical programming, 125(2):235-205 261, 2010.
Matthew J Sobel. The variance of discounted markov decision processes. Journal of Applied Probability, 19(4):794-002 1982.
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. arXiv:0912.3995, 2009.
arXiv preprint
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Aviv Tamar, Yinlam Chow, Mohammad Ghavamzadeh, and Shie Mannor. Policy gradient for coherent risk measures. Advances in neural information processing systems, 28, 2015.
Aviv Tamar, Dotan Di Castro, and Shie Mannor. Learning the variance of the reward-to-go The Journal of Machine Learning Research, 17(1):361-366 2016.
Aman Ullah. Entropy, divergence and distance measures with econometric applications. Journal of Statistical Planning and Inference, 4911)1377- 1996.
Nelson Vadori, Sumitra Ganesh, Prashant Reddy, and Manuela Veloso. Risk-sensitive reinforcement learning: martingale approach to reward uncertainty. In Proceedings of the First ACM International Conference on in Finance, pp. 1-9, 2020.
Shaun S Wang. A class of distortion operators for pricing financial and insurance risks. Journal of risk and insurance, pp. 15-36, 2000.
Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael Jordan. On function approximation in reinforcement learning: Optimism in the face of large state spaces. arXiv preprint arXiv:2011.0400 2020.
Pengqian Yu, William Haskell, and Huan Xu. Approximate value iteration for risk-aware markov decision processes. IEEE Transactions Automatic Control, 63(9):3335-3122, 2018.
Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Conference Artificial Intelligence and Statistics, pp.
PMLR, 2020.
13

---

Published as a conference paper at ICLR 2023
A CONNECTIONS TO DISTRIBUTIONAL RL
We first give brief survey on the distributional RL literature and discuss its connection to risk-sensitive RL. For a policy æ distributional RL, we define the total reward from state æ (or state-actin action pair (z, a)) and time step the sum of rewards of agent starting in time h, at state x (or state-action pair (z, a)), and the following policy и as follows
H
(T)(
=
Σ
The (a an)) = n, an ~ The
~ Pr (- ax);
k=
H
(2, a) = Σ
(ow ( |2h = 2, an a, as The(- Jhe41 ~ Pie (Ne aw)
h/=h
Both (x) and (x, a) are random variables where the randomness comes from the transition probability P and the (possibly stochastic) policy In standard MDP, the expected value of these random variables, [ (z) and E [1,
(x. a)], are known as the value function and action-value function, respectively. Distributional RL (Bellemare al., 2022) is built upon the overarching idea of estimating the value distribution, i.e., the distribution of the random variables G (x) and J (x, a), rather than just the expected values as in standard RL. The most important component of distributional RL is the distributional Bellman equation, which is given as follows:
[ d r2(2, a) JK (x', arg max E[J (2' a'EA
where Ah [H] and denotes equality in distribution, and the next state x' PA (- a). Although distributional RL models the entire value distribution, notice that the optimal action is greedy with respect to the expectation the value of the next state, which resembles that standard RL.
B COHERENT ONE-STEP CONDITIONAL RISK MEASURE
Recall the formulation of the risk-aware MDP objective function given Eq, (2):
max J (xI),
where ("(xx) = 1ı (I ( a1) + p(r2(22, + p(r3(13, 03) +)..)),
where P is a coherent one-step conditional risk measure, and I1, a1, 32, a..... trajectory of states and actions from the MDP under policy π. Notice that _ is defined as nested and multi-stage composition of conditional risk measure p. which also referred to as the dynamic risk optimization problem (Rigter et al., 2021, use CVaR as risk measure). There are two advantages to this formulation.
Firstly, one can show that the optimal policy exists, and it is Markovian (Theorem 4 in Ruszczyúski (2010).. Therefore, we can use the Bellman update to learn the risk-aware RL policy. When the
objective function uses single-stage risk measure the sum of rewards (i.e., P Eh (a an) the problem is referred to as the static risk optimization. Under this setting, (Bäuerle & Ott, 2011, also use CVaR risk measure) shows that the optimal policy exists but is non-Markovian. Therefore, these history-dependent policies must optimally solve the static risk optimization problem, which is harder than learning a Markovian policy.
Secondly, the above risk-aware objective satisfies the time consistency property. Intuitively, the time consistency property indicates that the sequence that better today should continue to better tomorrow, i.c., risk preference stays the same over time. To formally define this concept, let us consider the problem of measuring the risk of sequences.
Let (Ω, F,IP) denote probability space with filtration Fi C C... C FT C.F Let Zi.... ZT denote the adapted sequence random variables (one may view this as sequence of random rewards for the purpose of this paper). Finally, define 2,
[1, (0), and Z = Z, x ... x Zr. We define the following notion of conditional risk measure and dynamic risk measure follows:
14

---

Published as a conference paper at ICLR 2023
Definition 1. A conditional risk measure is mapping Ptr Z Ze that satisfies the following monotonicity condition:
Pt. S (w) for all Z, Z.W& E 2,, such that S W.
sequence of conditional risk measures: Jt=l....,. is called a dynamic risk measure.
One can view the conditional risk measure as a non-linear extension of the conditional expectation. The randomness of the entire sequence t..... T is reduced to the randomness time t. This is analogous to conditional expectation in which E| + ................................ Zr Zi] is random variable where the randomness comes from Z..
Intuitively, (t,r Zr) represents the amount reward a player is willing to take in exchange For risk-neutral player, that amount will
for sequence of future random rewards Z, + Zr. equal Ei + ... Zr]
We are now ready define the notion of time consistency.
Definition 2. dynamic risk measure (Pr,T)t=I.... cone-consistent if for all 7, E [T] and < we have the following: If for all T...., 1, Zu W4 and (e, .... ZT) S pe.r(Wo..... Wr), then we have (z,r(Z,,.... ZT) S Pr.r(W (rr.WW...,,TT) WT).
The time-consistency property implies that dynamic risk measure ensures that given the same rewards, the sequence that is better today should also be better tomorrow.
Why is time consistency desirable property? This property ensures that do not contract ourselves in our risk evaluation. If we observe the same realization, the sequence that is better today should continue be better tomorrow. Our risk preference stays the same over time. Note that this property is trivially satisfied in standard RL, where the risk measure is replaced with expectation.
In contrast, single risk measure applied on the cumulative reward p( E In (2 an)) does not enjoy this time consistency property.
C COHERENT RISK MEASURES
C.1 CONDITIONAL VALUE-AT-RISS
Let Z be finite mean random variable, i.e., Z|] < oc, with the cumulative distribution function [z IP < =) (an example to keep in mind is that Z represents the random total reward of learning agent). The value-at-risk at confidence level (0, 1) is defined as
VaR. (Z) = min(2 F2(2) 2 a).
(12)
The minimum is attained because the cumulative distribution function Fz is a non-decreasing and right-continuous function in z. When Fz is strictly increasing (and thus bijective), VaR, (Z) Fz (a). The conditional value-at-risk (also known as the average value-at-risk) at confidence level (0, 1) is defined as?
CV) = / VaR, (Z)
(13)
If Z is continuous random variable, then CVaR, (2) E (2). (Acerbi & Tasche, 2002). From this expression, CVaR, (Z) can be viewed as the average of the worst-case a-fraction of Z. It is easy to see that CVaR, (Z) E[Z]. and as - 0, CVaR,, approaches the worst-case (or robust) realization. An important result of CVaR (Rockafellar & Uryasev, 2002, Theorem 10) (also known the fundamental minimization theorem) is that it can be represented as the solution of convex optimization problem.
Lemma 1. (Keramati al., 2020; Baudry al., 2021) Let Z be finite mean random variable, and let e (o, 1). Then, holds that
CVaR, (Z) = max RER
E [s
2)
max sER $ [)
((12-))]]
Note that the definition of CVaR presented above is different from that in the literature, e.g., in (Rockafellar al., 2000). This is because are treating 7 as rewards and thus maximizing Z, whereas existing works consider Z as costs and consequently minimizing Z.
15

---

Published as a conference paper at ICLR 2023
where (x)* max(x,0) 0} represents the positive part of z. similarly (x) min(0, x) represents the negative part of x, and the maximun point is given by s aaRa
Conditional Value-at-risk is prominent risk measure with extensive applications in stochastic optimization (see Rockafellar et al. (2000) for example). By carefully choosing a, CVaR can be tuned to be sensitive to events with exceptionally low rewards, making it attractive measure. The CVaR is also known for having favorable mathematical properties such as coherence.
risk
Empirical estimation of the risk. Let ......, Zm be i..dd. samples drawn from the distribution Fz, then the empirical estimation of (Z) is given by
CVaR (1Z:)
max
(Zi 8) 3
(14)
SER
CET
Lemma 2. (Lemma 3 in Yu et al. (2018)) Let Zi...., ..,,, Zm
Fz be i.i.d. bounded random
variables, i.e., IP[O & Z, I B] = 1, then we have
PP CVaR.. (12) 2e 52
<2(1+
1
4
-mm= a)²
E(1 ax)
exp
2(2 a02
C.2 COMPARISONS BETWEEN ENTROPIC RISK MEASURE CVAR
The closest work to ours is Fei et al. (2021), which considers the risk-aware RL problem in the function approximation setting. However, they use the entropic risk measure. This section discusses some key differences between the entropic risk measure and CVaR.
Entropic risk measure. For finite-mean random variable Z and a parameter o 0, the entropic risk measure of Z is defined as
(2) = 3 log E|c
The entropic risk measure ER, is the normalized cumulant generating function of Z and is concave and additive for independent random variables (Föllmer Knispel, 2011). Using Taylor expansion, the entropic risk can be expressed as follows:
3
ERa(2) = B[2] Varlz + O(3)).
2
From the above expression, we observe that > induces a risk-tolerant objective and 8 < induces risk-averss one. As B 0, 3R, tends the risk-neutral expectation E(Z).
However, the additivity property of the entropic risk measure may not be desirable many practical scenarios. For example, if eR, + X2, + + Xx)) is the total reward of n i.i.d. random variables, then the reward per random variable is ER, (X,). ), no matter how large n is. Thus, the aggregation of independent risks does not affect 'diversification reduces risks.' In contrast, coherent risk measures like CVaR are super-additive and thus enjoy this property.
C.3 ENTROPIC VALUE-AT-RISKK
Let PP be probability space. Let Z be a finite mean random variable, i.e., E[|Z]] oc, whose moment- geweenttgnerraingggggg function Mz(x) exists for all 2 0. The Entropic Value-ar Miile-at-Riss Risk (EVaR) (Ahmadi-Javid, 2011; 2012) at confidence level a is defined as
Mz(z))
EVaR (2) = inf
2>0
The EVaR admits dual representution as follows:
EVaRi-ole sup QEe
[B (Z))
where Q = 1Q < P
PP) < In a where del denotes the Kullback-Leibler (KL)
divergence of Q with respect to P. This dual representation of the EVaR also reveals the reason behind its name.
16

---

Published as a conference paper at ICLR 2023
C.4 G-ENTROPIC RISK MEASURE
Inspired by the dual representation of EVaR, Ahmadi-Javid (2012) proposes a large class of enformation-theorettie coherent risk measures called g e-entropic risk measures. This new class contains both the CVaR and EVaR.
Let 9 be convex proper function with g(1) 0 and 3 0. The generalized relative entropy of Q with respect to P. denoted by Hy Q), is an information-ty: pseudo-distance (also called divergence measure) from Q to P:
dQ H2(P,Q) (P dp.
This quantity is important divergence measure, initially mentioned in Ali & Silvey (1966); Csiszár (1967), and discussed in more detail in Liese & Vajda (2006); Ullah (1996). For g(z) = 2 In we obtain the Kullback-Leillrr divergence from Q P (Kullback Leibler, 1951).
Let Z be a finite-mean random variable. Then, the g-entropic risk measure with divergence level / is defined as
ERg, sup Eo(Z), QEQ
where P
3). We can show that the CVaR and EVaR special cases of the g-entropic risk measure, with proper choices of and 3. For more comprehensive discussion of the properties of the g-entropic risk measure, please refer to Section Ahmadi-Javid (2012).
C.5 OTHER COHERENT RISK MEASURES
Risk measures like Tail value-at aisk,,k, Proportional Hazard (PH) risk measure, Wang risk measure, and Superhedging price also belong to the family of coherent risk measures. These risk measures have many important applications. For example, Proportional Hazard (PH) risk measure is widely used in healthcare domains such clinical trials (Rulli et al., 2018) () epidemiology (Moolgavkar et al., 2018). Wang risk measure and Superhedging price are commonly used financial applications such asset pricing (Wang, 2000) portfolio optimization (Löhne & Rudloff, 2014).
In the RI. context, CVaR is the most well-known and commonly used risk measure among all coherent risk measures and is relatively well-studied in the literature (Bäuerle & Ott, 2011; Yu al., 2018). Some very recent works (Ni & Lai. 2022a;b) have started investigating the use of EVaR in RL. Unlike our work, the techniques used by Ni & Lai (2022a;b) exploit properties that are unique EVaR and thus cannot be generalized to others in the family of coherent risk measures.
D PROOFS
Before presenting the proofs of the supporting lemmas, we review the properties of coherent risk measures and derive the necessary results needed in our proofs. A coherent risk measure (Föllmer & Schied, 2010) is defined as follows
Definition 3. Let X, Y be two random variables. mapping p is called a coherent risk measure if satisfies the following conditions for all X, Y:
Monotonicity: If X < Y a.s., then p(X) S p(Y).
Translation invariance: If m E, then p(X + m) p(X)
Positive homogeneity: If > 0, then p(aZ) ap(Z).
Super-additivity: p(X Y) p(X) p(Y).
We want to highlight in our paper that we consider maximizing risks of the rewards. It in direct contrast to other papers that consider minimizing risks of the costs. Therefore, properties upended compared to the properties presented Föllmer Schied (2010). The following result presents simple inequality we will use throughout this section.
17

---

Published as a conference paper at ICLR 2023
Lemma 3. For any two state-action value functions f2 :8 A - R, we have
(D) - -D - (f1 fz))
( (z)
Proof. The super-additivity property of p implies that
p(x)+ + pY XX) S p(Y), equivalently,
- -()) -plY X). X).
(15)
In the inequality given Eq. (15), want to highlight the super-additivity properties of p. We emphasize that the statement p(X) p(Y) I p Y) is incorrect since is only positively homogeneous. This argument concludes our proof of inequality.
Let æ' ~ (- a) be the random variable represents the next state by following the transition kernel Ph. by definition of Df, in Eq. (3), we have
(Dffi((z.o) (Dffe)(z, p(f((z')) - p(f((z'))
S-pl ((i(((())) f2(x')))
= --(pp(- (f1- f2)) (z,a),
where the first and last equality follows from the definition of Dj, from Eq. (3), and the inequality is due to Eq. (15).
D.1 PROOF OF THEOREM 1
We first define a few notations to simplify the presentation of the proof. First, we define the -efforal (TD) error
(x,,,)) = (rn + D.V (zz a) Qx a), v(z, a) E SSX A.
(16)
For a trajectory {(=1, af hemm we further define the two following quantities
Ct = (V%((A)) - VT (vt)) (1h of) 2 (1h. af)],
Gr, 1) af) (DRV (ath af)] (V++1(0/+1) V 144 (*)++))
(17)
The random variables G/, and G7,, capture the deviations of the value function due to two sources of randomness in the MDP the randomness of choosing the action of क (-(a))) and drawing next state 2hh+1 1 ~ (- a..). We establish the upper bound in the following steps.
Step 1: Decomposition of the regret.
Lemma 4. We can upper bound the regret
T
H
T
H
T H
R(T) <
II 1=1
Jaz U-)
- Σ
af)) +
Σ
(El. + E.,,,
Famm
(=1 Aml
[=1 hml
where oh Go and Gr,, are defined above.
Proof sketch. We decompose the instantaneous regret at the 1-th episode into
Vi{ - VT (af) - + [V1 VT (af)
To upper bound the first term, we establish an inequality of the form V/₃ V% S S(Vin1 V(+1) for some function f and apply it recursively. This inequality is established using the Bellman equation and the super-additivity property of CVaR. Similar techniques can be applied to the upper bound of the second term. The detailed proof is given in Appendix D.2
Step Upper bounding Term
Lemma 5. Let X 1/T and 3 Br in Algorithm RA-UCB. Then under Assumption with probability at least -
we have that for all I E (T), E [H) E S, and a E A:
-,30 S (1r, a) < 0.
18

---

Published as a conference paper at ICLR 2023
The proof of Lemma 5 is in Appendix D.3. By Lemma Lemma 5, 8/ is negative function, and thus we could upper bound the first term in (I) by 0. We obtain that, with probability of at least
1 -
Term
S
(1 a%))
t=1
h=1
T
H
S 2,3
Σ
(1
which is upper bound of the sum of the bonus terms. Recall that rewrite the bonus term
69 (2) af.) = [o(a af.) (AA)) o(ah, (A af]] 1/2
where A/. =i=l o ( )
1h and z7 the identity operator on H. Then,
H Term I 23 VT
1/2
Ma T (MAA)))((aa)))) ah)
h=1
H
23 VT
(2 log (1 + /A)11//
= =43H- C (T))).
where T& (T, A) is the maximal information gain defined in Eq. (10).
Step Upper bounding Term I.
Lemma 6. For Gt,,, and Gi,, defined in Eq. (17). We have that, with probability least 1 8,
T 11 ΣΣ (C, + &.W 111TTTHHlggl log(2/8) + 2TH 5(m,,6/4TTH)
Proof sketch. We show that (G..) [ is a bounded martingale difference sequence and apply Azuma-Hoeffding concentration incquality. For (e, ()) x inequality the risk estimator. The complete proof is in Appendix D.4
concentration
Setting 8 (2T² gives
Term II /16TH3 log(4T 2TH 3(m, (33-1
Therefore, combining these above results, with probability at least 1 - (1² -1 the regret is bounded by
R(T) S 48H (T&(TA) + 16TT (4 + 2TH E(m, (8T H²)
53H (T, + 2TH E(m, 3 H
Substituting 3 By completes the proof of Theorem 1.
D.2 PROOF OF LEMMA 4
We decompose the instantaneous regret at the t-th episode into
v*(=f) V7 vi((f) vi(at) + V7(at) - Vi (xf).
(B)
We proceed to upper bound the two terms separately. For ease of presentation, we first define the
operator Jy acting functions f S x A + R that map state-action value function to the state value function by following policy π as follows:
(J+ (f(x, (-(x))))
19

---

Published as a conference paper at ICLR 2023
Since the domain of (a. .) and x(-[xr) is a finite set A, the inner product above can be interpreted as an inner product between two Euclidean vectors.
Term (A). By the definitions of the optimal value function, we have (z) (, for all x E S. Similarly, by the definition of V we get (xx = (2, ( for all x E S. Thus, for any & (7), h E [H] x E S, we have
- (z) (x) - (z) = (Q)((,)) -
(2)( (1, =)
(Q%(2,)) () + (z, - (+(+)))
Since Th is the greedy policy with respect to 1% it gives
(Qh ) x (-12%)) (+(x=)) (Q% (zt. ) n1 (+(()))))
max (1 a) $ 0,
aeA
for all 2/ S. As result, we can upper bound the second term by and have (x) (²) < (1, - (z, (+12:)) Jnn (Q% (z).
From the Bellman optimality equation and the definition of the temporal-difference, we get
Qh - Q (rn + D - (rn + DVV - 5%.
D2 DgV + 5%
s < - (Vž+1 - vi++)) + 5%
where the last inequality follows from Lemma 3. Substituting this in the previous derivation gives us
(x) (x) s Jm, ( (- - -- ( Vh+1)) + 5% (x) -J,;; D (Vi+1 Vi++)) (x)) Jxū (-8))r)
(18)
Eq. (18) represents a recursive relation between V/= - V2 and Vn+ - Vit Then, recursively
applying Eq. (18) for all E [H] gives
Vi* V v Df (V² V/²)) - (-8))
< -Jx; D2 (-Jn; Dg - -VV - V(3) - Jag (-55) - Jaz (-59)
= -Ix; DP (Jn; D2( - -(V3* - -V3) + +Jng (-6)) - Jnm (-
II Jx; DR (- (Vz vz))
II Jx; DE (-
H (II
<
Jnz D2) (- (V#+1 -
- V++1))
Jnz D3 Jnn (-8%)
A=1
h=1
1=1
Σ II -=: (58)),
(19)
where the last equality follows due to the fact that Vi+ (x) V1+1 (x) for all S.
Term (B). By definitions of 8h, St,, and C2,, defined Eq. (16) and Eq. (17), we have
(((aa)) - Vo (x = (x(( - VT (af) + (, af) - 5% (1h (x(.)) VA (a(h D2V af) D&VE'' (xh,a)))
20

---

Published as a conference paper at ICLR 2023
+ 1Q% Q1)(2), a/., (hh oh)
(V2 Vo (a/h)) - (0) Q% (2 oh) +
DRVT (2), (Vh+1
(1h+1)) +
(V (1t+1)) - - (1(21 dh)
= -V ( tt + =2,, - (2 af)-
Recursively applying the above gives:
V1((2)) - (x4) = (V2z - V23" (zb) + 4 + 121- - (1
= ((v5 - V3"" (2/)) + 2122 + E2 -2 ab) + E + 2,1 a1)
(V33 - V (2 +
(L,, + +,,,) Σ (1h
h=1
h=1
H
H Σ
= -Vh+1 - VHt +
Σ
(EL, + C2,
(hh dh)
A=1
H
H
Σ h=1
(LL, + (h,p) - Σ ah)
(20)
hm1
where the last equality follows due to the fact that V (xH+1) = VT (IH+1) 0. Combining Eq. (19) and Eq. (20) gives
T
Ri
Eiv - VT (xf))
[=1
Σ (1 EG,, + G., Σ oh (
which concludes the proof of this lemma.
D.3 PROOF OF LEMMA 5
Let á Z + H. denote the feature representation induced by the kernel k, i.e. k(2,2)
(ő(2), (0 ((2))) n. For ease of representation, view <(z) as vector and write o(2) 6(21)
(0(z), ((2 (2)))x to denote the inner product. The kernel regression problem in Eq. (9) becomes
0 - min L( = Σ [ral ah) + +(V H()))) 0J o0
+ + 101
(21)
DEH
We define the feature matrix $/ : H + Rt and the covariance matrix AA : 71 - H as
0/. [o(=))
of 1TJT and AA = Σ (zZ))(=ZZT + AlR = (Φ)) 1/ + ALR
where Ix the identity mapping on H. The Gram matrix K Eq. (6) can be expressed as K; = 4 (D))), and (x) Φ0(2). With these definitions, we can rewrite Eq. (21) as
min L(0) = l 0 + To 8. RE7
The solution to the optimization problem above is given by 0 = (AA) vg. As a result, Q in Eg. (9) can be expressed as Q) (z) <(=) 0z In the rest of this section, to further simplify the T0,
21

---

Published as a conference paper at ICLR 2023
notation, we denote %% as simply & when the context is clear. Since (Φ4 + XI) and (Φ ToTT ob + AIn)
positive definite, and thus invertible, and 4b (Φ + +1)= (Φ d + ) have
- ( + + AIR) - x -
$ (Φ. + +XI) x T (K) + X1)
Consequently, we can write 0% as
0 =
v/. = 2 TKK + '/.
In the sequel, we will bound the temporal-differenee difference error 8, defined in Eq. (16). Since (x) max, 0% (I, a), we have
5 + + - Q2h = T;40+1 - Qhh
where Tý is the Bellman optimality operator. By Assumption Assumption 1, since for any t, h, 2h+1 E (0, H), therefore we have 1h+1 E B(HH). Consequently, there exists 0% H such that for any 2 E 2, Th 2 h+ (z) = x(2) T8 We can write 6(2) as
Φbz) (44))"A(,,02)
-A [ T (L))((2)
= (A + ((t) -1
= + (K) + x1)
Using the above, we can write (0z) 08
((=) k/ (z) (K) + x1) + x0(2) (AA)) -
We have:
<(=) To: - {(2)
(22)
==)= T Φ T ((K, + + y/. - kx)=)) T (K) + - >x(2)) =
(AA))11)
(=) T (K) + XT) (1/ +07)) - xØ(=) -AA))10%
(
We proceed by bounding Term (i) and Term (ii) separately. For Term (ii), by Cauchy-Schwarz inequality:
Term (ii) = [*Φ(2) T (AA)
S (IA(A)) (()) 10%/lH S R <(=))
RRH V (O)=) WH (AA))+
S RH / A (A)) (AT) (AA))16())
= VARH (=).
(23)
where the second last inequality follows from the fact that (Aj, - AIu) is a sesitive-semidefiite operator, which implies for any f E H. we have f (A), Xxxf 2 0.
We continue to bound Term (i) in the rest of this section. For [0, t 1]. the r-entry of the vector (vh, 400)) can be expressed as
[ [+ rr( ah) + (VVVi++
(0 ah) 0h
= =rn(oT, (() + (1V QTi (=%, -((VVi+ (2/1)) )== (1
Combining these above results, we have
[Term (i) = (x) (K) + X/) (w) - +00)) )1
(d(=) Φ (K) -1/h +0%)
22

---

Published as a conference paper at ICLR 2023
l0(z) (AA) $ (uh +0%)
- -1ocE) ((A))
(102 oh)
[ - (DRVit))
s =1((())
Σ ( ah))
(
(DRVA+1) ax)
(24)
(AA)-)
where the last inequality follows from the Cauchy-Schwarz inequality. To bound the RKHS norm in the second term, we apply techniques similar to (Yang et al., 2020) by combining concentration of self-normalized processes and uniform convergence over the function classes that contain V/++ To achieve this, let first define the action-value function classes Queb (h, R, B)
Quc R. B) = (Q:
((2) = min (o + --A42(((2z,)) (n)o-====)) + hoot)) ||Qo S R, 3 E [0, B),1| T).
h 13*,
Let us further define the state-value function classes Vucl (h, h, R, B) as
Vac R. B) (V V<x) = max QTI, a) for Q E Quch R. B)}.
aEA
By (Yang et al., 2020, Lemma C.I), if we set Ri 2HHHHH,,, (T, A), then we have for all E [T], h [H), Vg as defined in Eq. (9) satisfies that V/ E Vueb (h, Rr, Br) where Br is defined in Theorem 1.
We now bound Term by a covering number argument over the function classes Vueb (h, Rr. Br) for h E [H) For any two state-value functions V, V' S - IR, we consider the maximum metric (also known as the Chebyshev metric) d(V, V') = sup,es V(x) - V.)))). For e, B > O, let Na h, B) be the e-covering number of Viab(h, Rr, B) with respect to the metric d, and Noo h, B) as the e-covering number of Queb RT. B) with respect to the maximum metric. Applying (Yang et al., 2020, Lemma E.2) with 8 22
and taking union bound over h E [H] gives
Ma a (
(D
(a()-1
Σ M ah)
a5)
sup
VeVan(bti.Rrr Br)
(A))-1
< 2H log (T + /AAA) + 2H 1(A -)
+ 4/12 log oo (e, h + 1, BT) + log (21 +
uniformly over all E [7]. h [ with probability (2T The first inequality is due to the fact that V E Vueb (h + 1, Rr, Br). According to the algorithm, we set À + 1/T. We further set e" = H/T, the above simplifies to
Σ (()%.1)) [oLVE (z)) (D (arh a
(A6)-1
< 4HH + 2 10HH + 4H² log Noc (E", h + 1, Br) ) 12H² log (TH).
Combining the above result with Eq. (22), Eq. (23), and Eq. (24), gives
(0(2) (0) 0
(z) + 8lg (E" B) 16log (T + 2
4log h 11 + 8 log (TH) + vXR]
Br (2) 3 (6)
(25)
23

---

Published as a conference paper at ICLR 2023
holds uniformly for all t [T], h [H] with probability 1 - (2) The second inequality follows from the fact that va + vb v2(a² b2), and the last inequality follows from the assumption on Br.
Finally, by the definition of the temporal difference error 8), and Eq. (25), have:
8% (2) 0 (2) + S <(() (0) B%)) + Sb, (2) - 25b (2)
which proves the left inequality of Lemma 5. For the right inequality, note that since Q (z) S
H h for all E Z, we have (T)QH++) H - h + 1. Therefore, we have
(=) T - (z)
( h+ max{f(=)) 0% ((z) - (=), 0% (H h + 1)} 00,
<bz) g - min min( + (-))
where the first term is negative due to Eq. (25), and the second term is negative due to the fact that (1+4) s h 1. This completes the proof of Lemma 5.
D.4 PROOF OF LEMMA 6
This section follows Yang et al. (2020) to show (G S2, (e is a bounded martingale difference sequence. We construct the filtration as follows. For any t E [T], E [H]. we define the following oallgerras
Ft, = o (((0o)))))))0000-----00 [|][] U a(aafa)))aan)) de)a)))
Fi,,,2 = (1(xf af) a,)) []x U Uf dieN U Ufz/-11)
where (.) denotes the o-algebra generated by a finite set. Since V/ and O are computed based on trajectories of the first t episodes, they measurable with respect Fr,1,1 Since the action af are sampled from xz(- we have
[ =0. 0.
Thus, applying Azuma-Hoefidiig inequality (Azuma, 1967), we obtain that for all / >> O:
(( E
T
CL >
exp
t²
(26)
H3
We let the right hand side equal to 8/2, yielding
= v I6TT log (4/8).
Next, we bound G2,, using the risk estimator concentration inequality. Recall that the empirical risk estimate و achieves the rate of Emm, 5), i.e.,
(Z S E(m, 2 1-8. 8. By definition, Vi (2f, a p(x') where x' ~ Px (- of.. ). Note that a/,11 is also sampled from Pr (-1th, a. Applying the above inequality, for all & E [T], E [M]] we have
P((p(Z)
(I (x), af) - V (*f+1)) S Emm, 5/((HH)) 2 88/(THH).
(27)
Taking union bound over all [T] and h E [1]] yields
T H
P
( - Vhin < TH E(m, ((m,8/(4TH))) 2 1-54/.
(28)
(=1 1m1
Following similar arguments, we have
T H
P D af)) V (+(4a)))) < TH =(m,6/ 2 1-54
(29)
Finally, performing union bound over 26, 28, and 29 gives with probability at least have
T (Chn + G.N S 16TTH>log(2/0 + 2TH E(m, ())
which concludes the proof of Lemma 6.
24

---

Published as a conference paper at ICLR 2023
D.5 PROOF OF COROLLARY
We first restate CaR empirical risk estimator and its concentration result.
Lemma (Lemma in Yu et al. (2018)) Let Zi...., Zm variables, i.e., P/O < Z - B| 1, vi, then we have
Fz be i.i.d. bounded random
4
-mE? a
P CVaRo (2) - CVaR (12 2
52
1+
exp
E(1
α)
2(2 a2)
where
CVaRa(1Z:)1s
max SER
s
Σ
(Z,- 8)
1=1
Setting the RHS 5, we have
4
-me a)²
8 = 2 1
exp
E(1
2(2 a
or equivalently,
( + 22 a)²
log
de(1 a)
e
For the regret to be order-optimal, we need
c c= Bry (T)
and 6 = (8T
VT
That gives us
T
m 0000(1
BFIA(T,A))
which concludes the proof of Corollary 1.
E ADDITIONAL. EXPERIMENTS
This section provides additional empirical results to demonstrate the effectiveness of RA-UCB. We study the proposed algorithm under various risk measures, namely VaR, CVaR, and EVaR. Refer to Appendix C for a formal introduction and discussion of these risk measures.
The robot navigation environment is similar to the setting in Section 5.1. The robot receives a positive reward of 10 for reaching the destination and negative reward for being close obstacles. The negative reward increases exponentially as the robot comes close to the obstacles. We set the horizon of each episode H 30 and m 100 samples from the weak simulator estimate the risk in Eq. (7). We approximate the state-action value function using the RBF kernel and the Kernel 1 Ri dge regressor from Scikit-leam.
We run RA-UCB for 50 episodes and report the performance of the Iearned policy with three different risk measures, namely Value-at-Riss (VaR), Conditional Value-at-Risk (CVaR), and Entropic Value-at-Risk (EVaR). Each risk measure is evaluated against different values of the risk parameter [0.1, 0.5, 0.9.. We note that VaR is not a coherent risk measure; therefore, our regret upper bound does not apply to VaR. Regardless, VaR is still an important risk measure with many real-world applications and has important connections with CVaR and EVaR.
Fig. 4 shows the robot's 's cumulative rewards following the learned policies after 50 episodes. Each column represents a different risk measure, and each row represents different risk parameter. We observe that the reward distribution changes when vary the risk parameters. For 0.1 (top row), the policies are more risk-averse, favoring safer paths with higher worst-case rewards but having smaller average rewards. As we increase the value of a, 0.5 (middle row), and 0.9 (bottom row), the learned policies become more risk-tolerant, which causes the average rewards to be higher but occasionally small.
We also observe that, for the same risk parameter, CVaR outperforms VaR marginally in terms of average rewards. This gain is because VaR does not control rewards below its value (for instance, you
25

---

Published as a conference paper at ICLR 2023
significantly reduce the smallest rewards below VaR, but the Value-at-Rist will not change). In other words, VaR disregards some parts the distribution. This property can be both good and bad, depending upon the applications. For example. VaR estimates statistically more stable than CVaR estimates. However, in our case, we use a sufficiently high number of samples to estimate the risk values; thus, risk measures that consider the complete distribution, like CVaR EVaR, are slightly more effective.
Furthermore, it can be shown that for the risk parameter a, EVaR more risk-averse than both VaR and CVaR (Ahmadi-Javid, 2012). Our results show that the reward distribution using EVaR (plots the rightmost columns) tends to have lower average rewards but better worst-case rewards.
VaR (or 0.1)
CVaR (a 0.1)
EVaR (ar 0.1)
0.3
0.3
0.3
Proboste
Probeesky
Probasibyy
0.2
0.2
0.1
0.1
0.0
0.0
0.0
Revarda
Rewards
Rewards
0.5)
(a 0.5)
0.5)
0.8
0.3
0.3
Probobiity
Protwaalty
Probablity
0.2
0.2
0.2
0.0
0.0
0.0
VaR 0.9)
CVaR (a 0.9)
EVaR 0.9)
Probasitty
Protwaaky
Probasiity
0.2
0.2
0.2
Rewards
Rewards
Rewards
Figure 4: Histograms show the distribution of the cumulative reward when following the learned policy. The solid lines represent the estimated densities using Gaussian kernels, and the vertical lines represent the mean of the distribution. For 0.1 (top row), the policy is more risk-averse, favoring safer paths with higher worst-case rewards but having smaller average rewards. As we increase a, 0.5 (middle row), and 0.9 (bottom row), the learned policy becomes more risk-tolerant, which causes the average rewards to be higher but occasionally small, Furthermore, for the same risk parameters, e.g., 0.1, EVaR usually has the smallest average but better worst-case rewards. This result also confirms that EVaR is more risk-averse than VaR and CVaR for the same risk parameter (Ahmadi-Javin 2012).
26


Reviews:
[{"review_id": "hCbI-6-_7Y", "reviewer": "Reviewer_yVV1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper introduces a framework for analyzing the regret of risk-aware RL policy with coherent risk measures. The framework is based on an episodic finite-horizon Markov decision process (MDP) instead of the MDP with a discounted factor and infinite horizon. Under this framework, this paper proposes a Risk-Aware Upper Confidence Bound (RA-UCB) for performing value iteration under a coherent risk measure by applying non-linear function approximation. The theoretical results provide the regret upper bound guarantee of RA-UCB. To develop this bound, this paper decomposes the risk-aware RL policy’s egret by the super-additivity property of coherent risk measures and assumes access to a weak simulator. Some empirical results are presented to empirically demonstrate the performance of this algorithm.", "summary_of_the_review": "The quality of this paper is satisfying. The main contribution is presented clearly with strong motivations. The algorithm is novel, and the theoretical results are meaningful. The reviewer lists some weaknesses, but they are minor compared to the contributions. After reviewing the main paper and scanning through the appendix, the reviewer suggests accepting this paper, although it is possible that reviewer dismisses some important problems.", "strength_and_weaknesses": "\n### Strength\n1. The paper is well-structured. The definitions are clear and well-motivated. The proof sketch is easy to follow. \n\n2. To the best of the reviewer's knowledge, the RA-UCB algorithm is novel. The way it defines means and variances of action values is inspiring, especially after acknowledging their similarity with the Gaussian process regression and linear bandits problem, ** although more explanation about the insights is appreciated.**\n\n3. The framework for analyzing the regret of risk-aware RL policy can be scaled to coherent risk measures, as opposed to Fei et al. (2021) which used the entropic risk measure. The theoretical results are meaningful and important, which leads to the first sub-linear regret upper bound of the risk-aware RL policy with coherent risk measures.\n\n\n### Weaknesses\n\n1. The algorithm assumes access to a weak simulator. Although this assumption is less influential compared to the ones in previous works, the algorithm becomes no longer model-free and how to alleviate the assumption will be an important direction.\n\n2. Many previous works have explored implementing risk-sensitive RL with non-linear function approximation. While the related works section covers most of them, it is still unclear whether the difference is significant.\n\n3. The empirical results are weak, but I won't argue for more since the main contribution is on the theory side.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "QqguoTvoHY", "reviewer": "Reviewer_aLWD", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of RL for finite horizon MDPs with possibly infinite state spaces to learn the policy which is optimal according to an objective determined by a coherent risk measure rather than the standard expected return objective.  The proposed algorithm, RA-UCB, learns a RKHS representation for the Q-value function.  A key technical challenge is that a single sample does not suffice to form an estimate of the risk measure, so an assumption is used that a “weak simulator” which can sample the transition dynamics.  While the primary contribution is theoretical, small simulation demonstrate an implementation with CVaR as the risk measure.", "summary_of_the_review": "Overall I like the question asked and technical contributions of the paper, but I have some small technical questions and substantive concerns with the presentation.", "strength_and_weaknesses": "On this positive side I’m appreciative of the overall agenda of risk-aware RL.  I agree that coherent risk measures in particular are interesting.  The idea of using a weak simulator to enable estimating them is nice.  So overall I am quite positive about the theoretical results.\n\nOn the negative side, the paper lacks a related work section.  I was left wondering about the relationship to work such as distributional RL.  While there is a related work section in the appendix, for the purposes of this review I am ignoring it as to do otherwise would be abusive of the page limits.  I do not believe this paper is complete without a proper discussion of related work.\n\nI found the clarity of presentation to be a notable negative.  I discuss this in more detail below, but I have a hard time digging out the insights behind the way the weak simulator is used from the presentation.  On a technical level, I am somewhat concerned about the form of the objective given by equation (2).  The justifications provided for it seem to center around technical convenience (e.g. guaranteeing the optimal policy is Markov).  But how does this form of the objective affect the “meaning” of the risk measure chosen relative to the “static” version?  Finally, while a smaller issue for a paper whose contributions are largely theoretical, it is a bit disappointing that after a pitch about how prior work was specialized for CVaR but this approach was more general, all the experiments only used CVaR.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "77XkuBiXH6Z", "reviewer": "Reviewer_osfS", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposed and analyzed the risk-aware reinforcement learning algorithm RA-UCB with coherent risk measures and non-linear function approximation. ", "summary_of_the_review": "Overall, I feel like this is a solid paper that provides a new approach to analyzing risk-aware RL algorithms under a particular class of risk measures that have never been touched before, which adds to the existing literature in the study of risk-sensitive RL.\n\n===============================\n\nThe rebuttal from the authors address all my questions. I feel like the paper is in general well-written, but the choice of the objective function, as suggested by reviewer aLWD, is still a bit concerning. Therefore, I decide to keep my original score for the paper.", "strength_and_weaknesses": "**Strength:**\n- The paper provides a risk-aware RL algorithm under coherent risk measures with a sub-linear performance guarantee.\n- The authors overcome the challenge of the non-linear Bellman equations through the application of the super additivity property of the measures.\n- A unified framework is proposed for analyzing regrets under coherent risk measures.\n- A number of empirical experiments on both synthetic and real-world datasets showcase the performance of the proposed algorithm.\n\n**Weakness:**\n- There is no matching lower bound provided to show the optimality of the proposed method, and I tend to believe that the algorithm is not optimal in that sense.\n- The algorithm requires an oracle (or simulator) to generate an unbiased estimation of the value functions, and such simulators may not exist in some of the use cases.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster