Provably Efficient Risk-Sensitive Reinforcement Learning: Iterated CVaR and Worst Path
Authors: Yihan Du
Siwei Wang
Longbo Huang
Venue: ICLR 2023 poster (2023)
Keywords: Risk-sensitive Reinforcement Learning (RL)
Iterated CVaR RL
Worst Path RL
RL theory

Abstract: In this paper, we study a novel episodic risk-sensitive Reinforcement Learning (RL) problem, named Iterated CVaR RL, which aims to maximize the tail of the reward-to-go at each step, and focuses on tightly controlling the risk of getting into catastrophic situations at each stage. This formulation is applicable to real-world tasks that demand strong risk avoidance throughout the decision process, such as autonomous driving, clinical treatment planning and robotics. We investigate two performance metrics under Iterated CVaR RL, i.e., Regret Minimization  and Best Policy Identification. For both metrics, we design efficient algorithms ICVaR-RM and ICVaR-BPI, respectively, and provide nearly matching upper and lower bounds with respect to the number of episodes $K$. We also investigate an interesting limiting case of Iterated CVaR RL, called Worst Path RL, where the objective becomes to maximize the minimum possible cumulative reward. For Worst Path RL, we propose an efficient algorithm with constant upper and lower bounds. Finally, the techniques we develop for bounding the change of CVaR due to the value function shift and decomposing the regret via a distorted visitation distribution are novel, and can find applications in other risk-sensitive online learning problems. 

Published as a conference paper at ICLR 2023
PROVABLY EFFICIENT RISK-SENSITIVE REINFORCE- MENT LEARNING: ITERATED CVAR AND WORST PATH
Yihan Du
Siwei Wang
Institute for Interdisciplinary Information Sciences Tsinghua University
Microsoft Research
Beijing, China
Beijing, China
s i we i wang@mi crosoft.
duyh18@man ilmails.. tsinghua. edu. on
Longbo Huang
Institute for Interdisciplinary Information Sciences Tsinghua University
Beijing, China
Longbohuang@tsinghhun edu. on
ABSTRACT
In this paper, we study novel episodic risk-sensitive Reinforcement Learning (RL) problem, named Iterated CVaR RI, which aims maximize the tail of the reward-to-go at each step, and focuses on tightly controlling the risk of getting into catastrophic situations at each stage. This formulation is applicable to real- world tasks that demand strong risk avoidance throughout the decision process, such as autonomous driving, clinical treatment planning and robotics. We investi- gate two performance metrics under Iterated CVaR RL, i.e., Regret Minimization and Best Policy Identification. For both metrics, we design efficient algorithms ICVaR-RM and ICVaR-BPI, respectively, and provide nearly matching upper and lower bounds with respect to the number of episodes K. We also investigate an interesting limiting case of Iterated CV&R RL, called Worst Path RL, where the objective becomes to maximize the minimum possible cumulative reward. For Worst Path RL, we propose an efficient algorithm with constant upper and lower bounds. Finally. our techniques for bounding the change of CVaR due to the value function shift and decomposing the regret via a distorted visitation distribution are novel, and can find applications in other risk-sensitive RL problems.
INTRODUCTION
Reinforcement Learning (RL) (Kaelbling et al., 1996; Szepesvári, 2010; Sutton & Barto, 2018) is classic online decision-making formulation, where an agent interacts with an unknown environment with the goal of maximizing the obtained reward. Despite the empirical success and theoretical progress of recent RL algorithms, e.g., (Szepesvári, 2010; Agrawal & Jia, 2017; Azar et al., 2017; Zanette & Brunskill, 2019), they focus mainly on the risk-neutral criterion, i.e., maximizing the ex- pected cumulative reward. and can fail to avoid rare but disastrous situations. As result, existing algorithms cannot be applied to tackle real-world risk-sensitive tasks, such as autonomous driv- ing (Wen al., 2020) and clinical treatment planning (Coronato et al., 2020), where policies that ensure low risk of getting into catastrophic situations at all decision stages are strongly preferred.
Motivated by the above facts, investigate Iterated CVaR RL, novel episodic RL formula- tion equipped with an important risk-sensitive criterion, i.e., Iterated Conditional Value-at-Risk (CVaR) (Hardy & Wirch, 2004). Here, CVaR (Artzner al., 1999) is a popular static (single-stage) risk measure which stands for the expected tail reward. Iterated CVaR is a dynamic (multi-stage) risk measure defined upon CVaR by backward iteration, and focuses on the worst portion of the reward-to-ge at each stage. In the Iterated CVaR RL problem, an agent interacts with an unknown
"Corresponding author.

---

Published as a conference paper at ICLR 2023
episodic Markov Decision Process (MDP) in order maximize the worst a-portion of the reward- to-go at each step, where a E (0, 1] is a given risk level. Under this model, we investigate two important performance metrics, i... Regret Minimization (RM), where the goal is to minimize the cumulative regret over all episodes, and Best Policy Identification (BPI) where the performance is measured by the number of episodes required for identifying an optimal policy.
Compared to existing CVaR MDP model, e.g., (Boda & Filar, 2006; Ott, 2010; Bäuerle & Ott, 2011; Chow et al., 2015), which aims to maximize the CVaR (i.e., the worst a-portion) of the total reward, our Iterated CVaR RL concerns the worst a-portion of the reward-to-go al each step, and prevents the agent from getting into catastrophic states more carefully. Intuitively, CVaR MDP takes more cumulative reward into account and prefers actions which have better performance in general, but can have larger probabilities of getting into catastrophic states. Thus, CVaR MDP is suitable for scenarios where bad situations lead to a higher cost instead of fatal damage, e.g., finance. In contrast, our Iterated CVaR RL prefers actions which have smaller probabilities of getting into catastrophic states. Hence, Iterated CVaR RL is suitable for safety-critical applications, where catastrophic states are unacceptable and need to be carefully avoided, e.g., clinical treatment planning (Wang et al., 2019) and unmanned helicopter control (Johnson & Kamnan, 2002). For example, consider the case where we fly an unmanned helicopter to complete some task. There is a small probability that, at each time during execution, the helicopter encounters a sensing control failure and does not take the scheduled action. To guarantee the safety of surrounding workers and the helicopter, we need to make sure that even if the failure occurs, the taken policy ensures that the helicopter does not crash and cause fatal damage (see Appendix C.2, C.3 for more detailed comparisons with existing risk-sensitive MDP models).
Iterated CVaR RL faces several unique challenges as follows. (i) The importance (contribution to regret) of state in Iterated CVaR RL is not proportional to its visitation probability. Specifically, there can be states which are critical (risky) but have small visitation probability. As a result, the regret for Iterated CVaR RI. cannot be decomposed into the estimation error at each step with respect to the visitation distribution, as in standard RI. analysis (Jaksch et al., 2010; Azar et al., 2017; 7anette & Brunskill, 2019). (ii) In Iterated CVaR RL, the calculation of estimation error involves bounding the change of CVaR when the true value function shifts to optimistic value function, which is very different from typically bounding the change of expected rewards as in existing RL analysis (Jaksch et al., 2010; Azar et al., 2017; Jin et al., 2018). Therefore, Iterated CVaR RL demands brand- new algorithm design and analytical techniques. To tackle the above challenges, we design two efficient algorithms ICVaR-RM and ICVaR-BPI for the RM and BPI metrics, respectively, equipped with delicate CVaR-adapted value iteration and exploration bonuses to allocate more attention on rare but potentially dangerous states. We also develop novel analytical techniques, for bounding the change of CVaR due to the value function shift and decomposing the regret via a distorted visitation distribution. Lower bounds for both metries are established to demonstrate the optimality of our algorithms with respect to the number of episodes K. Moreover, we present experiments to validate our theoretical results and show the performance superiority of our algorithm (see Appendix A).
We further study an interesting limiting case of Iterated CVaR RL when approaches 0, called Worst Path RI, where the goal becomes to maximize the minimum possible cumulative reward (optimize the worst path). This setting corresponds to the scenario where the decision maker is extremely risk- adverse and concerns the worst situation (c.g., in clinical treatment planning (Coronato et al., 2020), the worst case can be disastrous). We emphasize that Worst Path RL cannot be directly solved by taking a -> 0 in Iterated CVaR RL's results, as the results there have a dependency on 1 in both upper and lower bounds. To handle this limiting case, we design a simple yet efficient algorithm MaxWP, and obtain constant upper and lower regret bounds which are independent of K.
The contributions of this paper are summarized follows.
We propose a novel Iterated CVaR RL formulation, where an agent interacts with an unknown environment, with the objective of maximizing the worst a-percent tail of the reward-to-go at each step. This formulation enables one to tightly control risk throughout the decision process, and is most suitable for applications where such safety-at-all-time is critical.
We investigate two important metrics of Iterated CVaR RL, i.e., Regret Minimization (RM) and Best Policy Identification (BPI), and propose efficient algorithms ICVaR-RM
2

---

Published as a conference paper at ICLR 2023
and ICVaR-BPI. We establish nearly matching regret/sample complexity upper and lower bounds with respect to K. Moreover, we develop novel techniques to bound the change of CVaR due to the value function shift and decompose the regret via distorted visitation distribution, which can be applied to other risk-sensitive decision making problems.
We further investigate a limiting case of Iterated CVaR RL when a approaches O, called Worst Path RI., where the objective is to maximize the minimum possible cumulative ward. We develop a simple and efficient algorithm MaxiP, and provide constant regret upper and lower bounds (independent of K).
Due to space limit, we defer all proofs and experiments to Appendix.
2 RELATED WORK
Below we review the most related works, and defer a full literature review to Appendix B.
CVaR-based MDPs (Known Transition). Boda & Filar (2006); Ott (2010); Bäuerle & Ott (201 1); Chow et al. (2015) study the CVaR MDP where the objective is to minimize the CVaR of the total cost, and show that the optimal policy for CVaR MDP is history-dependent (see Appendix C.2 for a detailed comparison with CVaR MDP). Hardy & Wirch (2004) firstly define the Iterated CVaR measure, and Osogami (2012); Chu & Zhang (2014); Bäuerle & Glauner (2022) consider iterated coherent risk measures (including Iterated CVaR) in MDPs, and demonstrate the existence of Marko- vian optimal policies. The above works focus mainly on the planning side, i.e., proposing algorithms and eπror guarantees for MDPs with known transition, while our work develops RL algorithms (in- teracting with the environment) and regret/sample complexity results for unknown transition.
Risk-sensitive Reinforcement Learning (Unknown Transition). Tamar et al. (2015); Keramati al. (2020) study CVaR MDP with unknown transition and provide convergence analysis. Borkar & Jain (2014); Chow & Ghavamzadeh (2014); Chow et al. (2017) investigate RL with CVaR-based constraints. Heger (1994); Coraluppi & Mareus (1997; 1999) consider minimizing the worst-case cost in RL and design heuristic algorithms. Fei et al. (2020; 2021a;b) study risk- risk-sensitive RL with the exponential utility criterion, which takes all successor states into account with an exponential reweighting scheme. In contrast, our Iterated CVaR RL primarily concerns the worst a-portion successor states, and focuses on optimizing the performance under bad situations (see Appendix C.3 for detailed comparison).
PROBLEM FORMULATION
In this section, we present the problem formulations of Iterated CVaR RL and Worst Path RL. Conditional Value-at-Ree Riskk (CVaR). We first introduce two risk measures, i.e., Value-at-Risk (VaR) and Conditional Value-at-Risk (CVaR). Let X be random variable with cumulative distribution function F(x)= = Pr(X I z/.. Given a risk level a E (0, 1). the VaR at risk level a is the a-quantile of X, i.e. VaR VaR = ( 2 a). and the CVaR at risk level a defined as (Rockafellar et al., 2000):
1 [(x-)))++
CVaR (X) sup
where (x)+ == max(æ. 0}. If there is probability atom at VaR"(X), CVaR can also be written as (X) E[X] X < (X)] (Shapiro et al., 2021). Intuitively, CVaR" (X) is dis- torted expectation of X conditioning on its a-portion tail, which depicts the average value when bad situations happen. When a = 1, CVaR"(X) = [[[). and when a - 0, CVaR" (X) tends to min(X) (Chow et al., 2015).
Iterated CVaR RL. We consider an episodic Markov Decision Process (MDP) A, r). Here S is the state space, A is the action space, and H is the length of horizon in each episode. p the transition distribution, i.e. ((s'|s,00 a) gives the probability of transitioning to s' when starting from state s and taking action a deterministic reward for taking action a in state s. A policy π is defined as a collection of H functions, i.e., (mh S + A}bE[H), where [7] = {1, 2, 2..,.... H).
r S A + [0, 1] is reward function, and r(s, gives
3

---

Published as a conference paper at ICLR 2023
The episodic RL game is as follows. In each episode k. an agent chooses policy n², and starts from a fixed initial state $1, i.c. sf := $1, as assumed in many prior RL works (Fiechter, 1994; Kaufmann et al., 2021; Ménard et al., 2021). At each step h [H]. the agent observes the state s and takes an action ot (*))) After that, it receives reward r(s af) and transitions next state + according to the transition distribution p(-|s% a.). The episode ends after H steps and the agent enters the next episode.
In Iterated CVaR RL, for any risk level (0, 1] and policy म, we use value function V S + R and Q-value function 0% S x A + to denote the cumulative reward that can be obtained when the agent transitions to the worst a-portion states each step, starting from and (s, step h, respectively. For simplicity of notation, when the value of a is clear, we omit the superscript a and use the notations VØ and QT. Formally, Q7 and V, are recurrently defined in Eq. (i) below. Since S. A and H are finite and the maximization of (s) in Iterated CVaR RL satisfies the optimal substructure property, there exists an optimal policy x²' which gives the optimal value (s)
max, Vi (s) for all s E S and h E [H] (Chu & Zhang, 2014). Therefore, the Bellman equation and the Bellman optimality equation are given in Eqs. (i), below, respectively (Chu & Zhang, 2014).
(T. a) = - () + p0 (
( (s))
(s, a) = =r(s, a) + C s'-((-)) (Vh+1 (s'))
(=) = (7, Q7) (s))
V = max Q1 (s, aEA
(s) 0, Vs E,
ii)
(s) = 0, Vs S,
(ii)
where C (V h+44(()) (8)) denotes the CVaR value of random variable + (s') with s' p(-|s, a) risk level a. We also provide the expanded version of value function definitions for Iterated CVaR RL (Eqs. (i), (ii) in Appendix C.1.
We consider two performance metrics for Iterated CVaR RL, i.e., Regret Minimization (RM) and Best Policy Identification (BPI). In Iterated CVaR RL-RM, the agent aims to minimize the cumula- tive regret K episodes, defined as
K = Σ VV
R(K)
(1)
A=1
In Iterated CVaR RL-BPI, given a confidence parameter d E (0, 1] and an accuracy parameter e >> 0, the agent needs to use as few trajectories (episodes) as possible to identify an e-optimal policy f, with probability as least 1 - 8. That is, the performance of BPI is measured by the number of trajectories used, i.e., sample complexity.
which satisfies 1/$ (#1) 2 (s1)
Worst Path RL. Furthermore, we investigate an interesting limiting case of Iterated CVaR RL when a approaches 0, called Worst Path RL. In this case, the objective becomes maximizing the minimum possible reward (Heger, 1994). The Bellman (optimality) equations become
(7, = r(s,a) + min (V"+z(s')) (7,s, a) = r(s,a) + min s'mp(t)a.a)
(V (s'))
s'mpl: s.0)
(s) = (s, (s))
Vi(( (5) = max (s) aEA
(s) = 0, Vs E S,
(+)+(s) = O, Vs E S,
where min.--m( (V 1 (s')) denotes the minimum value of random variable V (s') with s' p(-|s,a) From Eq. (2), sees that
H
H Σ
(T(s,a) min
Σ (s., a.) = an a π (T)(s
min (S Jomm
(s) s, n Lt=h
(Se foum
Thus, QT(ss a) and (s) denote the minimum possible cumulative reward under policy т,, starting from (s. a) and at step h. respectively. The optimal policy .² maximizes the minimum possible cumulative reward (i.e., optimizes the worst path) for all starting states and steps. Formally, x² gives the optimal value (s) max, VA (s) for all S and h [H].
For Worst Path RL, in this paper we mainly consider the regret minimization setting, where the regret is defined the same Eq. (1). Note that this case cannot be directly solved by taking a: - in Iterated CVaR RL, as the results there have a dependency on 1. Thus, changing from CVaR(.) to min(-) in Worst Path RL requires a different algorithm design and analysis.
4

---

Published as a conference paper at ICLR 2023
Algorithm 1: ICVaR-RM
Input: 8, a. 8' == 5 I = log KHSA) V H+1 = 0 for any k > 0 and 8 E S
5
for k = =.=,,..... 1....... K do
for / H, 1,.... do
(V (5))) H
ne(s,a) H3, (ss,a))x))
(s) - Play the episode with policy n², and update nx++ (8, a) and g (d'ls,))),)
max.c. Q (s, a). (5) )= + argmax aEA (h (8, Vs E
The best policy identification setting of Worst Path RL, on the other hand, is very challenging. This is because we cannot establish confidence intervals under the min(-) operation, and it is difficult to determine when the estimated optimal policy is accurate enough and when the algorithm should stop. We will further investigate this setting in future work.
ITERATED CVAR RL WITH REGRET MINIMIZATION
In this section, we consider regret minimization (Iterated CVaR RL-RM). We propose an algorithm ICVaR-RM with CVaR-adapted exploration bonuses, and demonstrate its sample efficiency.
4.1 ALGORITHM ICVaR-RM AND REGRET UPPER BOUND
We propose value iteration- bbasd algorithm ICVaR-RM (Algorithm 1), which adopts Brown- type (Brown, 2007) (CVaR- addated) exploration bonuses and delicately pays more attention to rare but risky states. Specifically, in each episode k; ICVaR-RM computes the empirical CVaR for the
values of next states CVaR ('1sp((1s.a) C (V h++ (s')) and Brown-type exploration bonuses II E
ma(s,a) Here n² (s, a) is the number of times (s, a) was visited up to episode k. and (5'(ss, (s, is the em- pirical estimate of transition probability p(s'ls, a). Then, ICVaR-RM constructs optimistic Q-value function 0 (s, a), optimistic value function (s).. and a greedy policy n² with respect to Q (s, After calculating the value functions and policy, ICVaR-RM plays episode k with policy π² observes a trajectory, and updates (s, a) and gh+ (s' a). The calculation of CVaR (Line 3) can be im- plemented efficiently, and costs O log S) computation complexity (Shapiro et al., 2021).
We summarize the regret performance of ICVaR-RM as follows.
Theorem (Regret Upper Bound). With probability at least 1 1- 8, the regret of algorithm ICVaR-RA is bounded by
o min
HSVKHA
KHSA 8
log
min h,s: ( Wn, (s)
where (r. denotes the probability of visiting state s at step under policy m.
Remark The regret depends on the minimum between an MDP-intrinsic visitation factor (ming,A,s (s))0 War (s)) and Va"-T- When a is small, the first term dominates the bound, which stands for the minimum probability of visiting an available state under any feasible policy. Note that ming J.s: w. (e)>00 Wa, a takes the minimum over only the policies under which is reachable, and thus, this factor will never be zero. Indeed, this factor also exists in the lower bound (see Section 4.2). Thus, characterizes the essential problem hardness, i.c., when the agent is highly risk-adverse, her regret will be heavily influenced by exploring critical but hard-to-reach states.
When a is large, V instead dominates the bound. The intuition behind the factor र is that for any state-action pair, the ratio of the visitation probability conditioning on transitioning to bad successor states the original visitation probability can be upper bounded by - This ratio is critical and will appear in the regret bound (see Lemma for a formal statement).
In the special case when 1, our Iterated CVaR RL problem reduces the classic RL formu- lation, and our regret bound becomes Ö(HSVKH)))) KH)) which matches the result in existing classic
5

---

Published as a conference paper at ICLR 2023
RL work (Jaksch et al., 2010). This bound has a gap of VHS to the tfate-of-the-an regret bound for classic RL (Azar et al., 2017; Zanette & Brunskill, 2019). This is because our algorithm is mainly designed for general risk-sensitive cases (which require CVaR-adapted exploration bonuses), and does not use the Bernstein-tyri exploration bonuses (which only work for classic expectation max- imization criterion). Such phenomenon also appears in existing risk-sensitive RI works (Fei al., 2020; 2021a). Designing an algorithm which achieves an optimal regret simultaneously for both risk-sensitive cases and classic expectation maximization case is still an open problem, which we leave for future work. To validate our theoretical analysis, we also conduct experiments to exhibit the influences of parameters a, H. S, A and K on the regret of ICVaR-RM practice, and the empirical results well match our theoretical bound (see Appendix A).
Challenges and Novelty in Regret Analysis. The analysis of Iterated CVaR RI. faces several chal- lenges. (i) First of all, in Iterated CVaR RI, the contribution of a state to the regret is not proportional to its visitation probability as in standard RL. analysis (Jaksch et al., 2010; Azar et al., 2017; Zanette & Brunskill, 2019). Instead, the regret is influenced more by risky but hard-to-reach states. Thus, the regret cannot be decomposed into estimation error with respect to visitation distribution. (ii) Second, unlike existing RL analysis (Jaksch et al., 2010; Azar et al., 2017; Jin et al., 2018) which typically calculates the change of expected rewards between optimistic and true value functions, in Iterated CVaR RL, we need to instead analyze the change of CVaR when the true value function shifts to an optimistic value function. To tackle these challenges, we develop a new analytical technique to bound the change of CVaR due to the value function shift via conditional transition probabilities, which can be applied to other CVaR- -bsed RL problems. Furthermore, we establish a novel regret decomposition for Iterated CVaR RL via a distorted (conditional) visitation distribution, and quan- tify the deviation between this distorted visitation distribution and the original visitation distribution.
Below we present a proof sketch for Theorem 1 (see Appendix D.1 for a complete proof).
Proof sketch of Theorem 1. First, we introduce key inequality (Eq. (3)) to bound the change of CVaR when the true value function shifts to an optimistic one. To this end, let ga. (-Is, a) E R denote the conditional transition probability conditioning on transitioning to the worst a-portion successor states s', i.e., with the lowest values V(s'). It satisfies that Ev'ss as go, V (s')s, a) (V*)== = CVaRg CVaRgrmp(-e... (V(s)).. Then, for any (s, a) and value functions V, V such that Vss)) 2 V(s') for any s E S, we have
CVaR2-p(1e.. (V()))
8a. (H)ss)) VV)
(3)
Eq. (3) implies that the deviation of CVaR between optimistic and true value functions can be bounded by their value deviation under the conditional transition probability, which resolves the aforementioned challenge (ii), and serves as the basis of our recurrent regret decomposition.
Now, since V is an optimistic estimate of Vgg, we decompose the regret in episode kt as
(2) H a
L nx (4)
VT V/T
+ CVaR
( (V))) - CVaR3 C
pp at) (V (s'))
CVaR
('mp(( (x)) - CVaRg
CVaR ( (VT (6')
(6)
L
4H
SL
+ va. (11s),a)) T(V v3r)
+
ma(st,aft a
H
HVI+AHVSI (s,a)- aVTu(ss,a)
Wkh
a,
(4)
1=1 (s.a)
CVaR, v=* Here Wih k. conditioning on transitioning to the worst a-portion successor states s' (i.e., with the lowest a-
(8, a) denotes the conditional probability of visiting (8, a) at step h of episode
vv** (s, a) is a distorted portion values (s')) at each step h' = L,..., h - 1. Intuitively, Wkh
visitation probability under the conditional transition probability ga.v= (.);,). Inequality (b) uses the concentration of CVaR and Eq. (3). Inequality (c) follows from recurrently applying steps (a)-
(s, a) is the visitation ovaR, v
(b) to unfold (-) V= (-) for h = 2,..., H, and the fact that kh
6

---

Published as a conference paper at ICLR 2023
probability under conditional transition probability 3a.v= (11,-). Eq. (4) decompases the regret into estimation error at all state-action pairs via the distorted (conditional) visitation distribution
aVaR,a,V* (s, a), which overcomes the aforementioned challenge (i).
Wkd kk
Summing Eq. (4) over all episodes & [K] and using the Cauchy Schwarz inequality, have
5HVSL
o, V
(s,a)
H
[[R(K)] <
Wsh
Wkh
o,
(s,
(x
(s,0)
(s.a)
5 VSL VKH
H
"kh
aVa
(s,
(a)(s,
1 (w 0}
a
WKh WEn(8,
(x(s,a)
(s.a)
W05HVKHSL
H
wka(s, nx(s,a)
min
min [.,, (s,a)s)
(x, H-1
k=1h=1(s,a)
Here Wanh (s, a) denotes the probability of visiting (s,a) at step h of episode k, and w & (s, a) denotes the probability of visiting (s at step h under policy т. Equality (d) uses the facts
CVaR,o,V** (s)a) must as well. Inequality (e) is due to that E(s,a) a, a (s)
Win
and if the visitation probability (an(s,a)
the
ditional visitation probability Wkhh
that whh aVaR,a,V* (s, (s,a)/wan(s) can be bounded by both 1/ //miin,, (s.a() (s, and 1-1 Specifically, the bound 1/ miing,h,ss.a) a (s,0)=0 W7,4 follows from minz,h,(ssa): a (x.0)00 (s,n S Wan (s, a), and the bound 1/a" H-1 comes from the fact that
the conditional visitation probability WhAh CVaR,,,V (s, a) is at most 1/a" times the visitation prob- ability WkA (s, a). Having established the above, we can use a similar analysis as that in classic wenls,a) and then, D(s,)) (x.aa)
RL (Azar et al., 2017; Zanette & Brunskill, 2019) bound we can obtain Theorem 1.
4.2 REGRET LOWER BOUND
We now present regret lower bound demonstrate the optimality of algorithm ICVaR-RM. Theorem 2 (Regret Lower Bound). There exists an instance of Iterated CVaR RL-RM, where ming,h, (s))0 (x) > H-1 and the regret of any algorithm is at least
AK
Ω H
(5)
a mmiin, h,,s w. (8)20 Wa.h
In addition, there exists an instance of Iterated CVaR RL-RM, where H-1 h.s: h.ss: wx (s))S (s) and the regret of any algorithm is at least 22 a
mill
AAK
Remark 2. Theorem 2 demonstrates that when a is small, the factor min, h.s: was (s)>0 (s) Wa, (s) is
inevitable in general. This reveals the intrinsic hardness of Iterated CVaR RL, i.e., when the agent is highly sensitive to bad situations, she must suffer regret due to exploring risky but hard-to-reach states. This lower bound also validates that ICVaR-RM near-optimal with respect to K.
Lower Bound Analysis. Here we provide the proof idea of the first lower bound (Eq. (5)) in Theorem and defer the full proof to Appendix D.2. We construct an instance with a hard-to-reach bandit state (which has an optimal action and multiple sub-optimal actions), and show that this state critical for minimizing the regret, but difficult for any algorithm to learn. As shown Figure 1, we consider an MDP with actions, n regular states $1 $1...., .,..,,,,, 8n and three absorbing states 21, 22, F3, where
D.8
Reward 0.2
3
#
Reserd 1
H. The
Figure 1: Instance for the lower bound.
7

---

Published as a conference paper at ICLR 2023
Algorithm 2: MaxWP
Input: 6, 8 -. -= log( ) V (+) for any k 0 and 8
for k = -1,2.... ..... K do
for h = H, - 1,.... do
(s, a) + r(s, a) ( ( a() E A:
(s) - max.eA ( a). Th argmax (s, a). Vs S;
Play the episode with policy n², and update n (8, a) and f (5'1,, a);
reward function r(s, a) depends only on the states, i.e.,
$1...., Sn generate zero reward, and Z 22. 2a generate rewards 1, 0.8 and 0.2, respectively. Let be a parameter such that < a < μ < 3. Under actions, state 81 transitions to 82, Ii, 22, 43 with probabilities μr, 1 3/, fa. and μs, respectively, and state 8; (2 S i S with probabilities f and transitions to 22, 23 with probabilities 1 a a and a 7,, respectively. Under sub-optimal actions, 8n transitions to 22, D3 with probabilities 1 - a and a respectively.
1) transitions to 8j-1, fu, respectively. For the bandit state sn, under the optimal action, &n
In this MDP, under the Iterated CVaR criterion, the value function mainly depends the path 81 7 $2 + + 8n - /2/ I3, and especially on the action choice in the bandit state 8n- Thus, to distinguish the optimal action in 8n, any algorithm must suffer a regret dependent on the probability of visiting 8n. which is exactly the minimum visitation probability over all reachable states mi (+)x (x))(s). Note that in this instance, min (=)x())>0 Wx,A (5) p²=1, which does not depend on a and H. This demonstrates that there is an essential dependency on min (s)=0 Wx As (s) in the lower bound.
ITERATED CVAR RL WITH BEST POLICY IDENTIFICATION
In this section, we design an efficient algorithm ICVaR-BPI BPI, and establish sample complexity upper and lower bounds for Iterated CVaR RL with best policy identification (BPI).
5.1 ALGORITHM ICVaR-BRR BPI AND SAMPLE COMPLEXITY UPPER BOUND
Algorithm ICVaR-BPI introduces a novel distorted (conditional) empirical transition probability to construct estimation eπrоr, which effectively assigns more attention to bad situations and fits the main focus of the Iterated CVaR criterion. Due to space limit, we defer the pseudo-code and detailed description of ICVaR-BPI to Appendix E. Below present the sample complexity of ICVaR-BPI.
Theorem 3 (Sample Complexity Upper Bound). The number of trajectories used by algorithm ICVaR-BPI to return e-optimal policy with probability at least 1 - 8 is bounded by
1
S2 A
)
min
miny h w. ( Wr.h (8))
H
HSA where C² log (min mi,,, wa (s)20 W. (()) a sad
Similar to Theorem 1, min w.., (s) Wx (s))(s) and a 1| dominate the bound for a large a and small a, respectively. When = 1. the problem reduces to the classic RL formulation with best policy identification, and our sample complexity becomes Ō S" A). which recovers the result in z²
prior classic RL work (Dann et al., 2017). Similar to Theorem 1, this bound has gap of HS to the state-of-the-ard sample complexity for classic RL (Ménard et al., 2021). This gap is due to the fact that the result in (Ménard et al., 2021) is obtained using the Bernstein-type exploration bonuses, which are more fine- fine-graing grained for the classic RL problem but do not work for general risk-sensitive cases, because it cannot be used to quantify the estimation error of CVaR.
To validate the tightness of Theorem 3, we further provide sample complexity lower bounds H²A
Ω Za w, A ( (=s) log (t)) and 2 A log (1)) for different instances, which demonstrate that the factor min 1/ ming, we (s)>0 Wx,n 1/1 is indispensable gen- eral (see Appendix E.3 for a formal statement of lower bound).
8

---

Published as a conference paper at ICLR 2023
6 WORST PATH RL
In this section, we investigate an interesting limiting case of Iterated CVaR RL when a - 0, called Worst Path RL, in which case the agent aims maximize the minimum possible cumulative reward.
Worst Path RL has a unique feature that, the value function (Eq. (2)) concerns only the minimum value of successor states, which are independent of specific transition probabilities. Therefore, once we learn the connectivity among states, we can perform a planning to compute the optimal policy. Yet, this feature does not make the Worst Path RL problem trivial, because is still challenging to distinguish whether a successor state is hard to reach or does not exist. As result, careful scheme is needed to both explore undetected successor states and exploit observations to minimize regret.
6.1 ALGORITHM MaxWP AND REGRET UPPER BOUND
We design an algorithm MaxWP (Algorithm 2) based on a simple and efficient empirical Q-value function, which makes full use of the unique feature of Worst Path RL, and simultancously explores undetected successor states and exploits the current best action. Specifically, in episode k, MaxWP constructs empirical Q-value/value functions Q% (s,, a), V (s) using the estimated lowest value of next states, and then, takes greedy policy (s) with respect to (s, a) in this episode.
The intuition behind MaxWP is as follows. Since the Q-value function for Worst Path RL uses the min operator, if the Q-value function is not accurately estimated, it can only be over-estimated (not under-estimated). If evtresstimttion happens, MaxWP will be exploring an over-estimated action and urging its empirical Q-value to get back its true Q-value. Otherwise, if the Q-value function is already accurate, MaxWP just selects the optimal action. In other words, MaxWP combines the exploration of estr-estddated actions (which lead undetected successor states) and exploitation of current best actions. Below we provide the regret guarantee for algorithm MaxWP.
Theorem 4. With probability at least 1 -, 8, the regret of algorithm MaxWP is bounded by
o (E
H
SA
log
ming: (=())))0 Us (8, a) min, o Essppce(lsa)))) p(8 (8,
(s.0)ESxA
where Ux (8, a) denotes the probability (s, a) is visited at least once in an episode under policy и.
Remark The factor ming: v=(a,))00 Uz (s, a) stands for the minimum probability of visiting (s, a) at least once in an episode over all feasible policies, and min, Esupp(p((ee]] p(s'|s, |s, a) denotes the minimum transition probability over all successor states of (8, a). Note that this result cannot be implied by Theorem I, because the result for Iterated CVaR RL there depends on 1. and simply taking a + leads a vacuous bound.
Theorem 4 demonstrates that algorithm MaxWP enjoys constant regret with respect to K. This constant regret made possible by the unique feature of Worst Path RL that, under the worst path metric, once the agent determines the connectivity among states, she can accurately estimate the value function and find the optimal policy. Furthermore, determining the connectivity among states (with a given confidence) only requires a number of samples independent of K. MaxWP effectively utilizes this problem feature, and efficiently explores the connectivity among states.
To validate the optimality of our regret upper bound, we also provide a lower bound ((max (s) mine::z(s.0))0
p())) for Worst Path RL, which demonstrates the tightness of the factors min (s,)20 Uy a) and esmploosss))) p(s"|s,,0) a).
7 CONCLUSION
In this paper, we investigate a novel Iterated CVaR RL problem with the regret minimization and best policy identification metrics. We design two efficient algorithms ICVaR-RM and ICVaR-BPI, and provide nearly matching regret/sample complexity upper and lower bounds with respect to K. We also study an interesting limiting case called Worst Path RL, and propose simple and efficient algorithm MaxWP with rigorous regret guarantees. There several interesting directions for future work, e.g., further closing the gap between upper and lower bounds, and extending our model and results from the tabular setting to the function approximation framework.
9

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
The work Yihan Du and Longho Huang is supported by the Technology and Innovation Major Project of the Ministry of Science and Technology of China under Grant 2020AAA0108400 and 2020AAA0008403. the Tsinghua University Initiative Scientific Research Program, and Tsinghua Precision Medicine Foundation 10001020109. The work of Siwei Wang was supported in part by the National Natural Science Foundation of China Grant 62106122.
REFERENCES
Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: worst- case regret bounds. Advances in Neural Information Processing Systems, 30, 2017.
Philippe Artzner, Freddy Delbaen, Jean-Mare Eber, and David Heath. Coherent measures risk. Mathematical Finance, 93):203-- 1999.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The non-stochastic multi- armed bandit problem. SIAM Journal on Computing, 32(1))48-777 77, 2002.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In International Conference on Machine Learning, pp. 263-272. PMLR, 2017.
Nicole Bäuerle and Alexander Glauner. Markov decision processes with recursive risk measures. European Journal of Operational Research, 296()):953-966 2022.
Nicole Bäuerle and Jonathan Ott. Markov decision processes with werage-value-at-ie criteria. Muthematical Methods of Operations Research, 74(3):361-379, 2011.
Kang Boda and Jerzy A Filar. Time consistent dynamic risk measures. Mathematical Methods of Operations Research, 63(1):169-18) 186, 2006.
Vivek Borkar and Rahul Jain. Risk-constrained markov decision processes. IEEE Transactions on Automatic Control, 59())25774 2579, 2014.
Vivek Borkar. A sensitivity formula for risk-sensitive cost and the actor-critic algorithm. Systems & Control Letters, 44(5):339-346, 2001.
Vivek S Borkar. Q-learning for risk-sensitive control. Mathematics of Operations Research, 27(2): 294-311,0000
David B Brown. Large deviations bounds for estimating conditional value-at-risk. Operations Research Letters, (5(6):722-730, 2007.
Richard Cheng, Gábor Orosz, Richard Murray, and Joel W Burdick. End-to-end safe reinforce-
ment learning through barrier functions for safety-critic critical continuous control tasks. In Proceed-
ings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 3387-3395, 2019.
Yinlam Chow and Mohammad Ghavamzadeh. Algorithms for CVaR optimization in MDPs. In Advances in Neural Information Processing Systems, volume 27, 2014.
Yinlam Chow, Aviv Tamar, Shie Mannor, and Marco Pavone. Risk-sensitive and robust decision- making: a CVaR optimization approach. In Advances in Neural Information Processing Systems, volume 28, 2015.
Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone. Risk-constrained re- inforcement learning with percentile risk criteria. Journal of Machine Learning Research, 18(1): 6070-6120, 2017.
Shanyun Chu and Yi Zhang. Markov decision processes with iterated coherent risk measures. In- ternational Journal of Control, 87(11):228-2299) 2014.
Stefano P Coraluppi and Steven I Marcus. Mixed risk neutral/mmiiima control of markov decision processes. In Proceedings 3 It Conference Information Sciences and Systems. Citeseer, 1997.
10

---

Published as a conference paper at ICLR 2023
Stefano P Coraluppi and Steven Marcus. Risk-sensitive and minimax control of discrete-time, finite-state markov decision processes. Automatica, 35(2):301-309, 1999.
Antonio Coronato, Muddasar Naeem, Giuseppe De Pietro, and Giovanni Paragliola. Reinforcement learning for intelligent healthcare applications: A survey, Artificial Intelligence in Medicine, 109: 101964, 2020.
Christoph Dann and Emma Brunskill. Sample complexity of episodic learning. In Advances in Neural Information Processing Systems, pp. 2818 2818-2826, 2015.
reinforcement
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying PAC and regret: Uniform PAC bounds for episodic reinforcement learning. In Advances in Neural Information Processing Sys- tems, volume 30, 2017.
Dotan Di Castro, Aviv Tamar, and Shie Mannor. Policy gradients with variance related risk criteria. arXiv preprini arXiv: arXiv: 220.. 2012.
Mehdi Fatemi, Shikhar Sharma, Harm Van Seijen, and Samira Ebrahimi Kahou. Dead-ends and secure exploration in reinforcement learning. In International Conference Machine Learning, pp. 1873- 1881. PMLR, 2019.
Mehdi Fatemi, Taylor W Killian, Jayakumar Subramanian, and Marzyeh Ghassemi. Medical dead- ends and learning to identify high-risk states and treatments. Advances Neural Information Processing Systems, 34:4856-4870, 2021.
Yingjie Fei, Zhuoran Yang. Yudong Chen, Zhaoran Wang, and Qiaomin Xie. Risk-sensitive rein- forcement learning: Near-optimal risk-sample tradeoff in regret. In Advances in Neural Informa- lion Processing Systems, volume 33, pp. 12384-22395, 2020.
Yingjie Fei, Zhuoran Yang, Yudong Chen, and Zhaoran Wang. Exponential bellman equation and improved regret bounds for risk-sensitive reinforcement learning. In Advances in Neural Infor- mation Processing Systems, volume 34, 2021a.
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, 2021b.
Claude-Nicolas Fiechter. Efficient reinforcement learning, In Conference on Computational Learn ing Theory, pp. 88 97, 1994.
Javier Garcia and Fernando Fernández. A comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research, 16(1):1437-1480, 2015.
Mary Hardy and Julia L Wirch. The iterated CTE: dynamic risk measure. North American Actuarial Journal, 8(4):62-75, 2004.
William B Haskell and Rahul Jain. A convex analytic approach risk-aware markov decision processes. SIAM Journal on Control and Optimization, 53(3):1569-1598 2015.
Matthias Heger. Consideration of risk in reinforcement learning. In International Conference Machine Learning, pp. 105-111. Elsevier, 1994.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(4), 2010.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is Q-learning provably effi-
cient? In Advances Neural Information Processing Systems, volume 31, 2018.
Eric Johnson and Suresh Kannan. Adaptive flight control for an autonomous unmanned helicopter.
In AIAA Guidance, Navigation, and Control Conference and Exhibit, pp. 4439, 2002.
Leslie Pack Kaelbling, Michael Littman, and Andrew W Moore. Reinforcement learning: A
survey. Journal of Artificial Intelligence Research, 4:237-285, 1996.

---

Published as a conference paper at ICLR 2023
Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, and Michal Valko. Adaptive reward-free exploration. In Algorithmic Learning Theory, pp. 865- 891. PMLR, 2021.
Ramtin Keramati, Christoph Dann, Alex Tamkin, and Emma Brunskill. Being optimistic be conservative: Quickly learning a cvar policy. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 4436 4443, 2020.
Prashanth La and Mohammad Ghavamzadeh. Actor-critic algorithms for risk-sensitive MDPs. Ad- vances in Neural Information Processing Systems, 26, 2013.
Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Emilie Kaufmann, Edouard Leurent, and Michal Valko. Fast active learning for pure exploration reinforcement learning. In Inter- national Conference Machine Learning, pp. 7599-7608. PMLR, 2021.
Takayuki Osogami. Iterated risk measures for risk-sensitive markov decision processes with dis- counted cost. arXiv preprint arXiv: 2012.
Jonathan Theodor Ott. A markov decision model for surveillance application and risk-sensitive markov decision processes. 2010.
Tyrrell Rockafellar, Stanislav Uryasev, et al. Optimization of conditional value-at-rish Journal of Risk, 2:21 1221-42,222 2000.
Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczynski. Lectures on stochastic program- ming: modeling and theory. SIAM, 2021.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018
Csaba Szepesvári. Algorithms for reinforcement learning. Synthesis Lectures Artificial Intelli- gence and Machine Learning, 4(1):1-103, 2010.
Aviv Tamar, Yonatan Glassner, and Shie Mannor. Optimizing the CVaR via sampling. In AAAI Conference on Artificial Intelligence, 2015.
Philip Thomas and Erik Learned- Concentration inequalities for conditional value-at-risk. In International Conference on Machine Learning, pp. 6225-6233 PMLR, 2019.
Chunhao Wang, Xiaofeng Zhu, Julian C Hong. and Dandan Zheng, Artificial intelligence in radio- therapy treatment planning: present and future. Technology in cancer research & treatment, 18: 1533033818873922, 2019.
Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger. In- equalities for the él deviation of the empirical distribution. Newlett-Packarc Labs, Tech. Rep, 2003.
Lu Wen, Jingliang Duan, Shengbo Eben Li, Shaobing Xu, and Huei Peng. Safe reinforcement learning for autonomous vehicles through parallel constrained policy optimization. In IEEE In- ternational Conference on Intelligent Transportation Systems, pp. 1-7. IEEE, 2020.
Andrea Zanette and Emma Brunskill. Tighter problem- regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference Machine Learning, pp. 7304-7312 PMLR, 2019.
12

---

Published as a conference paper at ICLR 2023
APPENDIX
A EXPERIMENTS
In this section, we provide experimental results to evaluate the empirical performance of our al- gorithm ICVaR-RM, and compare it the state-of-the- ahe algorithms EULER (Zanette & Brunskill, 2019) and RSVI2 (Fei et al., 2021a) for classic RL and ien-stenittvve RL, respectively.
In our experiments, consider an Hl-layered MDP with S 3(11 - 1) + 1 states and actions. There is single state (initial state) in layer 1. For any 2 S h < H, there are three states 8a(h-2)++1 2 and 83(h-2)+3 3 in layer h, which induce rewards 1, 0 and 0.4, respectively. The agent starts from so layer 1, and for each step h E [H]. she takes an action from {a......0, and then transitions to one of three states in the next layer. For any a E (ai..... G.-11 action leads to 83(h-1)+1 and 83(h-1)+2 with probabilities 0.5 and 0.5, respectively. Action 0, leads to 8a(h-1)42 and 83(h-1)+3 with probabilities 0.001 and 0.999, respectively.
We set a E {0.05, 0.1, 0.15), , E {0.5, 0.005, 0.00005). H E (2 10), S E (7, 13,13,25) A E (3,5, 12] and K [0, 10000] (the change of K can be seen from the X-axis in Figure 2). We take = 0.05, 5 = 0.005. H = 5, S = 13. A = 5 and K = 10000 as the basic setting, and change parameters a, 8, H. S. A and K to see how they affect the empirical performance of algorithm ICVaR-RM. For each algorithm, we perform 20 independent runs and report the average regret across runs with 95% confidence intervals.
As shown in Figure 2, our algorithm ICVaR-RI RM achieves significantly lower regret than the other algorithms EULER (Zanette & Brunskill, 2019) and RSVI2 (Fei et al., 2021a), which demonstrates that ICVaR-RM can effectively control the risk under the Iterated CVaR criterion and shows perfor- mance superiority over the baselines. Moreover, the influences of parameters a, 8, H, S, A and K on the regret of algorithm ICVaR-RM match our theoretical bounds. Specifically, as 5 increases, the regret of ICVaR-RM decreases. As H, S or A increases, the regret of ICVaR-RU! RM increases as well. As the number of episodes K increases, the regret of ICVaR-RM increases at sublinear rate.
B RELATED WORK
Below we present a complete review of related works.
CVaR-based MDPs (Known Transition). Boda & Filar (2006); Ott (2010); Bäuerle & Ott (201 1); Haskell & Jain (2015); Chow et al. (2015) study the CVaR MDP problem where the objective is to minimize the CVaR of the total cost with known transition, and demonstrate that the optimal policy for CVaR MDP is history-dependent (not Markovian) and is inefficient to exactly compute. Hardy & Wirch (2004) firstly define the Iterated CVaR measure, and prove that it is coherent dynamic risk measure, and applicable equity-linked insurance. Osogami (2012); Chu & Zhang (2014); Bäuerle & Glauner (2022) investigate iterated coherent risk measures (including Iterated CVaR) in MDPs, and prove the existence of Markovian optimal policies for these MDPs. The above works focus mainly on designing planning algorithms and derive planning error guarantees for known transition, while our work develops RL algorithms (interacting with the environment online) and provides regret and sample complexity guarantees for unknown transition.
Risk-Sensitive Reinforcement Learning (Unknown Transition). Heger (1994); Coraluppi & Mar- cus (1997; 1999) consider minimizing the worst-case cost in RL, and present dynamic programming of value functions and heuristic algorithms without theoretical analysis. Borkar (2001: 2002) study risk-sensitive RL with the exponential utility measure, and design algorithms based on actor criticc learning and Q-learning, respectively. Di Castro et al. (2012); La Ghavamzadeh (2013) inves- tigate variance-related risk measures, and devise policy gradient and actor-critic-based algorithms with convergence analysis. Tamar et al. (2015) consider maximizing the CVaR of the total reward, and propose a sampling-basee estimator for the CVaR gradient and a stochastic gradient decent al- gorithm to optimize CVaR. Keramati et al. (2020) also investigate optimizing the CVaR of the total reward, and design an algorithm based tor. Borkar Jain (2014); Chow & Ghavamzadeh (2014); Chow et al. (2017) study how to minimize the expected total cost with -VaR-based constraints, and develop policy gradient, actor-critic and
optimistic version of the distributional Bellman opera-
13

---

Published as a conference paper at ICLR 2023
BULzn
14:00
SULER
EULER BSSK2
Cumuritie Regant
899-2
50:00
C.mulatrv
280
200
1000
Eptaddis
Epscods
Esoodas
0.05
(b) 0.1
(c) 0.15
Dlsk
14000
Orm.ariee Begiet
12000
Degred
9:00
6000
680
Eplonden
1608
2000
Epiicdes
3040
200
1800
of Eptuddex
1909
(d) 0.00005
(e) 5 = 0.005
(1) = 0.5
31300
360
14:00
10:00
090
Cum
Camu
700
Numbeer Epioodes K
Humbee Epiendes
The Number Epoodes K
(g) H7
(h) HT 5
Hf 10
780
DULER
EULER
Carru Mative
300
180
3008
100
1800
408
2080
M03
(i) S==
(k) S = 13
(1) S 25
1480
Clac
ECNP-RN
Oum.arneee Rogiet
1200
8:00
0900
1800
Eplundes
230
1606
2000
4710 CMC
Epiizdes
2000
201 1900 Bi0
1400
(m) A = 3
(n) A = 5
(0) A = 12
Figure Experimental results for Iterated CVaR RL.
stochastic approximation-style algorithms. The above works mainly give convergence analysis, and do not provide finite-time regret and sample complexity guarantees as our work.
To our best knowledge, there are only few risk-sensitive RL works which provide finite-time regret analysis (Fei et al., 2020; 2021a:b). Fei et al. (2020) consider risk-sensitive RL with the exponen- tial utility criterion, and propose algorithms based on logaritmmiceeppoentia transformation and lquares updates. Fei et al. (2021a) further improve the regret bound (Fei et al., 2020) by
14

---

Published as a conference paper at ICLR 2023
developing exponential Bellmen equation and Bellman backup analytical procedure. Fei al. (2021b) extend the model and results in (Fei et al., 2020; 2021a) from the tabular setting to the func- tion approximation framework. Our work is very different from the above works (Fei et al., 2020; 2021a;b) in formulation, algorithms and results. The above works (Fei et al., 2020; 202 1a:b) use the exponential utility criterion characterize the risk and take all successor states into account in deci- sion making. They design algorithms based on exponential Bellmen equations and doubly decaying exploration bonuses. contrast, we interpret the risk by the Iterated CVaR criterion, which pri- marily concerns the worst a e-ppotiion successor states. We develop algorithms using EVaR-adapted exploration bonuses.
The works we discuss above fall in the literature of RL with risk-sensitive criteria. There are also other RI. works which focus on state-wise safety. Cheng et al. (2019) utilize control barrier functions (CBFs) to ensure the agent within set of safe sets and guide the learning by constraining explorable polices. Fatemi et (2019; 2021) define the notion of dead-end states (which lead to suboptimal terminal state with probability in finite steps) and aim avoid getting into dead-end states. The formulations and algorithms in these works greatly differ from ours, and they do not provide finite- time regret and sample complexity analysis & Fernández, 2015) for detailed categorization and discussion on safe RL.
We refer interested readers the survey (Garcia
C MORE DISCUSSION ON ITERATED CVAR RL
In this section, we first present the expanded value function definitions for Iterated CVaR RL. Then, we compare Iterated CVaR RL with existing risk-sensitive MDP models, including CVaR MDP (Boda & Filar, 2006; Ott, 2010; Bäuerle & Ott, 2011; Chow et al., 2015) and the exponential utility-based RL (Fei et al., 2020; 2021a).
C.I VALUE FUNCTION DEFINITIONS FOR ITERATED CVAR RL
The value function definition for Iterated CVaR RL, i.c., Eq. (i) in Section 3, can be expanded
()(,,a)= a() + CVRR
((+h+1,
- +VaR ba
V/ = r(s, (s)) + CVaR C (1,7(())))) ( ((5144):442((4H)
CVaR
CVaR
Similarly, the optimal value function definition, e.g., Eq. (ii) in Section 3, can be expanded as
(s, = max r(s.a) + CVaR s (ppl (((hh)1: Th+1
+ CVaR
C..RR
mmx)=xx>> (()) CVaRa S (( (8
+ CVaRo ski papp-1an 1 (1 1)) (.. C...VV S n 19sH mn(r(s,, un(r(sH,T(ssu))) (((ss)))) (6)
15

---

Published as a conference paper at ICLR 2023
$1
(determnnisticlll)
d2 (deteminiitticlly)
(0.05)
(0.95)
(0.01)
(0.99)
Ss
(0.95)
(0.01)
(0.01)
(0.05)
(0.05)
(0.95)
(0.99)
(0.99)
$8
S9
$10
$11
S14
$15
Cost:
0.4
0.4
Death
Get much better
Cured
Death
Get better
Cured
Risk level 0.05
CVaR MDP:
QoVaR (s, 4,)
0.0025
0.05-0.0025
0.05
0.05
QeVaR (5,, a.)
0.0001
0.05-0.00
0.5 0.501
0.05
0.05
Itorated CVaR RL (ours):
@ (8 a.)
0.05
0.06
1)]1
0.05
0.05
Q (5 a2)
0.5) +
0.01
0.5
0.05-0011
0)
0.05
0.05
0.05
0.05
0.05
0.05
Figure 3: Illustrating example for the comparison between CVaR MDP and Iterated CVaR RL.
From the above value function definitions, we can see that, Iterated CVaR RL aims to maximize the worst a-portion tail of the reward-to-ge at each step, i.e., taking the CVaR operator on the reward- to-go at each step. Intuitively, Iterated CVaR RL wants to optimize the performance even when bad situations happen at each decision stage.
C.2 COMPARISON WITH CVAR MDP
The objective of CVaR MDP, e.g., (Boda & Filar, 2006; Ott, 2010; Bäuerle & Ott, 2011; Chow et al., 2015), to maximize the worst a-portion of the total reward, which is formally defined as
max CVaRe (AA (an p-p.
Σ r(sh, an)
Compared to our Iterated CVaR RL (Eq. (6) and Eq. (ii) in Section 3) which concerns bad situations each step, CVaR MDP takes more cumulative reward into account and prefers actions which have better performance in general, but can have larger probabilities of getting into catastrophic states. Thus, CVaR MDP is suitable for scenarios where bad situations lead to a higher cost but not fatal damage, e.g., finance. In contrast, Iterated CVaR RL prefers actions which have smaller probabilities of getting into catastrophic states. Hence, Iterated CVaR RL most suitable for safety- critical applications, where catastrophic states are unacceptable and need to be carefully avoid, e.g.. clinical treatment planning.
We emphasize that Iterated CVaR is not equivalent to simply taking the worst " -portion of the total reward. In fact, the good (1 " ) -portion of the total reward also contributes to Iterated CVaR. This is because Iterated CVaR accounts bad situations for all states (both good and bad states) in its iterated computation, instead of just considering bad situations upon bad states.
Below provide example of clinical treatment planning illustrate the difference between Iterated CVaR and CVaR MDP. Here we interpret the objective as cost minimization for ease of understanding, and set the risk level 0.05.
16

---

Published as a conference paper at ICLR 2023
Consider 4-layered binary tree-structured MDP shown in Figure 3. The state sets in layers 2, 3 and 4 are {s {82, S3.. {$1..... $7] and {sy...., $13). respectively. There are two actions 41 42 in each state, and d1, dg have the same transition distribution in all states except the initial state 81- Thus, a policy is to decide whether to choose 01 or 02 in state $1, which leads to different subsequent costs.
The agent starts from the initial state i in layer 1. If the agent takes action 01 she will transition to state 52 deterministically, and goes into the left sub-tree. On the other hand, if the agent takes action 42 in state 81, she will transition to state 83 deterninistically. and enters the right sub-tree.
If the agent goes into the left sub-tree (state 82) in layer 2, she will transition to 84 and 85 in layer 3 with probabilities 0.05 and 0.95, respectively. Then, if she starts from state 81 in layer 3, she will transition to sg and s9 in layer with probabilities 0.05 and 0.95, respectively. Otherwise, if she starts from state 85 in layer 3, she will transition to $10 and $11 in layer 4 with probabilities 0.05 and 0.95, respectively.
On the other hand, if the agent goes into the right sub-tree (state sy) in layer 2, she will transition to 8g and 87 in layer with probabilities 0.01 and 0.99, respectively. Then, if she starts from state sg in layer 3, she will transition to and 813 in layer 4 with probabilities 0.01 and 0.99, respectively. Otherwise, if she starts from state 87 in layer 3, she will transition $14 and 815 in layer 4 with probabilities 0.01 and 0.99, respectively.
The costs are state-dependent, and only the states in layer produce non-zero costs. To be concrete, we use the clinical trial example and the costs represent the patient status. Specifically, in layer 4, ág and $12 give costs 1, which denote death. $13 and $14 produce costs 0.5, which means the patient is getting better. 8y and $10 induce costs 0.4, which denote that the patient gets much better. $11 and 815 produce costs O, which stand for that the patient is fully cured.
Under the CVaR criterion, we have that
0.0025
0.05 0.0025
0.44 0.43,
0.05
0.05
and
0.0001
0.05 - 0.0001
0.5 = 0.501.
0.05
0.05
Thus, CVaR MDP will choose action ai (and goes into the left sub-tree), since an leads to better medium states 8g and 810. which give a lower cost 0.4 than the cost 0.5 produced by the right sub-tree.
On the other hand, under the Iterated CVaR criterion, we have that
Q ICVaR. (31, (s1,
0.05
Q ICVaR. (84.-)
0.05
/0.05
QIVVR, (sCV.R.
0.05
/0.05
1) = 1,
0.05
0.05
0.05
0.05
0.05
and
QCCVRR. (81,
0.01
QICVaR.a (s6,
0.05
0.01
QiVVaR.o (ST.
0.05
0.05
0.01
(0.01
QiCVaR.
(812. + 0.05 - 0.01
iiCVaR. (813.
0.05
0.05
0.05
0.05
0.01
00.01
0.05 0.01
+
QCCVaR.or (314.
0.05
0.05
0.05
0.01
00.01
0.05 - 0.01
0.05 - 0.01
0.01
0.05
0.01
1
0.5
+
0.5 +
0)
0.05
0.05
0.05
0.05
0.05
0.05
-0.2.
Thus, Iterated CVaR RL will instead choose action a2 because 02 has a smaller probability of going into the bad left direction (which leads to the catastrophic state 812).
17

---

Published as a conference paper at ICLR 2023
The above example shows that, Iterated CVaR RL prefers actions with a smaller probability of get- ting into catastrophic states. In contrast, CVaR MDP favors actions with better average therapeutic effects, but has larger probability of causing death.
Note that the above example also demonstrates that Iterated CVaR not equivalent to the worst a -portioon of the total cost. To this, we have that (here consider a because there are transition steps):
0.0001
0.000125 0.0001
QCVaR, (51,
0.5 0.9,
0.000125
0.000125
and
QiCVaR, ($1, 02)
0.01
00.1
1+
0.05 - 0.01
0.5
+
0.05 0.01
0.001
0.5
0.05 0.01
0)
0.05
0.05
0.05
0.05
0.05
0.05
-..
In addition, one can see that, the good state which gives cost (i.e., 815) also contributes to QICVaR, ($1, a2), which shows that the good (1 a " >-pottion of the total cost also matters for Iterated CVaR.
C.3 COMPARISON WITH EXPONENTIAL UTILITY-BASED SENSITIVE RL
The Bellman optimality equation for risk-sensitive RL with the exponential utility criterion (Fei et al., 2020; 2021a) is defined as
1
(s, (s) + log (Brrp())(()) (exp( (B (+))))
which takes all successor states s into account, i.e., all successor states s' contribute to the compu- tation of the Q-value. Here B < 0 is risk sen-iiensttivity parameter.
In contrast, in Iterated CVaR RL, the Bellman optimality equation is defined as Q% (s, a) = r(s, a) + CVaRsr-((1s.n (V (
which focuses only the worst a-portion successor states s' (i.e., with the lowest a-portion values (s')), i.., only the worst a-portion successor states s' contribute to the computation of the Q-value.
Besides the formulation, our algorithm design and results are also very different from those in (Fei al., 2020; 2021a). The algorithms in (Fei al., 2020; 2021a) based on exponential Bellman equations and doubly decaying exploration bonuses, and their results depend on H)) con- trast, our algorithms
based on value iteration for Iterated CVaR with CVaR-adapted exploration bonuses, and our results depend on the minimum between an MDP-intrinsic visitation measure 1/ min wx (..))))) (s) and a deeeeeeeel factor "-!
D PROOFS FOR ITERATED CVAR RL WITH REGRET MINIMIZATION
In this section, we present the proofs of regret upper and lower bounds (Theorems I and 2) for Iterated CVaR RL-RM.
D.1 PROOFS REGRET UPPER BOUND
D.1.1 CONCENTRATION
For any k > 0, E [H] and (s, a) E S A, let muth (s, denote the number of times that (s,a) a) was visited at step h before episode kt and let ny ( a) = EH nigh (8, a) denote the number of times that (8, a) was visited before episode k.
18

---

Published as a conference paper at ICLR 2023
((gls.,) - p(g15,
(ggl.)))) -.1 0.1
()lls,))=00
v(s)
n* (=,l. R** (G(ss,))
v(s))
(s).)))
A (5. =01
(2(2.ba)) =011
g (,)0)))
g
(21b,0)=
p6a 0.3
(4b4,)==22
RM
(6 (5,0)
Se
s'
$1
$2
$3
S4
S1
$2
$3
S6
Original a-quantile line
Shifted a-quantile line
0.5 {53} Sune-r {54} Sright
Steft {s:) Stine- {S2} Smidate
Figure 4: Illustrating example for Lemma 2. For each s' E {si, 82, 83, 84), the height of the bar denotes the value Vss') (fixed), and the width the bar denotes the transition probability p(s'|s, (ss"ss,a) or (s'ls, [f'ss,a) a). The colored part of the bars denotes the worst a-portion successor states (i.e., with the lowest a-portion values V(s)), )). In this example, a 0.5.
Lemma (Concentration for V*). holds that
log (KSSA) 6'
Pr CVaR
8 -pt (1ma)) (V)(s')) (Iaa))
CVaRy an) (a) (V((())) S
(8,
Ak E [K], vh E [H] ((s.a) A 21-28'
Proof of Lemma 1. Using Brown's inequality (Brown, 2007) (Theorem 2 in (Thomas & Learned- Miller, 2019)) and union bound over (s, a) S and ng(s,a) a) E [Klf], we can obtain this lemma.
For any risk level E (0, 1]. function V - R and (s',,, S x S A, ga.V (s'Is, a) is the conditional transition probability from (s, a) to s', conditioning on transitioning to the worst a-portion successor states s' (i.e., with the lowest a-portion values (s')). Let ya.V (s'|s, a) denote how large the transition probability of successor state s belongs to the worst a-portion, which satisfies that (x')((" ga.V (s')s,a) a) and Eves ao.V p (s'[s,a) a. addition, for any risk level (0, 1], function S IK and
A, CVaR (vt.a (V())) Eves (s')s, (de'ss)) V(s))
Σ 'eSS
ga. (s'ss,)s)))
Lemma 2 (Concentration for any V). It holds that
2H
KHSA 2S log
CVaR
(1 (V())) - CVaR (V(lls
<
a
nx(s, a)
VV 10,H,, Vk E [K], V(s,a) E 21 28'.
Proof of Lemma 2. order (from the left to the right). Add a virtual line at the a-quantile, denoted by a-quantile line. Fix the value function V(-), and the transition probability changes from p(-Is, to (-1s,, a).
As shown in Figure 4, sort all successor states s' S by V(s') in ascending
Without loss of generality, below we consider the case where as the transition probability changes from pf a) 6* (-1s,a), the a-quantile line shifts from left to right (the analysis of the contrary
19

---

Published as a conference paper at ICLR 2023
case can also be obtained by interchanging p(- a) and n² (-|s, a)). We use original ox-quantile line and shifted a-quantile line to denote the q--uuntile line before and after the shift, respectively.
We divide the successor states s' S into five subsets follows. Let Steft and Sright denote the sets of states which are always on the left and right sides of the original and shifted a a-quantile lines, respectively. Let Smiddle denote the set of states which are in the middle of the original and shifted a-quantile lines. Let Stine-! and Stine-r denote the states which lie on the original and shifted a-quantile lines, respectively.
For any 8' E &teftt, we have that n (6'18, (818,,)) a) = p(s''s, a) and jittav (6'18, (
For any s' E Eright, we have V (s']s, a) = V (s'1s, =
For any 5' E Smiddler we have that yaa (s'(s, u) 0 and f.a. (8 (5118, = ( (5
For state Stine-l, we have that WooV (Stime-i = p(stine-1880)) - (Exesiess 1(88'1,,0 + M8tiie--1880 a) a) and j.haaVV (Stinerts,, = (Stine-(00,))) a).
For state Sline-r: have that naa (Stinerls a) 0 and jihaa (stinerrl) Exesi, (s) EdESmaaai 1² (5'(s,a) -6 (8inee)1s..)
Then, we obtain
Σ
[ikaaV (8118,a)
S'ES
Σ S'ESteft
1a (5000010,))
E
(s)1s,,))
d'ESrighe
( (6'18, + |itia, (Stine-)l8,,) a) p.a.v (s)5me-1(s,a))
8' S'ESmiddie
+ / | (stinerlss, - ( (stinerlss.a) (s)
Σ ())( p(8'|s,0)|+
E
(*(1(,,))
E'Es
s'ESmiddia
+ / (stsmere(ssa) p8)
Σ d'ESiet
p(s'(s, a) + p( p(stim--lss ss
+ a- Σ (*(((ssa))
Σ
ps((s(ss -p" (stinerlsss))
d'ESiots
s'ESmsaato
S Σ ())( p(8'1s,
Σ
(5((,,,))
e'Si
E'midddie
+ (stimeel)ss) D(Stieerls,a)) +
Σ
p(s')s,a) + p(sume-rls,
S'ESiere
+ a Σ (551s,,a)
Σ
p5(5(1s,a) 50t (stso-r1sss)
D'ES
N' d'ESmiaste
Σ (8'1,,))))) p(8')s,a)|+
(s'1s,)))
e'ESuatt
8' VESmsddle
+ 1 (Siine-l(s,)) ps5tme-rls,aa)
Σ
p(s'(s, + p(sism-rlss, - a
s'EStefe
+ a Σ (5((s,,a))
E
(s((sss, -5 (s a)
d'ESiots
S'ESmidale
20

---

Published as a conference paper at ICLR 2023
E (d')),)))) - p(6'(s,))) 10 (stime-1sss a) pl (1,me-115,a))
d'ESteft
Σ p(5lls,a)
E
(5'1,, a) + p(stin--18s 18,0) 1 (Stine-118; a)
s' E'Eiff
d'ESiese
Σ StEftett
()) -p(6'ss, 1 (stime-tlss a) pl (1inn--18s,)))
Σ [p(5'18,0) 50 (s'1s, a)) + |p(stmm-r1ss a) - (81
s' E'EStajt
$ -
- p(s'|p
p(s)|s,0)|
S'ES
where (a) due to Edess p(5'(s, a) + p(stinerlsss)) - -a 2 0 by the definition of state Stine-l.
Thus, we have
CVaR (le))))))))) (V CVaR -pp (
S (s'(s,a) V(s') Eves aav (8') VV')
a Eves (j n (6'(8,a) a)) V(s')
a
Eves Tiessltton (s!(s,a) (stss vaa (s'|s,a) H
a Eves (s'1s,) (((")ss,))pp((ssss_)) H
Using Eq. (55) in (Zanette & Brunskill, 2019) (originated from (Weissman et al., 2003)), we have that with probability at least 28', for any [K] and (s, a) E A.
25 2og
KHSA
Σ (s's, p(s')s, S
8'
(9)
n& ( a)
Plugging Eq. (9) into Eq. (8), we obtain that with probability at least 1 28', for any & E [K], (8, E x A and function V S [0, H].
2H 25 2Slog 6'
KHSA
(1
(V(s') CVaR S ao (V(''))
mx(s,a) a)
For any k > 0, h E [H] and a) E S step h of episode k. Then, it holds that for any > 0, E [H] and (s, a, E A. Wkn (8, a) E [0. and (s, WaA (a,(s,, a) 1.
x A, let wks (s, denote the probability of visiting (s, a)
Lemma 3 (Concentration of Visitation). It holds that
Pr (s,
1
Σ
Σ
uw)(s,a)= H log
HSA 8'
Ak O, ((s,a) E A 21 21-8.
2
M=11=1
Proof of Lemma 3. Applying Lemma F.4 in (Dann et al., 2017), we have that for any fixed h E [H]
HSA
O, v(s,a) ES A 21 8'
Pr
RRRk (s, a)
wwn a) log
Vk
8
H
21

---

Published as a conference paper at ICLR 2023
By union bound over h [H], we have
1
HSA
Pr nx (s. 2 2
wwn(s,a) H log
2 8'.
8'
To sum up, we define several concentration events which will be used in the following proof.
H log KHSA
&
CVaR snptt (V
CVaR " (Va = V nx(s,a)
Ak E [K], vh [H], v(s,a)
8 = CVaR ( (V(+)) CVaR ~p (V('))
2H
2S log (s,
KHSA 8'
8
: + -
Ak E [K], (s
--1
HSA
& m)(s,a) 2
wwn(s,a) - H log
wk > 0, v(s,a) v(s,a)) ES
8'
k=1k=1
Lemma 4. Letting 8' S. it holds that
Pr 2 6.
Proof of Lemma 4. This lemma can be obtained by combining Lemmas 1-3.
D.1.2 OPTIMISM, VISITATION AND CVAR GAP
Recall that L = log (KHSA)
Lemma (Optimism). Suppose that event holds. Then, for any is E [K]] [H] and e S. we have
(x) 2 Vs)
Proof of Lemma 5. We prove this lemma by induction.
First, for any & [K], s S, it holds that V#+1(5) (s) (s) 0.
Then, any E [K], h E [H] and (s, E S x Qf) = H, (), 2 (7,ss a) trivially holds, and otherwise,
H
(8) =s) + CVaRg CV (1) ((')) +
nu (s
H
I
2r(s,a) + CVaR (1 (Vi
+
nu ())
2r(s, + CVaR (op (V)))(s'))
(s,
where (a) uses the induction hypothesis and (b) comes from Lemma 1.
Thus, have
(s) (1 2 (()) (s),
22

---

Published as a conference paper at ICLR 2023
which concludes the proof.
Following (Zanette & Brunskill, 2019), for any episode k 0, we define the set of acttonaction pairs which have sufficient visitations in expectation as follows.
Ck (s.0) E S A:
HSA 8'
wwn(s,a) 2 Hlo
H }
(10)
Lemma (Sufficient Visitation). Suppose that event & holds. Then, for any and (s. E Cu.
H
( 0)
wwn(s,a).
W=1h=1
Proof of Lemma 6. This proof is the same that of Lemma 6 in (Zanette & Brunskill, 2019).
Using Lemma 3, we have
HSA
(s, a)
wwn(s,a) - - log
8'
1
HSA
(wn(s,a)) +
(w 11 log
8'
(Kn(s, + H
as
+
Σ
Wph (s,
h=1
wwn(s,a)
where (a) uses the fact that a) E Lg and the definition of Cx, and (b) is due to that for any l: > 0,
h [H] and (s,a) S A, (x)(s, E (0, 1].
Lemma (Standard Visitation Ratio). For any > 0, we have
ΣΣ
K H
Σ
(s,
ax 52 SAlog
KHSA
8'
A= h= (8.0)EL+
Proof of Lemma 7. This proof is the same as that of Lemma 13 in (Zanette & Brunskill, 2019).
Recall that for any ls > O, let wx(s,a) = E( Wks (s, a). Then, we have
K
w
Wn(s,a) a) a)(s,a)
ΣΣ
nx(8,a))
k=
(s.0)EL+
(s,a)ELx
wx(s,a) n=(s,a)
1 ((sss) E Lu}
(3,0)
wk(3,
1 ((s, a) fx)
A= (s.a)e5xA Σ Σ Wk ())
wh(3,
1 ((s a) E fx)
(s.)eSxA k=1 EV=1 Wh (3.0)
23

---

Published as a conference paper at ICLR 2023
where (a) is due to Lemma 6.
According to the definition of C. (Eq. (10)), for any (s, E Sx A, once (s, a) satisfies (s, E Lx in some episode k, it will always satisty (s,a) Lx for all & 2 k. For any (s,a) E S A. let (s, a) denote the first episode &o where (s, LE.
Then, for any and (s, a) S A, if (s,a) Lk, we have
k
An(e,a)-1
Σ
(w, +
E
ww (s)
k=kols,a)
2 H
Wy (s,a)
k=
where (a) uses the fact that (s, a) E Cho(s,a) and the definition of Ls (Eq, (10)).
Thus, have
ΣE Σ
wah(s,
Σ
w a)
52 (x(0)
(*.0)55xAkRha(ee) H Σ ka (s,
(s,a)ELx
wx a). Define function |z| + 41=1 - [x]), where 0 < r S K - (o) + If x is an integer, we have F(x) = Σi= as and otherwise, F(x) interpolates between the function values for integers x. The derivative of (()) f() = a[x]-
Let d1 (ha(s,a) a2 Who(saa)11 ..... 0K CK-
F(r) = -
4=1
Hence, we have
K K-ka(s.))+1
(x
s(k)
Σ
H H+E E =k(eaa) (s
H FFk
ks.0))
f([x])
da
H + F(x1))
K ko(s)))))
f(x) dx
+ F(x))
log
(H + +FK ko a) + 1)) log (H + F(0))
< <log (KH)
KHSA
< log
8'
where (a) uses the fact that for any 0 S x K and (b) due to that (o(s, a) 2 2 by the definitions of L1 (Eq. (10)) and (s,
-K--hof ho(s, + 1, fxx f([x]) and F(x) & F([x1),
Therefore, have
K H
(an(s,a) 52 n)(s,a)
KHSA 8'
ΣΣ
log (s.0)ESXAA
Σ
==1A=1 (s.a)ECx
KHSA 8'
$2
SAlog
Recall that for any (s', E S S A, p(s'ls, a) is the transition probability from (s.a) a) to
s'. For any risk level a E (0, 1]. function S + R and (s' s, E S x A, ( a) the conditional probability of transitioning to s' from (s, conditioning transitioning the
24

---

Published as a conference paper at ICLR 2023
worst o-portion successor states s' (i.e., with the lowest a-portion values V(s')), and it holds that = Lovs ga. (s'(s,a) -V(').
CVaR ~p(ss|(ssa)) (V('') (VV
For any ho > O, h E [H] and (s,0) E ESX A, wkn (s. a) is the probability of visiting (s.a) a) at step h of episode &o (under transition probability p(-1::) )), and it holds that Wkk a) E [0, 1] and
E(sajesxA Whn a) 1. For any risk level a E (0, 11, > 0, h E [H] and (s,a) a) E S x A.
cVaR,o, a)) is the conditional probability of visiting (s, a) at step h of episode k, condi- Wkk tioning on transitioning the worst a-portion successor states s' (i.e., with the lowest a-portion Here x* is the policy taken in episode k, and VE (): S + is the value function step h for policy n² Intuitively, WAy. CVaalaav (s.a) is the probability of visiting (s, a) at step h of episode k under conditional transition probability
values (s")) at each step h' = 1,...,h -
ga. ga.V++ (+++()),-))))) (+),,-) for each step h' -......, h
It holds that for any risk level a (0, 1]. k 0, CVa (8,a) a) E [0, 1] and E(sa)esxA CVaR.o, (8,a) = 1.
h E [H] and (s, a) E S x A, Wkh
Whh
Lemma 8. For any risk level E (0, 1, k > 0, h E [M] and (s,a) 8 A, if wAn (s, 0, then
CVaRa, Wkh kh
(s, 0.
Proof of Lemma 8. If wkb (s, a) 0, then the algorithm has zero probability to visit (s,a) step of episode k, which means that (s, a) is unreachable under transition probability p(-1.-).
Note that for each step h' = I,..., / 1, the conditional transition probability 3o. (s'|s,a) just renormalizes the transition probability and assigns more weights to the worst a-portion suc- cessor states s' (i.e., with the lowest a-portion values (s')), but will not make an unreachable successor state reachable. Thus, (s,a) is also unreachable under conditional transition probability
ga.Vi &
(-),,-)
.) for each step h' 1, .,...,hh h 1. and therefore Wkh CVoRta, (s, 0.
Lemma 9. For any functions V1,... Vn S R, k > 0, h E [H] and (s, a) E S x A such that
WKA (s, a) 0,
Whh
CVaR, V
(s)
min
(8,
min T.h.(s,)): wa.a (s.0)20
W (8,
a)
an
CVaR.a.V (s, denotes the conditional probability of visiting (s, a) at step h of episode k, where wikh conditioning transitioning the worst a-portion successor states s' (i.e., with the lowest portion values Vi+1(*) (s')) ) at each step h' = =,, 1,....,
CVa (s, a.) is the conditional probability of visiting (s, a), we have CVaR,a,V (s) E [0, 1). Since wan a) is the probability of visiting (s, a) at step under policy x and min,,,h(s..) (=,a() (r,4(s, a) is the minimum probability of visiting any reachable
Proof of Lemma 9, Since Wkkh
w gh
(s, a) at any step h over all policies n, we have
Whh (s, a)
min =.hi(s,a): (2,000
Wr,n a).
Hence, we have
CVRR u Ah
(s, a) whh (s, a)
(1I)
min Wr, (5,
(. (1.000
CVaR.a.V (s, a) are the probabilities of visiting (s, a) Let 81 be the initial state. Since (an a) and with at step h with policy = under transition probability p(.l:)) and conditional transition probability ga.Vi'+ (c)).)) for each step h I,...,, h - 1, respectively, we have that
())(s,a)= = Σ
II
p p(sM+1 (w))
(N2 S1-- 1==1
25

---

Published as a conference paper at ICLR 2023
and
h-1
CV V (s,a)=
Σ
II
ga Va.
W kh
=
(02 JJES" 2/=11
where is the initial state, 8h := 8, and On := x (sw: for 1/' = 1,...,.- 1 1.
Recall that for any risk level a (0, 1]. function V S R and (s', s,a) E ExSSxA na (d'ls,)) denotes how large the transition probability of successor state s belongs to the worst a-portion successor states (i.e., with the lowest a-portion values V(-)), which satisfies that wa (e'ls.) ga.V (s'|s, a) and 0 < yaaV (s')s,a) S p(s'|s,a).
Thus, have
a Vo (s 18,, ax)
CVa W kh
(8, ()
Σ
II
( 1eSh-22 M==
a
h-1
Σ
p(sh+ 1 1sp,,ap)
a
(22 1)55h22
A-1
Σ
p(sw+1|8 ,,,,,,,,,, ar)
a-1
( slESa 2M=1
a-1 (un a)
Therefore,
oV
(s, WkA (8, a)
Wihh
(12)
Combining Eqs. (11) and (12), obtain this lemma.
Lemma (Insufficient Visitation). It holds that
CVaR, v
1
1
(s, S min
min
Wx.h (x))(()
all-1
(#.0) CL
n.k.s:
(+)>0
HSA
4SAH
+ 5SAH
8'
Proof of Lemma 10. According the definition of La (Eq. (10)), for any (s, a) S A, once
(s, a) satisfies (s,a) E La in some episode k, it will always satisfy (s, a) E Lx for all k2 2 k. For any (s,a) a) E S x A, let k(s, a) denote the last episode k where (s, & Lt. Then, we have
ΣΣΣ ak)(
Σ
ΣΣ
as) ((s,a) $ Cx)
k= (s,a)
(x,4)ESxA k=
k(saa)
Σ
Σ
Σ
a)
(a,0)E8XA k= h=1
Ma.0)-1 H
" (3, + Σ
Σ (KA)ESXA
Σ
Σ
(s,
k=
h=1
h=1
HSA
Σ
4H log
+ +4H + H
8'
(s.0)ESxA
26

---

Published as a conference paper at ICLR 2023
ps 0.4
a (s =
((yls, = 0.4
p(sgss.a)= 0.3
V(s))
4 ()) = =0
(s5)
(s2ls,a) 0.3
p(3.ls,0) 0.3
p(s ls, = 0.3
n (52 0.2
n (s (s,a) = 0.2
ls,, 0.3
ua (5,1s,a) 0.3
5
S1
$2
S3
$1 Shifted a-quantile line
S2
S3
Original a-quantile line
0.5
Sup {s.}
Sowwn {
Sunch {533
Figure 5: Illustrating example for Lemma 11. For each s' {sı $2, $3). the height of the bar denotes the value (ss') or (s'),, and the width the bar denotes the transition probability p(s'|s, a) (fixed). The colored part of the bars denotes the worst a-portion successor states (i.e., with the lowest a-portion values Vss') or V(s')) )) In this example, a 0.5.
HSA 8'
<4SAH log
+ 55AHH
where (a) is due to that as & Lss and for any k > 0, h H and (s,a) E S A, wkk (s, a) E [0, 1].
For any policy π, E [H] and (s E A, let Wx (s, a) and wn, (s) denote the probabilities of visiting (s, a) and at step h under policy æ, respectively. Then, we have
Σ Σ
Wkk
CVaR.o,V**
(8,0)
k= (K.))&..
CVaR.a.V v=t whh
(8,a) (xb(s,a)
(un(s,a) 1 fuwn a) 0}
k= A=l (L
K
H
min
wkh (8,
min x,h,(s,)): (o,a(0
(x,) --
k= h= (x.a)EE.
JAG
HSA
min
4SAH log
5SAH
min
Wreh a 1-1
J.h.s We. (x)>0
Here (a) is due to Lemma 8. (b) comes from Lemma (c) uses the fact that for any deterministic
policy h E [H] and as, E S x A, we have either Wn,a(s, a) Wx.n or Wn,k a) 0. and thus ming (e,0)) (s,2() Wr. (x,((8, = millg,h,e (=)x Wa. (s).
Recall that for any risk level (0, 1], function V S R and (s', s, a) SxSxA, Ba.V (s'|s, a) is the conditional probability of transitioning to s' from (s, a), conditioning on transitioning to the worst a- a-portion successor states (i.e., with the lowest a-portion values V(s'), and it holds that CVaR s'p(s" (s.a) (V(s') = EEres ga.V (s'|s, a) V(s').
Lemma 11 (CVaR Gap due Value Function Shift), For any (s, a) SxA. distribution p(-(s, a) As. and functions V. V S + [0, H) such that ((s') 2 (s') for any s' S.
CVaR
(()))) (V('')
CVaR
Sp ll) (V(s') < 8a. V (118,a)T (V -V).
27

---

Published as a conference paper at ICLR 2023
Proof of Lemma 11. Recall that for any risk level (0, 1]. function V : + and (s', s.a) x x A, (s'ls, a) is the conditional transition probability from (s, a) to s', conditioning on transitioning to the worst a-portion successor states s' (i.e., with the lowest a-portion values (s*'), and y (d'ss,a) a) denotes how large the transition probability of successor state s' belongs to the worst a-portion, which satisfies that (d'lsaa) = ga.V (s']s, a) and Eves (.. (5'18, = a. Then, for any risk level a (0, 1], function V - R and (s', s, ES88xA A.
(1. Eveesav (8')s, V(s') = Σ gav S'ES
V(s'),
As shown in Figure 5, we sort all successor states s' S by their values V(s') in ascending order (from left to right). Fix the transition probability p(-|s, a) and the value function shifts from (.) to V()) Then, below we divide all successor states s' S into three subsets, i.e., Sup- Sdown and Sunch. according to how ya. (s'(s,a) changes to na, (s'1s, a) as V(8') shifts to V(s').
For any s' E Sups na. (d'1s,, < (s') s, a). the rank of s' goes up, and the position of s' moves to the right (here "rank" means to rank all successor states s E S by their values (s') or (ss)) from highest to lowest).
For any E Sdown, a (s'(s, > (s) the rank s' goes down, and the position of s' moves to the left.
For any s' E Sunch, / (5')8,0) = ( the rank and position of s' keep un- changed.
Then, it holds that
Σ S'E
(ne
Σ
(108(6118,0)- (1aV(()s,)))) = 0. (13)
8 E'doow
Next, we have
CVaR (oplaaa))
CVaR S/ppleo (V(())
_ Σ
(5'1s,))))) - (5))))))))))) V(5))
d'ESup
Σ
(n (5'ss,))) V(5')-++*
- (5'(sss (s1)),))-v((')
s S'ESdown
Σ
(d(1,)'(1)))) V(s') - , (s's()'))))) (o)ss.))vv(()))))))))))
S'Enunch
Σ
(5'ls,)) (V(x)- ((<)) (5')s,)))))))) -x -1010 (00
((6'))
d'ESup
p ( (V(s,)))(((()))))))))))))))))))) - -v())))()) + (51)) - V(6')
+
d'ESoomn
aa (s'(s,)) (V(s)- -(6'))
S'EGunch
Σ (s'(s, (V(s)) - v(5))= - Σ
(wa.V("((ss)) (d)3))))))))) V(5')
SES
S'ESup
Σ ( a (s(1s,))) V(s')
S'E
28

---

Published as a conference paper at ICLR 2023
( Evay (d'1s,)) ())s,))((((s')))))))))))))))))()
min V(8).
Σ
(1a. - 1a. -1. 1 (s'1s,
s'ESup
FE
3'ESup
min V(8). d'ESup
Σ
- 1..
s'ESdown
(b) Σ uav (8)
(s)ssa)
= (+|s,a) VV)
Here (a) due to that for any Sup. (d'1,,, a) < vay (d'ls,,)) and for any E Sup-
E Sdowns (ss)= 2 V(s'). (b) comes from Eq. (13).
D.1.3 PROOF OF THEOREM
Proof of Theorem I. Suppose that event & holds. Then, for any E [K].
(s((s) V1" (sf)
(V/( -VT (st)
=min r(stt at) + CVaR
( (V2"())
L
H
ma(sf,af))
-(r(st cVaRs -
(ntt)) (V/ (s'))
H
Sr(sf, + CVaR
Coaar (1 (s))) min
H
a an(
- -(r(st, + CVaRR
Sp (st (Va (d)))
H
L
min
H + CVaR
(1) (1 (V))
- CVaR
>pp((t) (P (F)
nn(sf,af) at)
+ CVaR popppp
(s)))
CVaRg
sopp aft) (V2** (s'))
min
H
L
H
+min
4H
aff H +ga.13
SL
3 (tst (V² -1,')
a no(st,
WAB
HVL+ 4H SL
Σ Ba. (s2lst, att (V2)))) - (x2))
min
2H
av/ (ff at)
HVL+AHVSL 2H
min
(s2ls)
avni(st, a
$
HVL+4HVSS 2H
+ Σ
Ba,
(83182, 02) (V5(+a) - V3=((s))) (sa))
min
n2 02)
HVT.+HHVSI
min
2H
+
Σ
ga.12
V2rk
(s2lst.af)
a oVne(st, at)
$2ES
HVL+4HVSH 2H + Σ
min
3o.13
a2)
(V/12(82,00 (12)
S
29

---

Published as a conference paper at ICLR 2023
... Σ
ga.Vil (sn)))--,ann-1)
WVL++HVVLL min
- 2H
1))
avnn(ss..a)
#EE
CVaR,.VV* Wkh
HVL 4HVSL 2H
(s,a) min (min
avni(s,a)
1= (s,
CVaR,avV*
HVL+ 4HVSL av avnx(s,a)
Wkh
(8,a)
(s,a)ELx
Σ
whh
CVaR, (8,
(14)
h=1 (a.0)ELe
Here an = T
* (8h) for 2..... H. (a) due to Lemma (b) uses Lemma 2 and the fact that for any k 0 [H] and E S, (s) [0, H). and thus for any k > 0, h E [f] and (s, a) E S x A,
CVaR g' (VA h+1 (s')) - CVaR
(V ( (s') S H, and also uses Lemma 11. (c) comes from the property of min (d) and (e) follow from recurrently applying steps (a)-(c). (f) is due to that CVaR,o, (s, is defined as the probability of visiting (s, a) at step h of episode under kh
the conditional transition probability ga, V2 (-1:,) -) for each step h' = I...., 1.
Since the second term in Eq. (14) can be bounded by Lemma 10, below we analyze the first term.
Recall that for any policy æ, h [H] and (s,a) S x A, Wx,a(s, a) and (x,n(s) denote the probabilities of visiting (s, a) and s at step h under policy स, respectively. Summing the first term in Eq. (14) over & E [K], we have
K
H
aVaR, V
wkk
()
a a))()8,
h=1 (o.
H HVL + 4HVSL
K
CVaR V= (s,
K ΣΣ
Wkh
Σ
oVaR (s,a)
Wk
TE (s
(s,0)EL
(8,a)ELx
HVL 4H
K
a. Whh ax(
(s,a)
(Wwn #0} VKH
==1=11 (s,a)ECs
(HVL 4HVSL) VKH
K H
CVaR, (8, (an(s, 1 (w 0}
Wkh wan(s,
a
ax(s,a)
(NO)EC
GA 33 (HVLLAH/SLVKY
H
(s
min
min
(x,n( HI k 1h (e,0)EL
ng(8,0 a)
(a,a) (.,a(0
(HVT. AH KH
2 SSLL min
min s.hi (a)(
W (x)n(s)
IOHSLLKHA
a x.h. (e)
min (x)( Va
Here (a) is due to Lemma 8 and the fact that for any k > 0 and h E [H], E(eNjsSAA Wkh
V= ()) (b) comes from Lemma (c) uses Lemma 7 and the fact that
30

---

Published as a conference paper at ICLR 2023
for any deterministic policy h E [H] and (s, S x A. we have either (x,)(s,a) wn. (s) or Wx (5, (5, a) = O, and thus minz,,.(s;a)) (s,a)) Wa, & (s, a) ming,h,s: "h,, (8)200 W (8).
Then, summing the first and second terms in Eq. (14) over k E [K] and using Lemma 10, we have
R(K) = Σ (1) VI (sf)
1=1
HVL + 4HV
wkh
(8,
av (x(
(s,a)ELn
aV vor (8,0) 2H
Wh
(8,0)EL2
10HS KHA
KHSA 8'
<min
log
Va
min
Wn (s)
xt R.h.s: (
(SSAHL log
HSA
min
10SA112
min
(x)n(s)
Wr.
a aH-11
8'
s,h.s (a.(())200
When K is large enough, the first term dominates the bound, and thus we obtain Theorem
D.2 PROOF OF REGRET LOWER BOUND
Below prove the regret lower bound (Theorem 2) for Iterated CVaR RL-RM.
Proof of Theorem 2. First, construct an instance where min,,,,,s: we,n(s)>0 (s) > a=11
and prove that on this instance any algorithm must suffer a 2 V min wx ( (e,((s)
AK
regret.
Consider the instance shown in Figure 6 (the same Figure 1 in the main text):
The state space is (s1, . Sny 31, F2, 1s,, where 8ı is the initial state, and n S - <
S < 2 H.
The reward functions are as follows. For any E A. r() 1.22 0.8 and r(æ3. 0.2. For any E [m] and a E A. r(si, a) = 0.
The transition distributions are as follows. Let μ be a parameter which satisfies that 0 < a < / < 3- For any a E A. p(82) $1, a) = n. p(z1|11,
and p(zz|s1, a) = μ. For any E (2,...,77 n - 1} and E A. p(s [8, a) = μ and p(z) [8; a) = μ.. 31, D2 and z3 are absorbing states, i.e., for any a E A, p(z ((, Let a, the optimal action state 8n, which is uniformly drawn from A. For the optimal action a.. p(zy|sn, a.) 1 + 77 and p(z (22 Sn, a.)
3p. p(22)
1, p(z2 (12, a) 1 and p(za|a3, a) 1.
17. where r is parameter which satisfies 0 < 77 < a and will be chosen later. For any suboptimal action a E A {ay}, p(22|s a) = a and ()) a.
For any aj E A, let EyI.] and Pry denote the expectation and probability operators under the instance with a, aj. Let Eunisl? and Prumis[]] denote the expectation and probability operators under the uniform instance where all actions a E A in state have the same transition distribution, ie., p(#2|sn, a) 1 and p(rz|sn;;))
Fix an algorithm A. Let * denote the policy taken by algorithm A in episode k. Let No...;; = ΣK IK, 1 (s,) = ) denote the number of episodes that the policy chooses aj in state sn, Let Vanaa denote the number of episodes that the algorithm A visits (8n, az). Let wss.) denote the
31

---

Published as a conference paper at ICLR 2023
Reward 0.8
Action dswa: 1 a Action a": 1
R
ST
Sm
Reward 0.2
Action agubi Action a": a
1 3/
X1
Reward 1
Figure 6: Instance of lower bounds (Theorems 2 and 5) for the min,, m,h,: w (s))0 Wx,h(s) > a H-1 case.
probability of visiting 5n in an episode (the probability of visiting on is the same for all policies). IE[N....ag]
Then, it holds that E[Ve,.ay]= = w(s,)
Recall that a the optimal action in state 8n. According the definition of the value function for Iterated CVaR RL, we have that
(i( (a 11 -0.((H n) + 0.8(H m)
a
and for any policy n,
(7*(s)= (a -n) 0..(H n) + n 0.8 H n) (1((()) aa}
a
+ 0.2 n). (1 (T( az)).
If J = j. for any policy n,
((())) (T1 7 0.6(H n) (1 (T(n)) = az)),
(15)
and summing all episodes & [K], we have
K E, (R()) Σ (8) - V/ VTT(
n 0.6(H - n) KK- Σ (snss = a;}
K
km
7 0.6(H - -n)
(K- (N,,,...,)))
Therefore, we have
A K A
E [[(K]]
=
(i'(s)) - -Vr=* v()(((11)
j=1 k=1
= + Σ
0.6(H n) (K 1Ey a))
1=1
-0.6(H n)
K
E, (an.a)
(16)
A j=1
For any j [A]. using Pinsker's inequality and 0
< a
3 we have that
KL(Punis (Sn, a;) (p)lpy az)) (L - 11))
enn for some
(o
(0-
1-(
32

---

Published as a conference paper at ICLR 2023
constant e1 and small enough 7). Then, using Lemma A.1 I in (Auer et al., 2002), have that for any j E [A], E sa SBunis sn 2 V
K
KL (Punss (3n 9,)lp, a,))
K Sounisl-Vaneee V //u(sn) Banss(AVsmaa))
c1n2
Then, using
Σك=1 Eunis [N and the Cauchy-Schwand inequality, we have
1
K
C1
By LV sn
Eunis (NV,,eN
((x) -uuniy [N)...a)]
A
2A
3
j=1
Kn
E Bunif N as 1+
w(sn) Eunis [Nenas)
2A
a
j=1
j=1
K
Kn
C1 w(n))
$
+
(17)
A
2
aA
By plugging Eq. (17) into Eq. (16), we have
E [R(K) 2 0.6(H - n)
17
K
K
Kn
C1
w Sn
A
2
aA
Let 22
aA w(s,)KK
for small enough constant C2. We have
E [R((K] =Ω
H
wo K K
AK a w((s))
=s "
Recall that Hl and 0 p $. Thus, have that ming, wi, (s) WT, (s) w(sn) = pm11 > a 1 and
AK
E [R(]] =s
a
min
Wa, (x,h(s)
a,h. (r)2
Next, we construct another instance where a 11-1 > min w. m())20 (s). and prove that on this instance any algorithm must suffer a 26
AK ②V
--
regret.
Consider the instance shown in Figure 7: The state space is S {s ( Sn, 2/y .... 8 T1 11, 33, F4J. where /I and is the initial state. Let
< 1
The reward functions are as follows. For any E A. r()1,)) = r( a) = 1, r(12, a) 0.8 and r(13, a) = 0.2. For any E [n] and a A, r(s, a) = For any E f2...., n) and a e A,
r(5/, a) 0.
The transition distributions are as follows. For any a E A, p(sg|sı, a) a, p(s//sı,,) = y and p(21 a) = 1 1----a a. For any E {2, .2,....f n- 1) and E p(5141|8;, 1 a. For any E {2...., - 1) and E A. p(s 18 a) and p(z1 [s/ a) = 1-7. For any a A. p(aa|s',
and p(z a)
= 7 and p(z11%% a) 11-7 7. 3t, 32, 23 and æ4 absorbing states, i.e., for any a E A and i E [4], p( a) = Let a, be the optimal action in state 8n. which is uniformly drawn from A. For the optimal action a,, p(rglsn,
+ 7) and p( a.)
1).
33

---

Published as a conference paper at ICLR 2023
Reward
Action dsub: Action a": 1 +1
a
a
Roward 0.2
$
2/
Sn-1
Sn
Action asub a Action a":
Y
2
1-a-y
1-y
1-y
Reward
1 1-y
x1
Reward
Figure 7: Instance of lower bounds (Theorems and 5) for the R ming,,, (x)()))00 Wr,h (s) case.
where is a parameter which satisfies 0 < < a and will be chosen later. For any suboptimal action a E A \ {ay), p(22)s,, a) a and p8 a) a.
According to the definition of the value function for Iterated CVaR RL, we have that Vi((s)) 0.2(a 7) + 0.87
and for any policy π,
(TT(s) = 0.2(a -1) 1)) + 0.8n
1 (T(s)) = a.} + 0.2 1 (x(sn) = aas)).
= j. for any policy n,
(i( (71 0.61) (1 ( =0y)),
(18)
and summing over all episodes & E [K]. we have
K
E, [R(K)] = Σ
Vii) - V/ (81)
k=1
0.6n
K Σ ((7()) ast
a
kml
0.6y
(K -
Therefore, we have
A K
E
[R(K)
= A
(ir - -VT (81)
j=1 k=1
A Σ
0.6n
(K (N..
a
1=1
0.61)
A
K
Σ
E, NN..
(19)
Recall that 0 < 1. For any j E [A]. have that (L(Punif (,))lp(ss,,
(Be) - 7)) S (a-m)(l-tt) S cin" for some constant C₁ and small enough 7).
34

---

Published as a conference paper at ICLR 2023
Then, using Lemma A.I in (Auer et al., 2002), we have that for any j [A],
K
Ey(Ne, sa .,1 Bunis (No.
+
2 V Eunsy[Von.ey KL (Panss (sn (pp a,))
K
2 V (((s))) Eunss(ANonaa) C172
Bunni (No..
+
Then, using Ej=1 Eunif (N [Non.ay) = K and the Cauchy-Schwaane Schwarz inequality, we have
A
1
Kn
C1
B, N sn I
Bunsy (Nons(A
((x)) ) Bunis [NNen.a)]
A
A
2A
==1
==1
A
Kn
Bunis [Nn. ]]
+
w(sn) IEunis [Ne
2A
a
j=1
j=1
K
Km
C1 W(())KK aA
(20)
A
By plugging Eq. (20) into Eq. (19), have
0.61) a
K
Ci
w(sn)K
E [RK)
K
A
aA
Let 1/ = /2/ w(sn)K
for small enough constant C2. have
A
E [R[(K]]
=Ω
(V
K
ar. w(8)))
AK
=s
a. w(sx)
Recall that < 7 a and H 1. Thus, we have min wx.x (x)((s) w(rs)
y H- < H-1 In addition, since w(sn)) = n- = a H-2 we have
AK
[R(K]] =Ω
AK
#-1
E PROOFS FOR ITERATED CVAR RL WITH BEST POLICY IDENTIFICATION
In this section, we present the pseudo-code and detailed description algorithm ICVaR-BPI, and formally state the sample complexity lower bound for Iterated CVaR-BPI (Theorem 5). We also give the proofs of sample complexity upper and lower bounds (Theorems 3 and 5).
E. ALGORITHM ICVaR-BPI
Algorithm ICVaR-BPI (Algorithm 3) constructs optimistic and pessimistic value func- tions, estimation error, and hypothesized optimal policy in each episode, and returns the hypothesized optimal policy when the estimation error shrinks within e. Specif- ically, in each episode k. ICVaR-BPI calculates the empirical CVaR for values of next states CVaRs (Vi (8')) CVaR2 2' (s')+()')) and exploration bonuses
35

---

Published as a conference paper at ICLR 2023
Algorithm: 3: ICVaR-BPI
Input: E, 6, a, 8' == 6 L(k) log( (2H for any k >
7.
8'
J - (s) = H+1 (s) = - = 0 for any h >> 0 and E S.
for k = 1, .
K do
for h H, H 1,..,, do
for s E S do
for a E Aoo
5
(s,a) + min r(s,a) + CVaR (M ( + # L(k)
nals,a)
H
(s, max
((8,0)) + CVaRR &' (1b,a) 1 (8')) 4ll SLik)
0}
mx(a,a)
M(L4AB3) + 8 B (118, a) Jhtt H]: (*, t min
x + argmax (s. (s) + max,ed (s) V 2 ())) (s) + C (s))
if (s) < E then L return क. (x) else
10
11
Play the episode k with policy x² and update nu- (8, a) and (8'18,
H Lik) 4H or mu(a,a) V nz(a,a)' to establish the optimistic and pessimistic Q-value functions (s,
SL(k)
and (s, respectively. ICVaR-BPI further maintains a hypothesized optimal policy n² which
greedy with respect (s, a). Let 3t:a. (-|s, a) denote the conditional empirical transition probability in episode k; conditioning on transitioning to the worst a-portion successor states s' (i.e.,
with the worst a-portion values y (s')), and it satisfies Eves 3 (s'|s, a) (s') =
of (-1,,) (s')) (Line 7). Then, ICVaR-BPI computes estimation error (s, a) and Jh (s) using conditional transition probability (-)ss Once estimation error JH(s) (s) shrinks within accuracy parameter ICVaR-BPI returns the hypothesized optimal policy nh
E.2 PROOFS OF SAMPLE COMPLEXITY UPPER BOUND
E.2.1 CONCENTRATION
In the best policy identification analysis, we introduce several useful lemmas and concentration events. Different from the regret minimization analysis where the logrithmic factor log( K KHSA
in the exploration bonuses is an universal constant, here the logrithmic factor log( increase as the index of the episode increases.
28 HSA will
Lemma 12 (Concentration for V BPI). It holds that
H.
log (22- (SA
Pr
CVaRo 8 (ptt (V)
CVaR (p.))) (V+(('))
a
n& (8, a)
Vk 0, wh H V(s S
2 1 2
Proof of Lemma 12. Using the same analysis as Lemma 1, we have that for a fixed k
log 22h HSA
( "V - CVaR (pp(() (V7(3))
Pr
(s(
W ((s,0)
> 1 2k
36

---

Published as a conference paper at ICLR 2023
By union bound over ...,..., have
log (2.HHAA)
Pr
CVaR (ttt,a (Vi((s))
CVaR pp()) & (V(((()))
(s, a)
Vk > 0, vh E [I], (
8
8'
21
2h
21 28'.
Lemma 13 (Concentration for any V BPI). It holds that
CvaRg (H (V(s)) CVaR (o0 (V))))))))
2H
2S log
224 6'
Pr
a V
nu (x a)
: HJ, 4k 0, (( A
21-28'
Proof of Lemma 13. Using the same analysis as Lemma 2, we have that for a fixed k
Pr
CVaRg &
(V(s))
CVaR 8 s 190) (V()))
2H
2S log
22* 8'
n (8,
8'
W ((s E 21 2k2
By union bound over A 1,2,... we have
2H
2S log 2k HSA
Pr
CVaRg (-1s,a)) (V(s')) - CVaR ~p(-1a))) (V(8))
S
ms(8, ()
VV S 0, H1, Vk > O, ((s,a)E8xx
8'
21 21-2.
21
-8'
For any risk level a E (0, 1), function V S + IR, > and (s', s, S A, fa. (s'1s, and @A a) are the conditional transition probability from (s, a) to s' and the conditional transitioning to
empirical transition probability from (s.a) to s' in episode k. conditioning the worst a-portion successor states (i.e., with the lowest a-portion values V(s')), respectively. ya.V (s')s, a) and j.a. (s'1s, a) denote how large the transition probability of successor state s' and the empirical transition probability successor state s' in episode & belong to the worst a-portion, respectively. holds that
aaa (5'1s, a) -3. B...VaVVsllll (s'1s,a),
and
kla. (s'ls, a) = -/.a.V (5'(s, a).
a
37

---

Published as a conference paper at ICLR 2023
Lemma 14 (Concentration for conditional transition probability). It holds that
2 <
25 log (2k9HSA) 8'
Pr
( (5'
a
ns(s,a)
W vk Vi. E(
2 21-22 28'.
Proof of Lemma 14. Using the analysis of Eq. (7), we have that for any levell E (0, 1], function V 8 R. k 0 and (s,a) E x A, pa.. (8|ssaa) 2 Σ
-
- p(s'|s,a)
(21)
S'ES
s'ES
Using Eq. (55) in (Zanette & Brunskill, 2019) (originated from (Weissman al., 2003)), we have that for any fixed k with probability at least (zx= ), for any (s,a) E A.
25 25
(26 8'
Σ d'ES
(5'ls,))) - p(d (1,1),a) a)l S
n& (8, a)
and thus,
N (s'(s.
aay (s'(s,a)
Σ ''ES
Bkra. V (s'1s,a) - -B.. (s) = =E
S'ES
Eves (itra.(8'lss, aaaaaasss (5'ls,u)
a 2 Eves (5'1s,)) - p(s -(((11a))
2 25 Slog (2SHSA)
S V
(s(
By union bound over A 1,2...., we have
25 log
(SA 8'
Σ
gloa. -B. (5'1s,a) (d)
Pr
<
(s( a)
E'ES
AA 8 R, Ak 0, ((8 ES A
8'
21 2. k=1
21.2
21 - 28'.
To sum up. we define the following concentration events and recall event Eg.
H
log
F
CVaR ( (V") CVaR (V (V2())))))
< a
6'
To a)
((s,a) E A A
Vk > O, vh E [H], V(s,a)
2H
25 log
HAA
Fg { CVaRg ( (11sa) (V(s') - CVaR Mp) (V())))
8
Th (8. ())
38

---

Published as a conference paper at ICLR 2023
AA S H], A > 0, ((s,a)
F3
( Ba. (5 (8118,00 a)
V
2
25 log (26'HSA)
n6(s,a)
AA SW+R, A4 0, v(s,a) E S
k-1
(HSA)
83 (4(5, a) 2
wwn(s,a)
Hlog
Ah > 0, ((s,))
b=1hn=
F= F33 &3
Lemma 15. Letting = 5 it holds that
Pr Pr > 1-66 8.
Proof of Lemma 15. This lemma can be obtained by combining Lemmas 12-14 and 3.
E.2.2 OPTIMISM AND ESTIMATION ERROR
For any ls > 0, let L(k: log (2H
Lemma 16 (Optimism and Pessimism). Suppose that event F holds. Then, for any k > 0, h E [H] and 8 E S,
(=) 2 (s),),
(S()) S V. (s).
Proof of Lemma 16. The proof (x) 2 Vs)(s is similar Lemma 5. Below we prove vi()) s Vr" (s) by induction.
First, for any h > 0, s E S, holds that 1 (8) V = 0.
Then, for any k 0, h e [H] and (s,a) S A. if (s, O. Q% QT (s, trivially holds, and otherwise.
4H
Sī(()
(s, a) =r(s,a) CVaR (1s,)) (Vitt
a
nu (s,a)
(r(8,a) CVaR (Vi++ 4H
Sī(k)
a ())
(r( + CVaR
(s'))
(CVaR (Vitt (s'))
CVaR xp (V
=r(s,a) CVaR CVaR ( (V7" -Q² (s,a).
where (a) uses the induction hypothesis, and (b) comes from Lemma 2.
Thus, we have
11(s) = (() S O (s, (s)))())) vs)((), (s),
which concludes the proof.
39

---

Published as a conference paper at ICLR 2023
For any risk level E 1], k O, h E [M] and (,), E x SxSx x A, 3l:o.V2-1 (6'1s, a) is the conditional empirical transition probability from (s,a) to s' in episode ks conditioning on transi- tioning to the worst a-portion successor states s' (i.e., with the lowest a-portion values V (s')). holds that CVaR s' (-1s,a) ( = Eves (lia.iiiiss a,)) 1
Lemma 17 (Estimation Error). Suppose that event F. holds. Then, for any k. > 0,
(i((s)) - Vi (s1) S (s1)
Proof of Lemma 17. In the following, we prove by induction that for any &s > 0, h E [H] and s E S, (a) (s) S J/(()
(22)
First, for any & > and s E S, it holds that / (s) - V (s) = - (s)= =0
Then, for any k > 0, h E [H] and (s,a) E A. if C (s, a) H. ()) holds trivially, and otherwise,
( (x, s (s,,a)
H a (x a mx(s,a) (s) ())
L(k)
+ 4H Si(k)
CVaRg (ogtttp (V++1 (s'))
(Vh++ (5')
(2) H / [(K)(( + 4V
+ Blinn (-1s,a) (Vi+ kh+t)
avn)(s,a)
(b) H [1())(++
+ 3is.. (1)s,a) J Sht2
avn((s.a) as,
where (a) uses Lemma 11 with empirical transition probability 1 (-|s, a), conditional empirical transition probability 3tsa. (-1s, a), and values V/t+1) Vh and (b) is due to the induction hy- pothesis.
Thus,
(s) - (i( = (())) (7) (ss))
which completes the proof of Eq. (22). Hence, for any & > O,
& (s1).
Using Lemma 16, we have
Vi((s) V/ (si) s (s1(s) (i(ss) S (s1))
E.2.3 PROOF OF THEOREM?
Proof of Theorem 3. Suppose that event JF holds.
First, we prove the correctness. Using Lemma 17, when algorithm ICVaR-BPI stops, we have
(s1) - - (s1) s (f1) S
Thus, the output policy * is s-optimal.
Next, we prove the sample complexity.
40

---

Published as a conference paper at ICLR 2023
Unfolding J (s1), we have
H(1 + ++++) L(k)
(s)) min
+
glia Vi (82))1,01) (52), H
a av mn a1)
#2ES
H(1+4v5)V L(k)
minn
go. (82)51, (5
av
Σ
(3tiav (52()1, - ga.L3s (s2)s1, 1 (52), H
H(L H[1+ + 4v 5) L(k)
(b)
min
+
Σ
ga. ga.Li (8218,,))),, (82)
avnn2ss,
#2ES
+
(Bira.L (82181,
(1)))) H
$2ES
min
H(1 + 4VS)V i(k)
+
Σ
( -
(52) + 4H
V mx(s),a))
S L(k) H
aV,n($51 a1)
#265
H(1 H(1+ iik)
min
H
+
v2
(1) 12
aV (V 01)
E
H(1+8V5) L(K)
min
H
Σ
ga.V2 (521s1,a1)-
(n a1)
H(1 H(1+8V5) L(k)
min
Σ
gaL's (sal82, a2) . ($(a)
av (32,
$B
H(1 H(1+8v5) i(k)
min
H
+ Σ
ga.L's (1))
(11,
H(1+8v5) i(k)
Σ SgES
go. (83(82, az)
min
(82, a2)
H(1 + 8V SVS) L(A) H 1))
(sal min
a / an)
RHES
H
H(1+8VS) L(k) H
CVaR,a. (s,a) min wkh
a m
h=1 (e,0)ESXA
11
H(L+8VS)V L(k)
H
Σ
CVaR,a.V Wigh
(8,a)
Σ Σ
CVaR, Wihh
(8,a) H
a (s
A= (3,
h= (SA)EC
Here (b) is due to that for any 1 > 0, E [H] and E S, S, [0, HJ. comes from Lemma 14.
(e) and (f) follow from recurrently applying steps (a)-(d). (g) the fact that w oVaR,o.V'* (s, a) is defined as the probability of visiting (s, at step à of episode under the conditional transition
probability go.K2 (-l.-)) for each step h' 1, I,...,hh
41

---

Published as a conference paper at ICLR 2023
Let denote the episode in which algorithm ICVaR-BPI stops (ICVaR-BPI will not sample any trajectory in the stopping episode r). Then, for any h T, we have & < (s1). Summing over k T, we have
(T () -) 8 Σ (x1)
H(1+ 5) L(k)
OVaR,o. Wkh
(8,0)
avnx(s,,)
1=1 (s,a)ELa
Σ
CVaR.a. wih
(8,a).1
= (s,0)ELK
H(1 + H((1+8VS) L(T
CVaR, (s,a)
Wih
(x(
k= [s.a)ECx
H
ΣΣ Σ
whh
av
(s,a)
k=1== (s,a)ELx
+ min
1
4SAH2 log
HSA 8'
+ 5SAH2
min
(r.b(()
a
J.his:: we ([))20
H(1 + 8VS))////////////))))/ ((T 1)
T-1 H
CVR V
(s.
11-1)
Wkh
(
k= 1=11 (E,0)EL
+ mim
[ASAHH log
HSA 8
+ 55
min W7,a (8) HI
T.his: we wenn 11)200
( (1 + 8/5H/HHHHHHH
- 1) ((--1)-(T-))
a
ΣΣ Σ k=1k=1 (s,a)EL+
T-1 H
With
CVaR.
kb
(s,a)
ww)(s,a)
1 (s, #0}
(
mx(
1
HSA 8
+ min
4SAH² log
+ 5SAHH
min
(s) a
n.his: we kss)20
(1 + 8/S) H. L(( 1).(T 1) 1)
min
min h.hs Wi (8)
(x))(s)
11
(hn a)
()( + min
min (x(((s)
HH-
Am Aml (s,a)ELe
J.h.s: (x)x
HSA
4SAH² log
+5SAH²
8'
(1 8V5)H
H. L(T 1) (T (T- 1)
min
wr (s) VoH-1"
min
x h.s (=)())>0
42

---

Published as a conference paper at ICLR 2023
2v SA - 1) + min
min
(x)(())
a
Fch,s: (x)20
HSA
4SAH log
5SAH?
8'
18SH
HA(T-
min
VaH-1
a, a (s)((s)
min
a
1
4SAHH log
HSA 8'
+ 55SAI)).
+ min
min R.bss: un (8)20
Wr, Wn.h (8)
HH-I
where (a) due to Lemma 10, (b) uses the fact that for any risk level a E (0, 1]. k > and h E [H]. E(ra)ESxA
MSA CVaR,o. Wkk
(s, a) 1, (c) comes from Lemma 8, and (d) is due Lemma
Thus, when log
2 1, we have
1
1
18SH /HA
2HSA(T 1)3
<min
VT 1.log
min
Wx. (x)
V-
EQ
8'
x.h. m (s)20
4SAH log (SA))
+ 58
+ min
s.h.s we (8)20 (s)
min
a-
1
1
54SH HA
2HSA(T - 1)
<min
VT 1.log
min
Wr (s))
V-"
8'
R,h, (a)(
9SAH!
HSA
+ min
log
min
W (x)
I-I
E
Ryh,s 10 (5)00
Using Lemma 24 with A = B, = 0, C' C'= min(
Vo*--- 51SHVHA
min hh wa ( (x) " "..)(s)" V #-1 9 E 0. 3
D = min min ming A. we ( (=))
2HSA 8'
and T = - 1, and
recalling that algorithm ICVaR-BPI does not sample any trajectory in the stopping episode т, have that the number used trajectories bounded by
H3S2A
T
min
min
W (s)) a1-
e?a?
n.h,e wi (e)20
1
HSA
log
min
min
Wx,a(s)
H-I
T.h.s: Wa,
(s)( (5)>0
E.3 SAMPLE COMPLEXITY LOWER BOUND
Below we present the sample complexity lower bound for Iterated CVaR RL-BPI and provide its proof.
We say algorithm is (8, e)-correct if A returns e-optimal policy such that (s1) 2 (81)) E with probability 1 - 8.
43

---

Published as a conference paper at ICLR 2023
Theorem 5 (Sample Complexity Lower Bound), There exists instance of Iterated CVaR RL- BPI. where minz,h.s w,, a x4))20 W))((() > n- and the number of trajectories used by any (Ó, E)-
correct algorithm is at least
HA
1 1
Ω
log
c
min
Wn. (8)
nt. su,,, ws (6)200
In addition, there also exists an instance of Iterated CVaR RL-BPI, where a ming h.ss wts)00 W (s) and the number of trajectories used by any (6, (6.orcct algorithm at least
Ω 1- log 1))
Theorem 5 corroborates that when is small, the factor min,,,,,s w. (s)o0 (s) (s) is unavoidable in general. This reveals the intrinsic hardness of Iterated CVaR RI, i.e., when the agent is highly risk-sensitive, she needs spend number of trajectories exploring critical but hard-to-reach states in order to identify an optimal policy.
Proof of Theorem 5. This proof uses similar analytical procedure Theorem 2 in (Dann & Brun- skill, 2015).
First, consider the instance in Figure 6 as in the proof of Theorem 2. where ming we (8)20 Wy (3)) > a H-1, Below we prove that on this instance any algorithm must suffer O min
=²5aA log(?)) regret.
(x))(a)
6"a²
h,hs wa (3)20
Fix an algorithm A. Define Es,, (*(sn) a.} as the event that the output policy of algorithm A chooses the optimal action in state 8n.
Using the similar analysis in the proof of Theorem (Eq. (15)), have
(st) =066) -n) " {E.,)) }).
For to be s-optimal, need
2 -V = 0.6H D. (Ea.1))
which is equivalent to
E0
1 (E 211 0.6(H n)
Let =
Se* ca 0.6co(H-n) for some constant cp and small enough e. Then, for स to be c-optimal, we need
Co Set
(E 2
Let Φ :=
6o 864
For algorithm A to be (e, 8) correct, we need
1 1 8 < Pr(V" - V" 2 c]
Pr 1 (Erm) } 2
E|E,a]
Φ
1
< Pr(S...
0
which is equivalent
Pr|E..| = Pr(Es., 0 Ø8.
44

---

Published as a conference paper at ICLR 2023
Recall that 0
3- For any [A], (L(Pansy($ns aj) (s)) a,)) KL(Ber(a)|Ber(a
7)) S (1-1)(1-+1) cr-22 for some constant ei and small enough Let Va, be the number of
times that algorithm visited state Sn. To ensure Pr(E..] S Φ + Φò, we need
C 1 - Φ + Φ
B[V,
log
KL (PLii az) (sn az))
j=1
a.A log
C2
1 172
1 1
Ø + dd
aA 0.6²
n)²
C2
log
Cn
+ 6
Se
for some constant C2.
Let co be small constant such that co < 8. Let w(sn) denote the probability of visiting &n in
Se4 an episode, and this probability is the same for all policies. Let T denote the number of trajectories required by A to be (s, -cooreet. Then, must satisfy
A 0.6 og n2) log cD
c 64 aa w(sn)
+ 8
S
H²A
=Ω
log
E²a wsn)
8
Recall that H and < 1 Thus, in the constructed instance (Figure 6), have that ming, h,s: w))()))0 Wx, (s)) w(s))
1 nn1 > H-1 and
H²A
=
log
ca
min
Wi.h
m,h. wi (s)20
Next, we consider the instance in Figure as in the proof of Theorem 2, where a H-1 > min, h,s w. (4))00 (s). Below we prove that on this instance any algorithm must suffer O H²S²A log( {)) regret.
sta
Define E,,, := (sx) = ).} as the event that the output policy a of algorithm A chooses the
optimal action in state snt
Using the similar analysis as in the proof of Theorem (Eq. (18)), we have
(s1) (s1) 0.67 (1 (Es,)) }).
For to be s-optimal, need
2 Vi*(s)) - (s1 0.69
(1 1 {E,n)),
a
which is equivalent to
(E,,)) 2
E0
0.6r)
Let
Setea for some constant cp and small enough Then, for to be e-optimal, need 0.6cp
1 (E 2
Se
Let = co. For algorithm A to be (c, 8) correect, we need
1 1 Pr(V" Va 2 c]
Pr {E,.1 } 2 ø)
45

---

Published as a conference paper at ICLR 2023
El
1 Pr(Esn]
which is equivalent
Pr[Es..] | Pr[Es.]] o Ød.
Recall that 0 < a < 3. For any E [A], (L(panss(ssn. (Sn, a, (lpp)(s,,,)) = (L
7)) S (1-o) S 2r-72 for some constant ei and small enough Let Vs, the number of
times that algorithm visited state Sn. To ensure Pr[Esa] S Φ Φd, need
02 KL (LLiiii (8 ag)l 0y)) log (1 1--1+00 + 66
V
j=1
aA log
4 172
+ dd
a. . 0.6 co
log
61 64
+
for constant C2.
Let cy be small constant such that so < 8. Let w(ss,) denote the probability visiting 8n in episode, and this probability is the same for all policies. Let denote the number of trajectories required by A to be (e, o)-orrett Then, must satisfy
Se*
A 0.062
2
log
4 64c8g2a w(sn)
+ 8
A
8 )
log
E2a w (Sn)
Recall that n H 1. Thus, the constructed instance (Figure 7), we have that w(ss) = a n-1 H-2 and
==-
Eaa a -2 log (1)
A
=Ω
21 (1)
F PROOFS FOR WORST PATH RL
In this section, we provide the proofs regret upper and lower bounds (Theorems and 6) for Worst Path RL.
F.1 PROOFS OF REGRET UPPER BOUND
F.1.1 CONCENTRATION
Recall that for any & 0 and (8, a) E S A, ms,s, a) is the number of times that (s, a) visited before episode k. For any l > O and (8', s, a) E x S x A, let s' before episode k.
denote the number of
times that (s, a) was visited and transitioned
For any policy æ and (s, a) E S x A. let Uz (s, a) and ex (s) denote the probabilities that (s, a) and are visited at least once in an episode under policy n, respectively.
46

---

Published as a conference paper at ICLR 2023
Lemma 18. It holds that
k-1
(SA) 8'
Pr m)(s,a) 2 2
Σ k²=1
U ()) log
Ak > 0, V(s,a) 21-0
Proof of Lemma 18. For any & and (s,a) E S x A, conditioning on the filtration generated by episodes I.... & 1, whether the algorithm visited (s, a) least once in episode & is Bernoulli random variable with success probability (s, a). Then, using Lemma F.4 in (Dann et al., 2017), we can obtain this lemma.
Lemma 19. holds that
SA
Pr
n 8, 2 ny (8, p(s'(s,a)
- 22og 8
4k > 0, s.d.
2 21-8'
Proof of Lemma 19. For any k, h E [H] and (s,a) E 8 A. conditioning on the event { 5. a). the indicator 1 { = ) is Bernoulli random variable with success probability (is'ssa)) Then, using Lemma F.4 in (Dann et al., 2017), we can obtain this lemma.
To summarize, we define some concentration events which will be used in the following proof.
SAA 8'
G1
n)(s,
2
(s, a)
log
4k > O, ((s.a)
2 k==1
SA 8'
C2
na(s',
8,
nM (s, a) 2 log
Vk: 0, V(s', (.
2
9
Lemma 20. Letting 8' 3. it holds that
Pr 9
8.
Proof of Lemma 20. This lemma can be obtained by combining Lemmas 18 and 19.
F.1.2 OVERESTIMATION AND GOOD STAGE
Recall that in Worst Path RL, for any k > 0, E [H] and (s, a) S A, (2(s.a) = r(s,a) +
mingr-p((1s.a) (V (s')) and V (8) = m (s) addition, (8, = r(s,a) +
mingropt (11,,)) (Vk 141 (8') and VK = max.e.4 (s)
Lemma 21 (Overestimation). For any l 0. h [H] and (s, ES A ()(,, (3, and V 2 (s).
Remark. Lemma 21 shows that if the Q-value of some state-action pair accurately estimated, it can only be overestimated (not underestimated), This feature is due to the min metric in the Worst Path RL formulation (Eq. (2)).
Proof of Lemma 21.
We prove this lemma by induction.
For any A > 0 and S, (s) (s) V*)+(() 0.
For any & > 0, h E [M]] and (s, S A. since r(s, a) is known and V/A (s) > V (s) (due to the induction hypothesis), if ş* (-Is,a) a) has detected all successor states, then Q (s, a) > Q Otherwise, if (-1s, a) has not detected all successor states, due to the property of min, we also have (), (s, Q7 (s, a). Therefore, we have ())( 2 V (s). which completes the proof. n
47

---

Published as a conference paper at ICLR 2023
Lemma 22 -onninnce Estimated Value), For any k1, k2 0 such that h S k2 h E [H] and (s,a) E A, Q (s, a) Q 0) and Va (s) V *s).
Proof of Lemma 22. We prove this lemma by induction.
For any 1 hi > 0 such that h S k2 and E S, V (+1(()) = H+1 (8) =0
kka
For any k1, l2 > 0 such that h1 I 12, h E [M] and (s,a) a) E S x A, since r(s, a) is known and h++ (s) 2 k= (s) (due to the induction hypothesis), if ph1 (-Is, a) has detected all successor states, then 2 (s, 2 ²² (s,a). a). Otherwise, p a) has not detected all successor states, due to the min metric and that (+),,)), will detect more (or the same) successor states than f (-|s, a). we also have Q (s, a) 2 2 (s,a), a). Therefore, we have 1 (s) 2 (s), which completes the proof.
Remark, Combining Lemmas 21 and 22, we have that as the episode k increases, the estimated value (s, a) (s)) will decrease to its true value Q7 (s, a) (Vi2 or keep the same.
Let S. {s 8 Un- (s) > 0} denote the set of states which are reachable for an optimal policy.
Lemma 23 (Good Stage). If there exists some episode ie 0 which satisfies that for any h [H] and S., V/ (s) (s) and (s) suggests an optimal action, then we have that for any 2 k
E [H] and s E S.. (s) = (s) and n suggests an optimal action, and thus for any 2 k algorithm MaxWP takes an optimal policy.
Remark. Lemma 23 reveals that if in some episode k for any step h and state S., algorithm MaxWP estimates the V-value accurately and chooses an optimal action, then hereafter, algorithm MaxWP always takes optimal policy.
We say algorithm MaxWP enters a good stage, if starting from some episode k for any k 2 k E [H] and 8 E S.. (s) = (s) and TH (s) suggests an optimal action.
Proof of Lemma 23. Suppose that in episode k, we have that for any h E [H] and s S., v/)
(s) and (s) suggests an optimal action. This is equivalent the statement that in episode k. for any [H] and s E S., for each optimal action a (such that Q (s, a) = (s)), (s,a) Q% a), and for each suboptimal action (such that Q7 a) (s). (7, < (s) < (s).
Using Lemmas and 22, we have that for any h E [H] and s E S., as k increases, (s a) will either decrease to the true value Q?(s, a) or keep the same. Therefore, we have that for any k, h E [H] and E Sz, for each optimal action ( a) = Q7,s, (s, a). and for each suboptimal action Q7 (s, < (f((),) a) < Vi (s), which completes the proof.
F.1.3 PROOF OF THEOREM 4
Proof Theorem 4. Suppose that event G holds.
Let
SA 88 2
T: min Uz(s, a) min p(s'|s, a)
+
(a,0) o: (s,0)>0
s'Esupp( (s,a))
For any (8,a) ESS A, let
SSA
a(
p() .8 $22log
+
min
U (s) min d'suup(p(-le..a)
8
n: (=.a)))
It holds that T ==E\Gaaesxa (s)
48

---

Published as a conference paper at ICLR 2023
According to Lemma 23, in order to prove Theorem 4, it suffices to prove that in episode T 1, for any h [H] and E S., + (s) and n (s) suggests an optimal action, i.e. algorithm MaxWP has entered the good stage in episode T + 1. We prove this statement by contradiction.
Suppose that in episode T + 1, there exists some h E [H] and some E S, which satisfy that +ss) Vg(s) (s) (the value function can only be overestimated) action.
T+1 o (s) suggests suboptimal
If the policy x IT+1 taken in episode T + 1 is optimal, then there exists some h [H], some E S. and some optimal action a which satisfy that ++ (s) > 0 and + a) > Q% (s, a). Otherwise, if the policy π ++ taken in episode T + 1 is suboptimal, then there exists some h E [H], some E S. and some suboptimal action which satisfy that 2yT+1 (s) > 0 and + a) > 27 (s, (s) Hence, no matter which of the above cases happen, we have that there exists some h E [H] and some (s, a) E S x A which satisfy that 1 > 0 and
a) (s,
Under the min metric Worst Path RL, the overestimation Q-value comes from the following reasons: (i) Algorithm MaxWP has not detected the successor state with the lowest V-value. (ii) The V-values of successor states at the next step are overestimated.
If the overestimation of Q7 (s, a) comes from the overestimation of the V-values at the next step (reason (ii)). then we have that at the next step, there exists some state-action pair whose Q-value is overestimated. Then, we can trace the overestimation from (s,a) at step h to some (s', (s') at some step h' 2 h, which satisfies that + (s', a') (s' a') and ( 1s',
(x) 1 (1) for any + (6',cl a²) is purely due to that at (s',a') a'), algorithm
S. In other words, the overestimation of h. MaxWP has not detected the successor state x with the lowest value (Ir).
For any k > 0 and (s, a) E S x A. let (s. = {K' < k (s > 0} denote the set of episodes where (s, a) is reachable before episode k. We consider the following two cases according to whether [TT+I(s (s', a') large enough to detect all successor states of (s', aa).
Case (I): If IT 1/12 T(s', ('',aa) a'), using Lemma 18, we have
SA 8'
n d') 2 Σ
Un a') -log
#=1
1
SSA
2/2
7(''
min
2x (
log
t:
log
p(81(s,a) (A +
SSA 8
log
min
Esupp(a( [s,a))
2 (2g SA +1)
p( 18, (s, [Eeupp(((-ls.a) (s,a))
min
Then, using Lemma 19, we have that for any supp(p(-Is'.a))
(SA)
ne(8,5', a')
2 ne(s',a))
min sEmpptp((1s'..00
p(s]s', aa') 2 log
SA
SA
2 2 log
+1
2 log
8
8
=1
which contradicts that (o', (8', 6''d o')= overestimated.
Case (2): If TT ,a)l < T(s'sa')) a'), we say the overestimation in episode T + 1 due to the insufficient visitation on (6,a'), Then, among episodes 1,..., T, exclude the episodes contained
(s','''))
49

---

Published as a conference paper at ICLR 2023
in (s'''' i.e., we ignore the episodes where (s', (s', ) is reachable and can be the source of the overestimation. Then, the number of excluded episodes due to (s', a') is (TT+ (s', ".ss,a') .a)l < T(s',
According to Lemma 23, since episode T+ 1 has not entered the good stage, for any h S T, episode k has also not entered the good stage. Then, for any k S T, there exists some h E [H] and some s S. which satisfy that (s) > (s) or (s)))) suggests a suboptimal action. This implies that there exists some h E [H] and some (s,a) S x A which satisfy that (8, > 0 and O a) > (s)
Consider the last episode i: among episodes .,.... T which is not excluded. Using the above argu- ment, let (s*, aat) denote the source of overestimation in episode k which satisfies that O (s',a') > (h a') and V (z)
V (x) for any x S. Since we have excluded all the episodes where (s', is reachable among episodes I....,T and episode k is not excluded, holds that (at ab) o (s',a), We repeat the above analysis on 7*(s*, a²). If Case (1) happens, i.e., (sK a²)1 T(skk aa), then we can derive contradiction and complete the proof. If Case (2) happens, i... (T" aa),
T(s* a²), we exclude episode is and the episodes contained in Th (st at)). Then, the number of excluded episodes due to (s a²)) among episodes 1...., T is at most (s* a²)]+ +
(T(s ,a*)).
We repeat the above procedure. Once Case (1) happens, we can derive a contradiction and com- plete the proof. Otherwise, if Case (2) keeps happening, we will exclude the episodes due to the reachability and possible overestimation of (s, a) for all (8,a) E S x A, and the total number of T. Thus, there exists some episode
excluded episodes strictly smaller than E(s.)) T(s,a) kn among episodes ,,..., which satisfies that for any (s, a) E S x A, Uxo (8, a) = 0, which gives contradiction.
F.2 REGRET LOWER BOUND
In the following, we establish a regret lower bound for Worst Path RL and give its proof.
To exclude trivial instance-specifie algorithms and formally state our lower bound, we first define an o( -oonsssitttt algorithm as an algorithm which guarantees an of ()) regret on any instance of Worst Path RL.
Theorem 6. There exists an instance of Worst Path RI., for which the regret of any of () -oonsiittn algorithm is at least
H
max (x.0): Sh, (s)
min U7 Uz($,0) of s'Esupp(p(-la.a))
min
p( (.sssss0)
ue (s,a)>0
where a))) (s)) takes the maximum over all (s, a) such that a is sub-optimal in state s at some step.
The intuition behind this lower bound is follows. For critical but hard-to-reach state 8, any of -))cossisttntt algorithm must explore all actions a in state 8, in order to detect their induced successor states s' and distinguish the optimal action. This process incurs regret dependent on factors min (ia): Ux (s, a) and min, (xupp(((-)ssaa p(s'| |s, a), and hence the lower bound.
Proof of Theorem 6. Consider the instance as shown in Figure
The action space contains two actions, i.e., A = {ar,az}. The state space is S {81, s2...., 8n, I1, I2, 23) where n = S 5 and $1 is the initial state. Let H > S and 0 < a <
The reward functions are as follows. For any A. r()1, = = r(22 0.8 and r(23. 0.2. For any E [n] and a E A, r(s,. = 0.
The transition distributions are follows. For any E A. p(52|31, p(22 (1, a) = a and p(za|s1,00 a) = a. For any E (2..... - 1} and a E A, 0(5,1115;,0 = a and p(z1|s;; a) p(22 1z2 a) = 1 and p(zz F3, a) = 1. The state s, is bandit state, which has an optimal action and suboptimal action. Let a. denote the optimal action in state 8a, which is uniformly drawn from
a, M = 30,
Zı, Z2 and 2z absorbing states, i.e., for any
A. ((11|1111 a) 1,
50

---

Published as a conference paper at ICLR 2023
Reward 0.8
Action a":
Action Asudi
S
Snt
Reward 0.2
1 - a
Action asubi
X3
a
Reward
Figure The instance for lower bound under the min metric (Theorem 6).
{ai, 02), and let asub denote the other sub-optimal action in state For the optimal action P(2g) Sn, a.) 1. For the sub-optimal action suub p(z2 Sn, axub)
and p(zg|Sn asub) a. Fix an o( -conssitttn algorithm A. which guarantees a sub-linear regret on any instance of Worst Path RL. We have that A needs to observe the transition from (8x; 0sub) T3 at least once. Oth- erwise, without any observation of the transition from (8ns aaub) to 23, A can only trivially choose aj or 02 state Sn, and no matter AA chooses a or a2, it will suffer a linear regret the counter instance where the unchosen action is optimal.
Thus, any of K) connsisett algorithm must observe the transition from (sn; Usub) to 3g at least once, and needs at least
U Uruu (Sn, (oub)) p( (8n (aub)
episodes with sub-optimal policies. Here sud denotes policy which chooses asub in state 8n, and Un..o (Sn, arub) denotes the probability that (8n, awub) is visited at least once in an episode under policy saub-
Once the agent takes a sub-optimal policy in an episode, she will suffer regret 0.6(H - n1) in this episode.
Therefore, A needs to suffer at least
Ω
0.6(H m)
Un.no (Sny agub) p(zs/Sns asub)
regret in expectation.
Since in the constructed instance (Figure 8)
1
max (s,a): 3h, a (K)
min (+.0)20
Uz (x, a)
min p()'(s,a) v(8n asws) p(oss ony yous) ('Esup)((()
we have that A needs to suffer least
max (s.o): 7h, (s)
min Ux a) (8.0)200
min ( 18, (ss.pp)((-1s..a)
regret.
G TECHNICAL TOOL
In this section, we present useful technical tool.
51

---

Published as a conference paper at ICLR 2023
Lemma 24 (Lemma 13 in (Ménard et al., 2021)). Ler D, and / be positive scalars such
that 1 < S E and B 2 e. IfT 2 0 satisfies
T T C T (Alog (ST) + B Blog (ST)) + D (Alog (3T) + Elog" (ST)),
then we have
(A+ + (D+2VDC) C) (
where
8 C = log (113 (A+ [C+
52


Reviews:
[{"review_id": "_sflf8Zmgwm", "reviewer": "Reviewer_gBVT", "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 studies the RL problem with a CVAR objective, which concerns the tail of rewards instead of the expectation in standard RL. In the standard setting, the paper proposes two methods. The first method, named ICVaR-RM, focuses on regret minimization, and the paper also provides a matching lower bound. The second method, named ICVaR-BPI, focuses on returning an $\\epsilon$-optimal policy. Finally, when the risk level $\\alpha \\to 0$, where the objective reduces to optimizing the worst-case cumulative reward, the authors propose MaxWP method that enjoys constant regret. ", "summary_of_the_review": "This paper studies the important problem of solving RL tasks with a risk-averse mindset. To this end, the authors propose new methods for solving CVaR RL problem, which performs efficient regret minimization (demonstrated by a matching upper and lower bound). The authors also additionally consider the limiting case, where the task is to optimize the worst-case cumulative reward, and a method with constant regret is proposed.", "strength_and_weaknesses": "Strength:\n1. I first find the technical results to be interesting. Especially the terms that have been singled out by the authors, e.g., the minimal visitation measure (Remark 1 in the paper). The authors have shown that this instance-dependent term not only appears in the regret upper bound, but also in the lower bound, demonstrating the importance of this term in CVaR RL problems.\n\n2. I also appreciate the author's effort in interpreting the result after each main theorem, and the additional highlight in delineating the technical differences between solving the CVaR RL problems and standard RL problems. The proof overview is well-written and easy to follow.\n\nWeakness:\n\nThere is one thing I recommend the authors to consider during revision. Namely, the value function and Q-function are defined in equations (i) and (ii), through recursion. Though I understand this might be concise and technically correct. This approach to some extent hides the true definition of the objective. Namely, how is it that this definition of value function reflects the goal of optimizing the tail? I find it hard to read the risk-averse nature of the problem simply from the DP equations. \n\nMinor Question:\n\n1. Looking into the author's explanation on the constant-regret of Worst Path RL, I was wondering is the technical analysis fundamentally different in the Worst Path RL than the CVaR case (when $\\alpha > 0$)?\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": "W4kFkgc5CR", "reviewer": "Reviewer_U4MP", "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 proposed a new risk-sensitive reinforcement learning formulation, namely iterated CVaR RL. It defines the value as the CVaR of the next step's value function with respect to the randomness in the states' transition. Under this framework, this paper proposes a regret minimization algorithm and a best policy identification algorithm, with regret and sample complexity upper bound respectively. The author also gives a lower bound of regret as well. Finally, this paper also studies the case of CVaR as the risk level $\\alpha$ goes to zero, namely the worst path case, and gives a regret analysis. ", "summary_of_the_review": "This paper gives a new formulation of risk-sensitive RL, iterated CVaR. It's a different definition than most current work, which takes CVaR over the return variable. The analysis in this paper under iterated CVaR is thorough. The main concerns are about the significance of some technical results, and the comparison with the current CVaR MDP.", "strength_and_weaknesses": "Strength:\n1. This paper proposed a new risk-sensitive RL formulation: iterated CVaR RL. Though the idea of iterated CVaR is not new, it is the first use case in RL to my knowledge. This paper gives a novel analysis and an alternative to standard CVaR MDP formulation.\n2. The paper thoroughly discusses the theoretical results of iterated CVaR RL under different settings: risk minimization, the sample complexity of best policy identification, limitation case when \\alpha goes to zero, and a lower bound for each case.\n\nWeakness:\n1. I think it could be better to have more discussion on the pros and cons of iterated CVaR RL with CVaR of return. With the current description in the main paper and comparison in Appendix C, it is not very convincing the iterated CVaR is more suitable for risk-sensitive RL than CVaR MDP. \n - Iterated CVaR takes the alpha CVaR over each transition step. That means in an H-step problem, only the worst $\\alpha^H$ portion of the outcome matter to this quantity. As it decreases exponentially, it's less convincing to me that such a quantity is a good metric to distinguish different algorithms. For a reasonable $H$, $1-\\alpha^H$ portion could be more meaningful even for the risk-sensitive analysis since it could consider more catastrophic returns.\n - Based on the last point, it is more concerning that an action with better performance in the worst $\\alpha^H$ portion could actually have worse performance in the rest (not only for overall performance but even under risk-sensitive metrics). An example could be constructed by considering different CDF curves of the full return.\n2. The term $1/\\min_{\\pi,s, a} w(s, a)$ in Theorem 1 seems meaningless to me. It can be arbitrarily large in an MDP, as long as there exists one state such that it has zero probability to be visited by at least one action. This looks like a very weak condition so please correct me if I'm wrong. Otherwise, the bound only depends on $\\alpha^H$ in almost all MDPs. The lower bound construction verified this, as the $min_{\\pi,s, a} w(s, a) = \\Theta(\\alpha^H) $. If authors want to show that there is a real dependency on $min_{\\pi,s, a} w(s, a)$, it needs to give a construction where $w$ terms can be changed freely without changing $\\alpha$ or $H$. (Like the proof of regret lower bound on $S$ and $H$.)\n\n\nSome minor writing issues and related work:\n - I didn't find a formal definition of $w_{\\pi, h}(s, a)$ in Theorem 1. \n - There exists work on efficient exploration with the CVaR of return (as CVaR MDP) in unknown MDP. E.g. Keramati et al., 2020, Being Optimistic to Be Conservative: Quickly Learning a CVaR Policy. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made 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": {}}, {"review_id": "Q0td0U32nj", "reviewer": "Reviewer_rNfK", "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": "The work studies iterated CVaR RL, and its limiting case worst path RL, as a representative provably efficient risk-sensitive RL problem. Two metrics, namely regret and best policy identification, are proposed and provably efficient algorithms with nearly matching upperbounds are provided. ", "summary_of_the_review": "The paper studies an interesting problem, risk-sensitive RL, and provides comprehensive results. The analyses used to obtain these results feature novel techniques. While some aspects of the proof depend on existing work, to me it does not outweigh the contributions made by the paper.", "strength_and_weaknesses": "Strength\n- The paper studies a setting that is novel and intriguing, offering new insights that are crucial to wider adoption of RL.\n- The results obtained in the paper are comprehensive, covering both the best policy identification setting and the online learning setting.\n- The regret decomposition used to obtain the main results is novel and not found in existing literature. \n\nWeakness\n- Algorithmically the work is not sufficiently novel. The two proposed algorithms bear strong resemblance to their non-risk aware counterparts. Moreover, while the concentration analysis leverages novel decomposition techniques, the lemmas used to prove the results (e.g. Lemma D.1, which shows the concentration behavior of the empirical CVaR estimate) can be found in existing literature. Overall the proof structure still seems to largely follow the optimism principle in provably efficient reinforcement learning. It would be great if the authors could further elaborate on how their analysis is not a combination of existing techniques in RL and existing concentration results from CVaR literature.\n\n------ Post response update --------\n\nI have read the authors' response and my concerns are addressed.", "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": "EMtNsYOOETG", "reviewer": "Reviewer_zHz7", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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 risk-sensitive reinforcement learning. The objective is to maximize the worst $\\alpha$-percent tail of the reward-to-go at each step. This paper designs algorithms for regret minimization and best policy identification problems using the concentration of conditional value at risk. For the regret minimization problem, regret upper and lower bounds are provided; for the best policy identification problem, the sample complexity upper and lower bounds are provided. This paper also studies the limiting case when $\\alpha$ is close to 0, i.e.the worst path RL. ", "summary_of_the_review": "This paper conducts a novel and comprehensive study for CVaR RL. ", "strength_and_weaknesses": "Strength:\n1. The paper studies the CVaR-based MDPs with the unknown transition. \n2. Both upper and lower bounds results are provided.\n3. The usage of concentration of conditional value at risk is interesting.\n\nWeaknesses:\n1. This paper does not use the Bernstein-type exploration bonuses. There could be potential improvements.\n2. The lower bound results do not involve the size of state space, which seems loose.\n\nI acknowledge the authors' response.", "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": {}}]

Author rebuttal:

Decision: Accept: poster