Efficient Risk-Averse Reinforcement Learning
Authors: Ido Greenberg
Yinlam Chow
Mohammad Ghavamzadeh
Shie Mannor
Venue: NeurIPS 2022 Accept (2022)
Keywords: Reinforcement Learning
safe RL
risk averse RL
risk sensitive RL
sample efficient RL
coherent risk measures
CVaR
blindness to success
cross entropy method
CEM

Abstract: In risk-averse reinforcement learning (RL), the goal is to optimize some risk measure of the returns. A risk measure often focuses on the worst returns out of the agent's experience. As a result, standard methods for risk-averse RL often ignore high-return strategies. We prove that under certain conditions this inevitably leads to a local-optimum barrier, and propose a mechanism we call soft risk to bypass it. We also devise a novel cross entropy module for sampling, which (1) preserves risk aversion despite the soft risk; (2) independently improves sample efficiency. By separating the risk aversion of the sampler and the optimizer, we can sample episodes with poor conditions, yet optimize with respect to successful strategies. We combine these two concepts in CeSoR - Cross-entropy Soft-Risk optimization algorithm - which can be applied on top of any risk-averse policy gradient (PG) method. We demonstrate improved risk aversion in maze navigation, autonomous driving, and resource allocation benchmarks, including in scenarios where standard risk-averse PG completely fails.

Efficient Risk-Averse Reinforcement Learning
Ido Greenberg
Yinlam Chow Google Research yinlamchow@googlee com
Technion
gido@campus technion.cc. ac. i1
Mohammad Ghavamzadeh
Shie Mannor
Google Research ghavanzadgoogle..
Technion, Nvidia Research shie@ee technion ac il
Abstract
In risk-averse reinforcement learning (RL), the goal is optimize some risk mea- sure of the returns. A risk measure often focuses on the worst returns out of the agent's experience. As result, standard methods for risk-averse RL often ignore high-return strategies. We prove that under certain conditions this inevitably leads local-optimum barrier, and propose mechanism call soft risk to bypass it. We also devise a novel cross entropy module for sampling, which (1) preserves risk aversion despite the soft risk; (2) independently improves sample efficiency. By separating the risk aversion of the sampler and the optimizer, we can sample episodes with poor conditions, yet optimize with respect to successful strategies. We combine these two concepts in CeSoR Cross-entropp Soft-Risk optimization algorithm which can be applied on top of any risk-averse policy gradient (PG) method. We demonstrate improved risk aversion in maze navigation, autonomous driving, and resource allocation benchmarks, including in scenarios where stan- dard risk-averse PG completely fails. Our results and CeSoR implementation are available on Github The stand-alone cross entropy module is available on PyPI
Introduction
Risk-averse reinforcement learning (RL) is important for high-stake applications, such as driv- ing, robotic surgery, and finance Vittori et al. 2020]. In contrast to risk-neutral RL, it optimizes a risk measure of the return random variable, rather than its expectation. A popular risk mea- sure is the Conditional Value Risk (CVaR), defined as CVaR, (R) E [R| R S q. (R)), where q.. = inf (=r (n(x)) 2 a} is the a-quantile of the random variable R and Fn is its CDF Intu- itively, CVaR measures the expected return below specific quantile a, also termed the risk level. CVaR optimization is widely researched in the RI. community, e.g., using adjusted policy gradient approaches (CVaR-PG) [Tamar et al. 2015b Hiraoka et al., 2019]. In addition, CVaR is a coherent risk measure, and its optimization is equivalent a robust optimization problem [Chow et al. 2015)
Since risk-averse RL aims avoid the hazardous parts of the environment (e.g., dangerous areas in navigation), CVaR-PG algorithms typically sample a batch of N trajectories (episodes), and then optimize w.r.t. the mean of the oN trajectories with worst returns Tamar et al., 20155] Rajeswaran et al. 2017]. This approach suffers from two major drawbacks: (i) - a of the batch is wasted and excluded from the optimization (where often 0.01 < a 0.05), leading to sample inefficiency: (ii) focusing on the worst episodes inherently overlooks good agent strategies corresponding to high returns phenomenon we refer to as the blindness success.
An illustrative example- the Guarded Maze: Consider the Guarded Maze benchmark (visualized in Figure Id). The goal is reach the target zone (a constant location marked in green), resulting in
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

-300
-10
20
-15
score
-600
46
PG (4/ (63)
(-260
(-11/ (111/227)
GCVaR (-32/-32) -32)
-400
GCVaR (-564/-7744 /-774)
-80
CeSoR (2 (2/-7)
CeSoR (-312 / -541)
CeSoR (-11/-15)
15
episode quantile [%]]
episode quantile [96]
episode quantile [%)
(legend: mean cvarss)
(legend: mean cvarys)
(legend: evarys)
(a) Guarded Maze
(b) Driving Game
(c) Servers Allocation
servers
in use
leader
agent (total cost)
TTS [s]
40
PG (28)
GCVaR
GCVaR (17)
CeSoR
20
CeSoR (15)
GCVaR
60
CeSoR
[min]
(d) CcSoR learns avoid the risk (red) and take the long path to the target (green), whereas GCVaR fails due to blindness to success.
(c) CeSoR maintains safe margin from the leader, while PG has an accident and GCVaR maintains a too conservative distance.
(f) CeSoR handles the exceptional peak in user-requests without pay- ing for as many servers as GCVaR, while PG fails to handle the peak.
Figure 1: Over benchmarks, test results of agents: risk-neutral PG, standard CVaR-PG (GCVaR, Tamar et al. 2015b), ) and our CeSoR. Top: the lower quantiles of the returns distributions. Bottom: sample episodes.
reward of 16 points. However, the guarded zone (in red) may be watched by a guard who demands a payment from any agent that passes by. Every episode, the probability that a guard is present is with average &2 32. That is, the cost of crossing the guarded zone in a certain episode is C' = C1 C2, where C1 ~ (er(Ø1), C2 ~ Eap( (b2) are independent and unknown to the agent. The agent starts at random point the lower half, and every time-step. observing its location, it selects an action: left, right, up or down, with an additive control noise. One point deducted per step. up to 32 deductions.
Φi = 20%, and the payment is exponentially-distiibuee
In this maze, the shortest path maximizes the average return; yet, the longer path is CVaR-optimal, since sometimes short cuts make long delays (Tokienn 1954). However, the standard CVaR-PC optimizer (GCVaR in Figure [ suffers from blindness to success: in a batch N random episodes, the worst oN returns (e.g.. for short path, or not reaching the goal at all. Hence, the desired long path is never even observed by the CVaR-PG optimizer, and cannot be learned.
5%) usually correspond to either encountering a guard in the
Our key insight that the variation returns comes from both environment conditions (epistemic uncertainty) and agent actions (aleatoric uncertainty). We wish to focus the low quantiles w.r.t. the conditions (e.g., costly guard in the short path of the maze), yet to be exposed to the high quantiles the strategies (e.g., taking the long path in the maze). To that end, devise two mechanisms: first, we use a soft risk-level scheduling method, which begins the training with risk neutrality = 1, and gradually shifts the risk aversion to a' of the Cross Entropy method (CE or CEM) (de Boer et al. 2005). aiming to sample the worst parts of the environment. That is, the CEM samples trajectories with more challenging riskier conditions, and the soft risk feeds a larger part of them (a' 2 (x) to the CVaR-PG optimizer. Together, these constitute the Cross-entropy method for Soft-Risk optimization (CeSoR). CeSoR can be applied on top of any CVaR-PG method to learn any differentiable model (c.g.. neural network).
Second, we present novel dynamic- targetttrttttt version
To apply the CEM, we assume have certain control over the environment conditions. For example, in driving we may choose the roads for collecting training data, or in any simulation we may control the environment parameters (e.g., d1, dy in the Guarded Maze). Note that (i) only the CE sampler (not the agent) is aware of the conditions; (ii) their underlying effect is unknown to the sampler and may vary with the agent throughout the training, hence the CEM needs to learn it adaptively.
Contribution: We present the following contribution for algorithms under risk-sensitive MDP problems (as defined in Section

---

1. We analyze the phenomenon of blindness to success in the standard CVaR-PG, and show that leads to a optimum barrier certain environments (Section
2. We analyze the potential increase in sample efficiency - if we could sample directly from the tail of the returns distribution (Section 3.2).
3. We introduce the CeSoR algorithm (Section which modifies any CVaR-PG method with: (i) soft risk mechanism preventing blindness to success; (ii) a novel dynamic-CC method that over-ssmples the riskier realizations of the environment, increasing sample efficiency.
4. We demonstrate the effectiveness of CeSoR in 3 risk-sensitive domains (Section 5 where learns faster and achieves higher returns (both CVaR and mean) than the baseline CVaR-PG.
1.1 Related Work
Optimizing risk in RL is crucial to enforce safety in decision-making [García and Fernández
2013
Paduraru et al. [2021]. It has been long studied through various risk criteria, c.g., mean- -vrannaa |aato
2016 Xie al. 2018), entropic risk measure (Borkar and Meyn 2002 Borkar and Jain, 2014 Fei et al. [021] and distortion risk measures [Vijayan and
all. 2000| Prashanth and Ghavamzadeh| 2013
Prashanth 2021 Tamar al. 2015a derived PG method for general coherent risk measures,
given their risk-envelope representation.
The CVaR risk measure specifically was studied using value iteration [Chow et al. 2015 and distributional RL (Dabney et al.) 20188| Tang et al. 2019) Bodnar et al. 2020] (also discussed in
Appendix H.. CVaR optimization was also shown equivalent to mean optimization under robustness
[Chow et al. 2015). motivating robust-RI. methods (Pinto et al. [207 Godbout et al. 2022]. Yet, PG
remains the most popular approach for CVaR optimization in RL [Tamar et al. [001bb] Raaeswaran
ctt al. 2017 Hiraoka et al. 2019 Huang et 202 and can be flexibly applied to a variety of
use-cases, g.g., mixed mean- CVaR criteria [Chow and Ghavamzadeh 2014 and multi-agent problems
QQu et al. 2021
Optimizing the CVaR for risk levels a <> 1 poses a significant sample efficiency challenge, only small portion of the agent's 's experience is used to optimize its policy [Curi et al.. 2020). |Kramati et al. [2020] used an exploration-based approach to address the sample efficiency. Pessimistic sampling for improved sample efficiency was suggested heuristically by Tamaar et al.] (2015b) using a dedicated value function, but no systematic method was suggested to direct the pessimism level. In this work, use the CEM to control the sampled episodes around the desired risk level a, and demonstrate CVaR optimization for as extreme levels as a 1%. Note that unlike other CE-optimizers in RL [Mannor ct al. 2003 Huang et al. 2021c], we use the CEM for sampling, to support gradient- optimizer.
2 Problem Formulation
Consider Markov Decision Process (MDP) (S, A, Po), corresponding to states, actions, state- transition and reward distribution, discount factor, and initial state distribution, respectively. For any policy parameter 0 E IR", denote by ma the parameterized policy that maps state to probability distribution over actions. Given a -ewwe trajectory 7 = {(s,, a,, rt) rT) the trajectory total return is denoted by R(T) = ET= y'r,. The expected return of a policy Te is defined as (TTE) = ET-pr [R(T)],
where pa (T) = (o0) -1'-1 P(s rt|0t, az (=) (mp is the probability distribution of r in- duced by T.. Under the risk-neutral objective, the PG method uses the gradient V&J(me) to learn 8, aiming to increase the probability of actions that lead to higher returns. In contrast, CVaR-PG methods aim to optimize the risk-averse CVaR, objective (w.It. given risk level a):
(TO) = Er [R(T) R(T)= S q. (R)TT))
where qe. ()) is the a-quantile of the return random variable of policy лe. Thus, CVaR-PG algorithms aim to improve the actions specifically for episodes whose returns are lower than qa Te).
Specifically, given a batch of N trajectories (Tr whose empirical return quantile is d.
a. (( the CVaR gradient estimation is given by (Tamar et al. 2015b]:
N
T
1 TO) aN Σ 1RTT)S (R(T)) )a)
Vo log To (3)
t=
3

---

where w; = P (T.) Ta) is the importance sampling (IS) correction factor for Tú, if TÜ is sampled from a distribution f * p Specifically, as discussed below, we modify the sample distribution using the cross entropy method over context-MDP formulation of the environment.
Context-MDP: As mentioned above, aim focus high-risk environment conditions. To discuss the notion of conditions, given standard MDP, we extend its formulation to a Context-MDP (C-MDP) HHallak et al. 2015). where the context is set of variables that capture (part or all of) the randomness of the original MDP. We define the extension as (S, A, Pc, 7, Po, Doo), where C' E C is sampled from the context space C according to the distribution Dáo parameterized by Φu, and Pc(.) = P(-[C) is the transition and reward distribution conditioned on C. In C-MDP, context-trajectory pair is sampled from the distribution P
do (C,+) = De (C)) (T), where (e) (T The mean and CVaR,, objectives ( (T)) in Equations and 2 are naturally generalized to C-MDP using the distribution P (C, T).
PC (T) Po(so) IT I Po($++1, 7 rel
Once we extend an MDP into C-MDP, we can learn how to modify the context-distribun parameter to sample high-risk contexts and trajectories, focusing the training on high-risk parts of the environment and thus improving sample efficiency. For this, we assume that certain aspects of the training environment (represented by C") can be controlled. This assumption indeed holds in many practical applications - in both simulated and physical environments. For example, consider a data collection procedure for self-driving agent training, which by default samples all driving hours uniformly: C ~ ([0 24)). As the hour may affect traffic and driving patterns, a risk-averss driver would prefer to sample more experience in high-risk hours. To that end, we could re- parameterizze the uniform distribution as, say, (eta(() with do = (1, (note that Beta(1, 1) is the uniform distribution), learn the high-risk hours, and modify é over-sample them. As another example, in the Guarded Maze described above, we can control the parameters 1), d2 of the simulation.
3 Limitations of CVaR-PG
Consider the standard CVaR-PG algorithm, which relies on Equation (3) to apply PG for maximization of (To) of (2). In this section, analyze two major limitations of this algorithm. Section 3.1 analyzes the blindness to success phenomenon, which may bring CVaR-PG learning to a local- optimum deadlock. This will motivate the soft-risk scheduling in Section 4 Section 3.2 analyzes the potential increase in sample efficiency when the environmental context is sampled in correspondence to the tail of the returns distribution. This will motivate the cross-entropy sampler in Section 4
While the analysis focuses on CVaR-PG methods, Appendix H discusses Distributional RL algorithms for CVaR optimization, and demonstrates that similar limitations apply to these methods as well.
3.1 Blindness to Success
We formally analyze how the blindness to success phenomenon can bring the policy learning to a local-optimum deadlock by ignoring successful agent strategies.
Recall the a-quantile of a return distribution gh = min(r FR(a)) (r) 2 a). We first introduce the notion of a tail barrier, corresponding to returns-issriiuttion tail with a constant value.
Definition 1 (Tail barrier). Let E (0, 1]. A policy has an a-tail barrier if Va' E [0, 0 = -.
Note that in any environment with a discrete rewards distribution, a policy is prone to having a tail barrier for some > O. In existing CVaR-PG analysis [Tamar et al., 2015b), such barriers are often overlooked by assuming continuous rewards. For the Guarded Maze, Figure [3c in the appendix demonstrates how standard CV exhibits a 0.9-tail barrier, since as many as 90% of the trajectories reach neither the target nor the guard, and thus have identical low returns.
A tail barrier has destructive effect on CVaR-PG. Consider a CVaR, objective, and a policy ा with a B-tail barrier where 3 > a. Intuitively, any infinitesimal change of cannot affect the CVaR return, since the returns infintesimalll--bbveee of. are identical to those below 1.- That is, any tail barrier wider than a brings the CVaR-PC to a stationary point of type plateau. More formally, consider VaJa of Equation (3) with a 3-tail barrier > ac any trajectory has either 1 R(()) = (if its return is above g.)) or R((:) - g.th = 0 (otherwise), hence the whole gradient vanishes. Such a loss plateau was also observed in specific MDP in Section 5.1 of Huang et al. 2202

---

In practice, a discrepancy between 9% and its estimate 4a (((T)) (used in Equation 3) may prevent the gradient from completely vanishing, if 9. = -6 < 9a ((R((,)) Otherwise, if g. (T)(T,))) - q3 in every subsequent iteration, the gradient remains zero, the policy cannot learn any further, and any trajectory returns beyond 9 will never be even propagated to the optimizer. We refer to this phenomenon as blindness success.
Definition 2 (Blindness to success). Let a risk level E (0, 1) and CVaR-PG training step mo 2 1, and let 3 E (a, 1). Denote by T, I1 the spaces of trajectories and policies, respectively, and by (T } pam the random trajectories in step z my- We denote by B the event of blindness success in the subsequent n steps (and the complementary event by a,3
Bagg = {{{( ((((Tmmr (Tmithii Tm)}
E (T x II)"
Vm: da (a((R(Tm)))) S 9
me mo
Note that Definition uses q3 Tmo (corresponding to step mg) to bound the returns in training steps
m > my, thus indeed represents training stagnation. Theorem shoos that given a 3-tail barrier with
3 a, the probability that CV avoids the blindness to success decreases exponentially with
3 a. For example, for n = 10", a = 0.05, 3 = 0.25, and N 400, we have IP( PP-BB,,p 10
Theorem 1.
Under Definition
s conditions, TP
B a.3
Tiag has B-tail barrier) ne 2N (B-a)
Proof sketch (see the full proof in Appendix A In every step m, we have 9g" Tmo < La (L
only if at least 1 of the returns higher than Qg Fmn We bound the probability of this event using the Hoeffding inequality (Lemma In the complementary event the gradient is 0 (due to the barrier), thus the policy does not change, and the argument can be applied inductively to the next step.
3.2 Variance Reduction and Sample Efficiency
As discussed in Section 2 an MDP can be often re-parameterized as a C-MDP. In terms of the C-MDP, C'VaR samples N context-rraeecoryy pairs from the distribution P% (C, r), and calculates the policy gradients with respect the a.N trajectories with the lowest returns. That is, CVaR-PG aims to follow the policy gradients corresponding to the tail distribution defined by
P $q.0 (C,T) = a = ( (C,
Notice that by considering only of the trajectories, CVaR-PG essentially suffers from a rredccctio in sample efficiency in comparison to risk-neutral PG.
Proposition I shows that if we could sample trajectories directly from p og.o. we would reduce the variance of the policy gradient estimate (and thus increase the sample efficiency) back by a factor of a-1, This will motivate the CEM in Section 4 which will aim to modify ó such that p p
Propusition ( (Variance reduction). If the quantile estimation error is negligible (qa = qa (R| in
Equation 3)) then
Var Par phe Sova
(fo a- Var Var=,-pn0 (VJo(((T)) m)).
Proof sketch (see the full proof in Appendix P Since the left term corresponds to the sample distri- bution pro a the corresponding IS weights are w = a w.p. 1. When applying IS analysis to the expected value, w cancels out the distributional shift (as in Equation resulting in the same expected gradient estimate. When applying the same analysis to the variance, we begin with the square weight w², thus a = a factor still remains after the distributional shift compensation.
The variance reduction can be connected to sample efficiency through the convergence rate as follows. According to Theorem 5.5 in Xu et al. [2020), denoting the initial parameters by lg the convergence of any CVaR-PG algorithm can be written as ([]))Ja(TT))13 < < (o. M
O Varl (ffx Clearly, variance reduction of a-factor linearly improves the second term. In particular, cancels out the denominator's a- a-factor attributed to tail sub-sampling, and brings the sample efficiency back to the level of the risk-neutral PG.
5

---

The Cross-entropy Soft-Risk Algorithm
Algorithm presents our Cross-entropy Soft-Risk algorithm (CeSoR), which uses PG approach to maximize Je (TT) ) in (2) CeSoR adds two components on top of CVaR-PG: soft-risk scheduling address the blindness to success analyzed in Section 3.1 and CE sampling to address the sample efficiency analyzed in Section 3.2
Soft-risk scheduler: We set the policy op- timizer (Line 15 in Algorithm [ to use a soft risk level of that gradually decreases from to a (Line 13 and Figure This is motivated by the blindness success analyzed in Section 3.1 by modifying the risk level a' > a, and specifically a' = 1 at the beginning of training, we guarantee that there cannot be a wider tail barrier 3 >> a'. Thus, CeSoR can feed the optimizer with trajectories whose returns 93 < R S %h are higher than any con- stant tail; and since the fed returns are not constant, they do eliminate the gradi- ent. In this sense, CeSoR looks beyond local optimization-platees
Algorithm 1:
CeSoR
Input: risk level a; context distribution Dæ: original context parameter do; training steps M; trajectories sampled per batch N, where y fraction of them is from the original Deoi smoothed CE quantile 3; risk-level scheduling factor
Initialize: policy No - LUN], N₂ + [(1 - N
+- dn.
for m M do
// Sample contexts
Sample (Co No Door (Co.) LN2 Do
C+ (Co.1..., Co,N., Co.,,..., Co.N.)
Wo,s 1, Vi (l....,Nol No}
Dag(Co.) Wp.s Do(Co.)) Vi E (1,....,NN) N.}
to prevent the blindness to success.
W + (Wal..... No,N., W Wo,N.) // Sample trajectories
The scheduling defined in Line 13 and Figure 2 heuristic. As demonstrated in Section 5 once we understand the limi- tation of blindness to success, this sim- ple heuristic is sufficient bypass the blindness. An adaptive a' scheduling that maximizes blindness prevention probabil- ity would require tighter concentration in- equalities [Boucheron et al.) 2013). and is left for future work.
10
(TC.. (TC.. f- run pain__pssddssTT... C*)
// Update CE sampler
11
q f max(Ia
(( (R((T...))) qa ((H((c.))))))
12
f argmaxy EisNW; 1s(
// PG step (e.g., Eq. 6p
13
a' t max(a, 1 111-1-1 (1-a) a-a).ma mm/mp-pp M))
o' + ( ((B(TC..)
14
15
+ CVaR_ PG (Irc..h (T. w, g¹)
2005 is general approach event sampling and optimization, which we use to sample high-risk contexts and trajectories. First, we review the standard CEM in terms adjusted to our setting and notations (for a more general presentation, see Algorithm in the appendix). Then, we discuss the limitations of the standard CEM in the RL settings, and present our dynamic, regularized version of the CEM.
Cross Entropy Method (CEM): The CEM de Boer et al.
we wish to align the agent's ' experience with the worst-case returns by sampling contexts whose corresponding likely to be below qa (R) That is, we wish to sample context-traj teatexxtrrajectory pairs from P ăv.a of (4). To that end, the CEM searches for a value of & for which pa is similar to Pae More precisely, it looks for ø that minimizes the KL-divergence (i.e., cross-entropy) between the two:
Motivated by the sample efficiency analysis of Section 3.2
jejectorr-retunne
o² E argmin DKL (XL(Pt)) (P 20.a argmax [E [a [n(r) (It mo) log D (C)]
(C,7)) (C, (C,)))
(5)
argmax [E (CC,)) [n(r) (M/ log Do (C)),
p (C.r) (a,(C) is the IS weight
where P5o (C (T) (Section 2). and w w(C,))
(C,) Dz(C)
corresponding the sample distribution (C,T) P 0 The optimization problem in Equation (5) often reduces to simple closed- form calculation: if D& is Gaussian. for example, o" reduces to the weighted expectation and variance of (C) R(()) I qa cc.-.gg with the IS weights T),
may produce noisy results when estimated from data ((C,, T.) ) unless N > a1, since only aN trajectory-samppee satisfy R(T) I qa and are used in the estimation. To address this,
Equation 5

---

PG early
c
GCVaR early
C
CeSoR / early
R
C
PG / late
GCVaR / late
C
CeSoR / late
01
0
pn training iteration
R
Figure 2: The soft-risk scheduling (Al- gorithm [ Line 13). The linear phase a' a prevents the blindness to suc- cess (Section(3.)) while the CEM still preserves risk aversion. The final con- stant phase a' provides station- ary objective and allows CeSoR to con- verge (Appendix
An illustration of training batches. Each point repre- episode with return R. and context C. Points of the same color correspond to "similar" agent actions that induce similar pol- icy gradients. Mean-PG averages over the whole batch and learns the blue strategy. C'aRR PG considers the left part (low returns) and learns the orange strategy. CeSoR over-samples the upper part (high-risk contexts), and only later decreases a' to explicitly focus on low returns, thus learning the purple strategy. The illustrated episodes are analogous to the strategies in Figures Id]4
Figure 3:
the CEM reaches the a-tail gradually over iterations. Every iteration, it samples a batch of contexts {C from the current distribution Da. and then solves Equation (5) with respect to a higher quantile qa More specifically, denote by de the estimated c-quantile of (R(T)),,rrPP' then, we set q max (H)) with hyperparameter > a (often 3 0.2). Since the data is drawn from p this guarantees at least BNN samples per update step. The quantile 46 corresponds to the o-tail of the original context-distribttion, and can be viewed as a stopping condition: once 1:00 > Tz- many of our samples are already in the tail, and / is no longer needed to smooth the update of Φ.
Dynamic-targer CEM: The standard CEM assumes to search for the tail of a constant distribution. In our setting, however, we look for the tail of the distribution of the returns R(T), where C, ~ Prt depend on Ty and thus are non-stationary throughout the training. The non-stationarity poses several challenges for the CEM. First, the stopping condition 4% varies with xo and has to be re-estimated every iteration" [T Second, the high-risk contexts (which correspond to the lowest returns) may vary as the agent evolves; and if the CEM learns to only sample strict subset of the context space, then it may miss such changes in the high-risk contexts.
We address both issues using reference samples: every iteration, we sample two batches of contexts (Co.) from the current context distribution Ds and {Co The reference contexts provide an important regularization: they guarantee continual exposure the whole context space, in case that the high-risk contexts vary. In addition, the reference samples were empirically found stabilize the estimation of 4% (Line 11 in Algorithm 1.
N. from the original distribution D
Consider the two batches of context- trajectory pairs, and denote the estimated return quantile qa = We can estimate the CVaR policy gradient, using the notation V1 s i No + N₂ if iis No
No (,) da
Co.s C. Co.NN.
+ +N by
by
N + sisss No
N.+N.
T
VoJa(TO)= = a(No N
Σ
1R(T)Sa (R(T.) (a) V log (o(
(6)
=1
==
where w, 1 for sis No and w. Do (C.)) (C.) for N. + +1 No + N..
Note that if the policy learning scale is slower than that of o, the target context distribution PT is effectively stationary in the d-optimization problem. In that case, according to de Mello and Rubinstein 2003). the CEM will converge to the KL-divergence minimizer d' of 5).
da.o
FFor the sake of coherent notations, we presented the CEM with the quantile objective q.. (R In fact, the standard CEM is usually defined with constant numeric objective go E K rather than quantile; hence, as shown in Algorithm in the appendix, the standard CEM does not require any quantile estimation at all.
7

---

Sample efficiency in practice: Proposition guarantees an o a -increase in sample efficiency when using an accurate quantile estimate d. 9, (o) and sampling exactly from pTp "a The latter condition is equivalent to the CE-sampler reaching its objective ( de.c || [xx))) = 0. In practice, p Φn.a can only be approximated, and the sample efficiency is increased - but by a smaller factor than a= Appendix D.3 demonstrates the increased sample size exploited by CeSoR in our experiments.
If q. + qa R m.), the quantile estimation enror may theoretically lead to unbounded IS weights (see Appendix B). Practically, we address this by clipping the weights (as mentioned in Section D., and by constraining the family of permitted distributions {Dol to have a constant support independently of Φ. A side-effect is function approximation error of the family {Dø la. as Dø P (r) cannot replicate the tail distribution Po (C,T) T) to achieve the full a -increase in sample efficiency.
Another limitation in the expressiveness of PTT (C,T)= ( (T) occurs when the context C only controls part of the environment randomness in (T). As an extreme example in the Guarded Maze, after Te already learns to avoid the short path, the context (guard cost) does not affect the outcome at all anymore. Indeed, Figure [0a in the appendix shows that high guard costs are sampled in the beginning; then, once the short path is avoided, the sampler gradually falls back to the original context distribution. Note that in this example, the invariance to C' began after the learning was essentially done, hence the CEM did play its part effectively.
Finally, note that the soft risk creates an intentional bias in the gradient estimate (to overcome the blindness to success). As result, in the first phase of training (a' >> a), only a few trajectories are overlooked every iteration. As a' approaches a, the number of overlooked trajectories increases, and so is the importance of over-sampling the tail. In the final steady- state phase (a' a), the sample inefficiency is most severe, the soft risk produces no further biases, and the CEM helps CeSoR to reduce the high variance in the policy gradient estimation.
The harmony between the soft risk and the CEM: Soft risk has the inherent side effect of reducing the risk aversion. In the Guarded Maze, for example, demonstrated in Section [. soft risk alone leads to learning the short path (instead of the risk-averse long path). Fortunately, the CEM reduces this side effect. In that sense, the two mechanisms complement each other: a' > a allows the optimizer to learn policies with high returns, while the CE sampler still preserves the risk aversion - as illustrated in Figure This connection stands in addition to the independent motivations of the two mechanisms, as discussed above.
Baseline optimizer: CeSoR can be implemented on top of any CVaR-PG method baseline (Line 15). We use the standard GCVaR (Tamar et al. 2015b]. which guarantees asymptotic conver- gence under certain regularity conditions. Appendix C shows that these guarantees hold for CeSoR as well, when implemented on top of GCVaR. Other CVaR-PG baselines can also be used, such as the TRPO-based algorithm of RRajeswaran et al. (017). However, such methods often include heuristics that introduce additional gradient estimation bias (to reduce variance), and thus do not necessarily guarantee the same thcoretical convergence.
5 Experiments
We conduct experiments in 3 different domains. We implement CeSoR on top of a standard CVaR- method, which is also used as risk-averse baseline for comparison. Specifically, we use the standard GCVaR baseline [Tamar et al., 2015b), which guarantees convenient convergence properties (see Appendix C and is simple to implement and analyze. We also use the standard policy gradient (PG) as a risk-nncural bascline. We stress that the comparison to PG is only intended to present the CVaR tradeoff, while each method legitimately optimizes its own objective. Appendix H also compares CeSoR to rest-ne and risk-averse Distributional RL algorithms.
In all the experiments, all agents are trained using Adam [Diederik P. Kingma, 2014 with learning rate selected manually per benchmark and N 400 episodes per training step. Every 10 steps we run validation episodes, and we choose the final policy according to the best validation score (best mean for PG, best CVaR for GCVaR and CeSoR). ). For CeSoR, unless specified otherwise, v = 20% of the trajectories per batch are drawn from the original distribution Døg: 3 20% are used for the CE update; and the soft risk level reaches a after p = 80% of the training. As mentioned in Section 4 for numerical stability, we also clip the IS weights (Algorithm I Line 9 to the range [1/5,5]
8

---

Every policy is modeled as neural network with tanh activation on its middle layers and sof softmar operator on its output, with temperature 1 in training (i.e., network outputs are actions probabilities). and O in validation and test (i.e., the max output is the selected action). We use a middle layer with 32 neurons in Section 5.2
neurons in Section 5.3] and no middle layer (linear model) in Section 5.1
In each of the 3 domains, the experiments required a running time of a few hours on an Ubuntu machine with eight 19-10900X CPU cores. In addition these RL-related experiments, Appendix D presents dedicated experiments for the independent CE module.
5.1 The Guarded Maze
episodes batch [%)
GCVaR
episodes batch [%)
SoR
The Guarded Maze benchmark is defined in Section I For the experiments, we set a target risk level of a 0.05, and train each agent for n = 250 steps with the parameters described above. The CEM controls C' through e = (œ), dh2,,
Benchmark:
80
stay
00
stay
short
short
8
long
long
88
iteration
iteration
where 6o = (0.2, 32) as mentioned above, and updates Φ1, d2 using the weighted means of C₁ and C2, respectively. As an ablation test, we add two partial variants of our CeSoR: CeR (with CE, without a-scheduling) and SoR (with scheduling, without CE). See more details in Appendix E.1
episodes batch [%]
200
CeSoR
long long-path path episodes
fed to optimizer [%)
100
00
60
stay
GCVaR
short
SoR
40
long
CeSoR
20-
Results: Figure Ta summarizes the test scores, and
iteration
iteration
Figure Td illustrras sample episode. PG learned the short path, maximizing the average but at the cost of poor returns whenever charged by the guard. CeSoR, on the other hand, successfully learned to follow the CVaR-optimal long path. GCV,R, which also aimed to maximize the CVaR, failed to do so. As analyzed in Figure $ throughout GCVaR training, the agent takes the long path in up to 50% of the episodes per batch, but none of these episodes is ever included in the bottom a 5% that are fed to the optimizer. Thus, GCVaR is entirely blind to the successful episodes and fails to learn the corresponding strategy. In fact, in most training steps, all the worst episodes of GCVaR reach neither the guard nor the target, leading to a constant return of -32, a tail barrier, and a zero loss- vass-gradient.
%-episodes that did not reach the target (" ("stay"), "), or reached it through the short or the long path in the Guarded Maze. Bottom Right: %-long-patti among the trajectories fed to the optimizer. See more details in Figure 13
Figure 4: GCVaR, SoR, CeSoR:
CeR suffers from blindness to success just as GCVaR. SoR is exposed to the successful long- ang-path episodes thanks to soft risk scheduling; however, due to the reduced risk-aversion, it fails prefer the long path over the short one. Only CeSoR both observes the "good" strategy (thanks to soft risk scheduling) and judges under "bad" environment variations (thanks the CEM). Appendix E..2 presents a detailed analysis of the learning dynamics, the blindness to success and the learned policies. is important to notice that standard optimization tweaks cannot bring GCVaR learn the long path: a "warm-stard from a standard PG only encourages the short- short-path policy (as in SoR); and increased batch size N does not expose the optimizer to the long path (see Theorem
5.2 The Driving Game
Benchmark: The Driving Game is based on an inverse-RL benchmark used by Majumdar et al. [2017] and Singh et al. (2018). The agent's 's car has to follow the leader (an "erratic driver") for 30 seconds as closely as possible without colliding. Every 1.5 seconds (i.e., 20 times per episode), the leader chooses a random action (independently of the agent): drive straight, accelerate, decelerate, change lane, or brake hard (" d'emerrency brake"), with respective probabilities de = (0.35, 0.3, 0.248, 0.1, 0.002). We denote the sequence of leader actions by C (1...., 5).20
Every 0.5 seconds (60 times per episode), the agent observes its relative position and velocity to the leader, with delay of 0.7 seconds (representing reaction time), as well as its own acceleration and steering direction. The agent chooses one of the five actions: drive in the same steering direction, accelerate, decelerate, turn left, or turn right. Changing lane is not an atomic action and has to be learned using turns. The rewards express the requirements to stay behind the leader, on the road, on the same lane, not too far behind and without colliding. See the complete details in Appendix F.I

---

We set = 0.01, and train each agent for n 500 steps. To initiate learning, for each agent we begin with shorter training episodes of seconds and gradually increase their length. The CEM controls the leader's behavior through the probabilities Φb = {dx ) described above.
Results:
Figure Tb summarizes the test scores of the agents, where CeSoR presents reduction of 28% in the CVaR cost in comparison to the baselines. GCVaR com-
distance from leader
PG (mean=-18.77
GCVaR (mean=-34 3-4
-10
CeSoR (mean=-25 25.4)
pletely fails to learn reasonable policy - losing in terms of CVaR even the risk-neutra, PG. Figure shows shows that CeSoR learned an grquabl--intuitiy policy for risk averse driving: keeps safer distance from the leader, and uses the gas and the brake less frequently. This results in com-
-30
plete avoidance of the rare accidents occurring to PG, as demonstrated in Figure Te] In Appendix [ we also see that by ever-sampling turns and emergency brakes of the
quantile [%]
(a)
leader, the CEM manages to align the mean return of the
action frequency [%)
training samples with the 1%-CVaR of the environment, and significantly increases the data efficiency.
CeSoR
5.3 The Computational Resource Allocation Problem
Benchmark:
Computational resource allocation in serv-
ing systems, and in particular the tradeoff between source cost and serving latency, is an important challenge
brake
left
nothing action
right
gas
to both academia (Jiang al. [003 Tessler et al. 2022] and industry Barr 2018 8 Lunden 2022]. In popular ap- plications such E-commerce and news, latency is most critical at times of peak loads [Garces] 2019]. making CVaR natural metric for risk-averse optimization. In our benchmark, the agent allocates servers to handle user requests, managing the tradeoff between servers cost and time-to-service (TTS). Requests arrive randomly with a constant rate, up to rare events that cause sudden peak loads, whose frequency is controlled by the CE sampler. See Appendix G for more details.
(b)
Figure 5: Over all the time-steps in all the test episodes in the Driving Game, the distri- bution of (a) the distance between agent and the leader, (b) the agent actions. Evi- dently, CeSoR learns to keep more distance than the risk- PG, and has slightly less frequent use the gas and the brake.
Results: As shown in Figure Ic CeSoR significantly improves the CVaR return, and does not compromise the mean as much as GCVaR. As demonstrated Figure Tf CeSoR learned to allocate default of 5 servers and react to peak loads as needed, whereas GCVaR simply allocates 8 servers at all times. PG only allocates 4 servers by default, and thus its TTS is more sensitive to peak loads. Appendix describes the complete implementation and detailed results, discusses the poor parameterization of Da in this problem and shows the robustness of CeSoR to that parameterization.
Summary and Future Work
We introduced CeSoR, a novel method for risk-averse RL, focused on efficient sampling and soft risk. In variety of experimental domains, in comparison to risk-averse baseline, CeSoR demonstrated higher CVaR metric, better sample-efficiency, and elimination of blindness to success - where the latter two were also analyzed theoretically.
There are certain limitations to CeSoR. First, we assume to have at least partial control over the training conditions, through parametric family of distributions that needs to be selected. Second, CeSoR can be applied robustly on top of any CVaR-PG method, but is currently not applicable to non-PG methods. Since the limitations of CVaR-PG apply in other risk-averse methods as well (as we demonstrated for Distributional RL), future work may adjust CeSoR to such methods, as well other risk measures. Third, in terms of blindness success and estimation variance, CeSoR shows both theoretical and empirical improvement but is not proven optimal. Future work may look for optimal design of CEM risk scheduling. Considering the current results and the potential extensions, we believe CeSoR may open the door for more practical applications of risk-averse RL.
A Acknowledgements: This research was supported by the Isracl Science Foundation (grant 2199/20).
10

---

References
Jeff
Barr.
Predictive
scaling
for
EC2, powered by machine
learning, 2018.
URL
https: / /ww. amazon wwt.ccommolooa. hoon/bllgs//// aws/
new www-pppddiiiivssalllaaae
www.ree--aaaii-o----eeeeeee forng--o---eeee ec2 porel--ooeere-eee p
Marc G Bellemare, Will Dabney, and Rémi Munos. A distributional perspective reinforcement learning. International Conference on Machine Learning, pages 449-458. PMLR, 2017.
Cristian Bodnar, Adrian Li, Karol Hausman, Peter Pastor, and Mrinal Kalakrishnan. Quantile QT-Opt for risk-aware vision- based robotic grasping In Proceedings of Robotics: Science and Systems, Corvalis, Oregon, USA, July 2020. doi:
V. Borkar and S. Meyn. Risk- sensisee optimal control for Markov decision processes with monotone cost. Mathematics of Operations Research, 27(1):192-209, 2002.
Vivek Borkar and Rahul Jain. Risk-constrained Markov decision processes. IEEE Transactions on Automatic Control, 2014.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: nonasymptotic theory of independence. Oxford university press, 2013.
Y. Chow and M. Ghavamzadeh. Algorithms for CVaR optimization in MDPss In Proceedings of Advances in Neural Information Processing Systems 27, pages 3509-3517, 2014.
Y. Chow, A. Tamar, S. Mannor, and M. Pavone. Risk-sensitive and robust decision-makinn: CVaR optimization approach. In Advances in Neural Information Processing Systems, 2015.
Sebastian Curi, Kfir Y. Levy, Stefanie Jegelka, and Andreas Krause. Adaptive sampling for stochas- Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin,
tic risk-averse learning. Advanaess in Neural Information Processing Systems, volume 33, pages 1046-1047 Cur- ran Associates, Inc., 2020. URL httttp::/proceedingg: neurips cc/
pdf
Will Dabuey, Georg Ostrovski, David Silver, and Remi Munos. Implicit quantile networks for distributional reinforcement learning. In Proceedings of the 35th International Conference Machine Learning, pages 1096-1 1005, 2018a.
Will Dabney, Mark Rowland, Marc Bellemare, and Rémi Munos. Distributional reinforcement learning with quantile regression. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1), Apr. 201 8b. doi: 10. (6.99/aai.v322..11777... AAATaarticle/vie////ta
htL/https:///ot aaai. .rg. index php/
Frederic Dambreville. Cross-entropy method: convergence issues for extended implementation, 2006.
T. de Boer, Dirk P. Kroese, Shie Mannor, and Reuven Y. Rubinstein. A tutorial on the cross-entropy method. Annals of Operations Research, 13:119-6 67, 2005.
Tito Homem de Mello and Reuven Y. Rubinstein. Rare event estimation for static models via cross-entropy and importance sampling, 2003.
Jimmy Ba Diederik P. Kingma. Adam: A method for stochastic optimization, 2014. URL https
//arxiv. farxiv.org// abs/1412 6980
Yingjie Fei, Zhuoran Yang, Yudong Chen, and Zhaoran Wang. Exponential bellman equation and improved regret bounds for risk-sensitive reinforcement learning. Advances in Neural Information Processing Systems, 34, 2021.
Carla Prat Garces. The problem of peak loads in web applications and its solutions, 2019.
Javier Gareía and Fernando Fernández. comprehensive survey on safe reinforcement learning. Mach. Learn. Res., 16:1437-1480 2015.

---

Mathieu Godbout, Maxime Heuillet, Sharath Chandra, Rupali Bhati, and Audrey Durand. CARL: Conditional-value-at-- adversarial reinforcement learning. arXiv preprint arXiv:2109.09477 2021.
Ido Greenberg. Cross entropy method with non-stationary score function. https://pypi.ors project/cross- eattsss-tttoopymmtoooollol/ 2022.
Assaf Hallak, Dotan Di Castro, and Shie Mannor. Contextual markov decision processes. arXiv 2015.
preprint
Takuya Hiraoka, Takahisa Imagawa, Tatsuya Mori, Takashi Onishi, and Yoshimasa Tsuruoka. Learn- ing robust options by conditional value at risk optimization. NeurIPS, 05 2019.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. In The collected works of Wassily Hoeffding, pages 409-426. Springer, 1994.
L. Jeff Hong and Guangwu Liu. Simulating sensitivities of conditional value at risk. Management Science, 55(2):281-22 -233, 2009. ISSN 00251909, 15265501. URL http://www. jstor org/ Stable/4053911
Audrey Huang, Liu Leqi, Zachary C. Lipton, and Kamyar Azizzadenesheli. On the convergence and optimality of policy gradient for markov coherent risk, 2021a. / 2103. 02827
Audrey Huang, Liu Leqi, Zachary C. Lipton, and Kamyar Azizzadenesheli. On the convergence and optimality of policy gradient for markov coherent risk, 2021b. URL https://aaxxx...rrrg//////////// 2210300283 02827
Kevin Huang, Sahin Lale, Ugo Rosolia, Yuanyuan Shi, and Anima Anandkumar. CEM-GD: Cross- entropy method with gradient descent planner for model-based reinforcement learning, 2021c
Jing Jiang. Jie Lu, Guangquan Zhang, and Guodong Long. Optimal cloud resource auto-scaling for web applications. 2013 13th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing, pages 58-65. IEEE, 2013.
Ramtin Keramati, Christoph Dann, Alex Tamkin, and Emma Brunskill. Being optimistic to be conservative: Quickly learning a CVaR policy. Proceedings of the AAAI Conference on Artificial Intelligence, 34:4436 44433 04 2020.
Leslie Kish. Survey Sampling, New York: John Wiley and Sons, Inc., 1965.
Tom Leinster. Effective sample size, 2014.
Ingrid Lunden. Intel confirms acquisition of Al-based workload optimization startup granulate, reportedly for up $650M, 2022.
Anirudha Majumdar, Sumeet Singh, Ajay Mandlekar, and Marco Pavone. Risk-sensitive inverse reinforcement learning via coherent risk models. Robotics: Science and Systems, 07 2017. doi: 10.15607/RSS.200 201..0.
Shie Mannor, Reuven Rubinstein, and Yohai Gat. The cross entropy method for fast policy search. Proceedings, Twentieth International Conference on Machine Learning. 2, 07 2003.
Cosmin Paduraru, Daniel J. Mankowitz, Gabriel Dulac-Amold, Jerry Li, Nir Levine, Sven Gowal, and Todd Hester. Challenges of real-world reinforcement learning: Definitions, benchmarks and analysis. Machine Learning Journal, 2021.
Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforce- ment learning. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML'17, page 2817-2826. JMLR.org, 2017.
L.A. Prashanth and M. Ghavamzadeh. Actor-critic algorithms for risk-sensitive MDPs. In Proceedings of Advances in Neural Information Processing Systems 26, pages 252-260, 2013.
12

---

L.A. Prashanth and M. Ghavamzadeh. and average reward MDPs, Machine Learning Journal, 105(3):377-41,,200 2016.
actor-critic algorithms for discounted
Wei Qiu, Xinrun Wang, Runsheng Yu, Xu He, R. Wang, Bo An, Svetlana Obraztsova, and Zinovi Rabinovich. RMIX: Learning risk-sensitive policies for cooperative reinforcement learning agents. ArXiv, abs/2102.08 10,9, 2021.
Antonin Raffin, Ashley Hill, Adam Gleave, Anssi Kanervisto, Maximilian Ernestus, and Noah Dormann. Stable-baselines:: Reliable reinforcement learning implementations. Journal of Machine Learning Research, 22(268):1-8, 2021. URL http::/jmlm org/ http//ppppa/////////// 1364. html
Aravind Rajeswaran, Sarvjeet Ghotra, Balaraman Ravindran, and Sergey Levine. Epopt: Learning robust neural network policies using model ensembles. ICLR, 2017.
Makoto Sato, Hajime Kimura, and Syumpei Kobayashi. TD algorithm for the variance of return and mean-variance reinforcement learning. Transactions of The Japanese Society for Artificial Intelligence, 16:353-362, 2001.
Sumeet Singh, Jonathan Lacotte, Anirudha Majumdar, and Marco Pavone. Risk-sensitive inverse reinforcement learning via semi- and non- non-parametric methods. The International Journal of Robotics Research, 37, 04 2018. doi: 10.11777077836991722011.
Aviv Tamar, Yinlam Chow, Mohammad Ghavamzadeh, and Shie Mannor. Policy gradient for coherent risk measures. NIPS, 2015a.
Aviv Tamar, Yonatan Glassner, and Shie Mannor. Optimizing the CVaR via sampling. AAAI'S,, page 2993-2999 2015b.
Yichuan Tang, Jian Zhang, and Ruslan Salakhutdinov. Worst cases policy gradients. In CoRL,, 2019.
Chen Tessler, Yuval Shpigelman, Gal Dalal, Amit Mandelbaum, Doron Haritan Kazakov, Benjamin Fuhrer, Gal Chechik, and Shie Mannor. Reinforcement learning for datacenter congestion control. SIGMETRICS Perform. Eval. Rev., 49(2) jan 2022. ISSN 0163-5999. doi: 10. 10.1145/3512798 3512815. URL lattps://doo org/ 10. 1144/1111/32998 3512815
J. R. R. Tolkien. The Lord of the Rings: The Fellowship of the Ring. George Allen and Unwin, 1954.
Nithia Vijayan and L. A. Prashanth. Likelihood ratio-based policy gradient methods for distorted risk measures: non-asymptotic analysis. ArXiv, abs/2107.044/ 04422,, 2021.
Edoardo Vittori, Michele Trapletti, and Marcello Restelli. Option hedging with risk averse reinforce-
ment learning. In Proceedings of the First ACM International Conference on Al in Finance, ICAIF '20, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450375849. doi: 10. (0.1453333455534225553
httLttt/p////oi org/ 10.
.4225322
T. Xie, B. Liu, Y. Xu, M. Ghavamzadeh, Y. Chow, D. Lyu, and D. Yoon. A block coordinate ascent algorithm for mean-variance optimization. In Proceedings of Advances Neural Information Processing Systems 232, pages 1073-1083, 2018
Pan Xu, Felicia Gao, and Quanquan Gu. An improved convergence analysis of stochastic variance- reduced policy gradient. In Uncertainty in Artificial Intelligence, pages 541-551. PMLR, 2020.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See the summary (Section 6).
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Risk sensitive RL is an abstract task and is not specifically associated with any negative- impact applications.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full assumptions of all theoretical results? [Yes] For each result, Section 3 either states the assumptions directly or refers to Appendices
(b) Did you include complete proofs of all theoretical results? [Yes] See Section 3 with references to Appendices C
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] A repository of code presents Jupyter notebooks that reproduce the experimental results.
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] General details in the beginning of Section and specific details per experiment in Sections 5.1 5.3
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes] In Figures 16 20a we provide not only the average return but the full distribution, which implicitly includes the information of error bars.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] In the beginning of Section 5
4. If you using existing assets (e.g., code, data, models) curating/releasing
assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material URL? [Yes]
An anonymized repository of our code is linked from the abstract.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "zX3nR_qchmP", "reviewer": "Reviewer_YQ45", "summary": "The authors study risk-averse reinforcement learning with the specific problem of how to keep risk-averse while using the collected samples efficiently. To this end, a soft risk-level scheduling mechanism is proposed where all samples are used at the initial stage, and it gradually shifts to high-risk (lower return quantile) samples. Additionally, a cross entropy method (CEM) is used to sample risky trajectories among soft risk samples. The proposed method is evaluated on three benchmarks to show its effectiveness.", "questions": "1. Some risk may caused by an insufficient exploration of the environment. What is the performance if using more advanced RL method, e.g. SAC instead of policy gradient?\n2. How to understand the relationship of CEM and soft risk-level scheduling in Algorithm 1? It seems they are independent.\n\nUpdate after the rebuttal.\nIt is clear now about the contributions and the relationship between CEM and soft risk-level scheduling.", "limitations": "No.", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nThe risk-averse property plays an essential role in reinforcement learning (RL), especially for real-world problems. Therefore, the research topic of this paper is interesting and important for the RL community. The proposed mechanisms for improving risk sample usage are effective on the evaluated benchmarks. The authors also give a theoretical analysis of the ignorance of high-return samples, which leads to a local optimum.\n\n**Weaknesses**\n\nThe writing need to be polished carefully. Although the paper is well-motivated, the methodology is hard to follow. Specifically, it is hard to understand how soft risk-level scheduling works together with CEM since the optimization in Algorithm 1 line 11:12 is independent of policy learning line 13:15. Additionally, a lot of details of the methodology, e.g. CEM are introduced in Problem Formulation sections, which further prevent the understanding. For the novelty, it seems unclear. The main contributions seem to be a heuristic risk quantile hyper-parameter scheduling and a sampling-based previous CEM.\n\n\nMinor:\n\n1. Symbol 1_{R(tau)<q_alpha} is undefined in Eq. 3. It seems to be the indicator function.\n2. Grammar error: Are —> is in line 133.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "KB8iNx48_xu", "reviewer": "Reviewer_WUYT", "summary": "The authors provide different contributions, all related to the CVaR policy gradient method:\n1) They analyze the phoenomenon named \"blindness to success\", which affects the CVaR gradient optimization.\n2) They propose soft risk scheduling as a heuristic way of circumventing the problem.\n3) They extend the CE method for their particular setting, obtaining the CeSor algorithm, which consists in applying the two enhancements on top of the original GCVaR algorithm.\n4) They analyse the theoretical advantages in employing the CE method in the exact case, showing that it allows to reduce the policy gradient variance, thus, to reduce the sample complexity of a variance reduced PG algorithm.\n5) They compare the performance of the proposed method with the original version on some simple domains, moreover, they provide an ablation study in order to analyse the contribution of the different components of the algorithm.\n", "questions": "- Can the authors please discuss how sensitive the approach is to the hyper-parameter $\\beta$?\n- In particular, is the choice of $\\beta$ important to guarantee convergence to the optimal solution? \n- If the approach is sensitive to this hyper-parameter, how should it be chosen?", "limitations": "As highlighted by the authors too, the main limitation is constituted by the necessity of having the possibility of conditioning sampling w.r.t. contexts. This requires to have a high-level control over the environments, an hypothes which can hold true in simulation, but which is usually more difficult to enforce in real-world environments.\n\nAnother limitation is constituted by the assumptions of Proposition 1, which are almost never satisfied in practical applications of the algorithm, as highlighted by the authors too.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strenghts\nThe has the following points of strength:\n- The empirical analysis shows the advantages of employing both the proposed enhancements, and an ablation study clarifies that applying just one of them alone is not sufficient to reach the optimal policy.\n- The problem of blindness to success is analysed in a formal and exhaustive way.\n- The theoretical contribution about CEM is sound and it allows to clearly highlight the advantages of employing this sampling strategy.\n\n# Weakesses\nThe article presents the following weaknesses:\n- The soft risk approach, while intuitive and justified from an empirical viewpoint is not analyzed from a theoretical perspective, thus, it can be considered just as an heuristic to avoid the problem.\n- The theoretical results provided for the CE method hold only in the exact case, i.e., when the quantile extimation has no error and the CE method allows to match exactly the desired distribution. \n- The role of the hyper-parameter $\\beta$ is to guarantee a minimun number of samples in the CE update. However, this can introduce a bias in the distribution found by CE. The sensitivity of the approach w.r.t. to this hyper-parameter is not discussed.\n\n## Minor\n- Arguably, from the point of view of exposition, the article may benefit from a gradual introduction of the two main innovations propose the application of CE method and the risk-scheduling, instead of directly introducing the whole algorithm.\n- Section 5.1 comment the performance of CeR, however, they are only showed in the appendix. \n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "CFwk8w96Ipj", "reviewer": "Reviewer_xSEv", "summary": "The paper studies policy gradient under the conditional value at risk (CVaR) objective. The proposed method contains two important components: (1) using CEM for the better sampling of data so as to obtain a better estimate of the value at risk; and (2) using soft-risk scheduling on alpha (the CVaR parameter) to address the blindness to success problem. \n", "questions": "- Figure 2 is a nice illustration. But could the authors provide how it is generated in detail? For example, how are R and C obtained for each method?\n- Is there any additional reasoning for choosing alpha' the way presented in L13?\n- This is just a small suggestion: For theorem 1, it might be more readable for the users to present it directly for B instead of negating the B. How should one interpret m_0? Does it depend on \\alpha itself?\n- For the experiments:\n  - Why is GCVaR chosen as the PG method? \n  - How big of a role does clipping play? Have the authors compared the performance of GCVaR without clipping with different methods?\n  - In the first experiment, the authors have done an ablation study and compared CESoR with SoR and CEM separately. What about the second and third experiments? How does  CESoR compare with SoR and CEM?\n", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n\nThe paper proposed interesting heuristics to address the problem that CVaR is hard to optimize (especially in the RL setting). Algorithm 1 seems to be generic to any CVaR policy gradient method, which is ideal. The experiments have demonstrated the efficacy of the proposed methods.\n\n\nWeakness: \n\nThe problem of estimating the VaR and the problem of zero gradients for optimizing CVaR is not new in the risk-sensitive learning field. For example: In \"Adaptive Sampling for Stochastic Risk-Averse Learning (Curi et al.)\", the authors have considered using adaptive sampling of the data to overcome these issues (both the estimation of VaR and the zero-gradient problem).  In \"On the Convergence and Optimality of Policy Gradient for Markov Coherent Risk (Huang et al.)\", the authors have showcased the zero-gradient problem of optimizing CVaR in a bandit setup (where the Markov CVaR is equivalent to CVaR). The proposed heuristics are interesting but it is unclear why certain design choices (e.g., the particular schedule of alpha') are made.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "AAMnsS1Jfcm", "reviewer": "Reviewer_QDcc", "summary": "- This paper studies the problem of optimizing CVaR-alpha of returns using the policy gradient method. \n- The paper identifies and tackles two deficits of existing PG approaches to CVaR optimization:\n1. the \"blindness to success\" phenomenon, which clips returns above the alpha-quantile of the return distribution and causes the corresponding gradients to be uninformative w.r.t. high-return scenarios -- the approach suggested by the authors is to start with a higher-alpha (e.g. 1) to allow PG to learn the high return scenarios, then gradually decrease the risk tolerance to the desired level as training progresses\n2. sample efficiency, which is addressed by a cross-entropy method that learns to weigh low-return experience more than high-return ones during training\n- Finally, the paper provides theoretical and empirical results on three domains that argue in favour of these two strategies ", "questions": "1. clearly, the authors assert some additional assumptions about the structure of the problem to allow the CE method to gravitate towards the high risk areas. in contrast, distributional RL does not make such assumptions, and it can reduce the model uncertainty through bootstraps (unlike PG which inherently has high variance). how does the proposed cross entropy approach differ from learning a distribution over return? what is the advantage and the drawback of making such assumptions compared to DRL? \n2. the cross entropy and \"alpha-annealing\" approaches seems to be largely orthogonal to one another. is there a stronger connection between them w.r.t. bias-variance trade-offs? \n3. in relation to the weakness point made above, does the existence of function approximation errors limit the effectiveness of the alpha reduction method?\n4. In sect. 4.2., variance reduction is connected to sample efficiency by showing that reducing variance reduces one term in the general error bound [Xu et al., 2020] . however, viewed in the same lens, doesn't annealing alpha play a contradictory role by increasing the bias of the CVaR estimate J_\\alpha, and hence increasing the first term in that bound? ", "limitations": "- limitations are briefly discussed in the conclusion of the paper, but it would be nice to discuss them in more details\n- while this work is theoretical/abstract in nature, there could be some societal impacts in areas where RL is starting to become more practical (e.g. financial trading, health-care) - the implications of this with regards to the modeling assumptions (e.g. contextual MDP) used in this work should probably be mentioned", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- the problems described pertaining to the optimization of CVaR seem important to address\n- the application of CE and its corr. Proposition 1 is novel to my understanding, and Theorem 1 is an important and interesting result that has standalone value for the general research area\n- the Algorithm choices are clearly motivated by and well connected to the theory  (Th. 1, Pr. 1, Lem. 2)\n\nWeaknesses:\n- a number of important algorithms discussed in the related work section are not compared against in the empirical evaluation: specifically, the paper by Keramati et al., 2020 appears to be similar in terms of the problem being tackled as well as their methodology\n- while I think the CE approach is interesting and appreciate the authors' theoretical insight and strong motivation for tackling the problem, my biggest concern is that it is largely unclear to me whether DRL and related approaches are already solving (or could readily solve) the same problem, and the distinction w.r.t. current work is a bit blurred (see question 1 below as well). I am willing to revise my score if additional experiments/discussion in the paper disprove this claim. \n- the experiments are fairly low dimensional and it is difficult to determine if the effects of functional approximation errors could indirectly solve one of the problems this paper is tackling, on more challenging domains.\n\nOrganization:\n- I think it would be helpful to the reader to provide a stylized example demonstrating empirically how CVaR optimization naively leads to the problems claimed in the intro. this might make it clear to the reader that the benefits seen in figure 1 do indeed arise from tackling the problems as claimed. \n- I would also suggest to consider moving the discussion of blindness of success before the algorithm presentation, and use it as principled explanation for why a larger alpha will be necessary. ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept