Regret Bounds for Risk-Sensitive Reinforcement Learning
Authors: Osbert Bastani
Yecheng Jason Ma
Estelle Shen
Wanqiao Xu
Venue: NeurIPS 2022 Accept (2022)
Keywords: Risk-sensitive reinforcement learning
CVaR objective

Abstract: In safety-critical applications of reinforcement learning such as healthcare and robotics, it is often desirable to optimize risk-sensitive objectives that account for tail outcomes rather than expected reward. We prove the first regret bounds for reinforcement learning under a general class of risk-sensitive objectives including the popular CVaR objective. Our theory is based on a novel characterization of the CVaR objective as well as a novel optimistic MDP construction.

Regret Bounds for Risk-Sensitive Reinforcement Learning
Osbert Bastani University of Pennsylvania obastani @seas. upenn. edu
Yecheng Jason Ma University of Pennsylvania j jasonymadseas upenn. edu
Estelle Shen University of Pennsylvania Exxa@saasuueenn... pixnaćsas. upenn. edu
Wanqiao Xu Stanford University wangiaox@stanforr edu
Abstract
In safety-critical applications of reinforcement learning such as healthcare and robotics, it is often desirable to optimize risk- objectives that account for tail outcomes rather than expected reward. We prove the first regret bounds for reinforcement learning under a general class of risk-sensitive objectives including the popular CVaR objective. Our theory based on a novel characterization of the CVaR objective well as novel optimistic MDP construction.
Introduction
There has been recent interest in risk-sensitive reinforcement learning, which replaces the usual expected reward objective with one that accounts for variation in possible outcomes. One of the most popular risk-sensitive objectives is the conditional which is the average risk at some tail of the distribution of returns (i.e., cumulative rewards) under a given policy (5] 6). More generally, consider broad class of objectives in the form of weighted integral quantiles of the return distribution, which CVaRR is special case.
(CVRR) objective 2 4)
A key question is providing regret bounds for risk-sensitive reinforcement learning. While there has been some work studying this question, has focused on a specific objective called the entropic risk measure [7 88, leaving open the question of bounds for more general risk-sensitive objectives. There has also been work on optimistic exploration for CVaR [ but without any regret bounds.
We provide the first regret bounds for iisk-sensitive reinforcement learning with objectives of form
(TT) = - (T) (7) -dG(T),
(1)
where ((x) is the random variable encoding the return of policy x, Fz(-) is its quantile function (roughly speaking, the inverse CDF), and G is weighting function over the quantiles. This class captures broad range of useful objectives, and has been studied in prior work [10 4
We focus on the episodic setting, where the agent interacts with the environment, modeled by Markov decision process (MDP), over fixed sequence of episodes. Its goal is to minimize the regret-i.e i.e., the gap between the objective value it achieves compared to the optimal policy, Our approach is based on the upper confidence bound strategy [2], which makes decisions according an optimistic estimate of the MDP. We prove that this algorithm (denoted 21 has regret
regret ( Ô (T LG |8/3/2 3/2 |A|
v VK
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

where T' is the length of single episode. LG is the Lipschitz constant for the weighting function G, [S] is the number states in the MDP, |A| is the number of actions, and K is the number episodes (Theorem 4.1,. Importantl, achieves the optimal rate v K achievable for typical expected return objectives (which is a lower bound in our setting since expected return is an objective in the class we consider, taking G(T) = 7). For CVaR objectives, we have LG 1/a, where a is the size of the tail considered-eet e.g. when is small, it averages
outliers with particularly small return.
The main challenge behind proving our result is bounding the gap between the objective value for the estimated MDP and the true MDP. In particular, even if we have uniform bound || |2 Fz al on the CDFs of the estimated return ((x) and the true return Z we need translate this bound on the corresponding objective values. To do so, we prove that equivalently, we have
= 2T J G(F2c=) dr.
(m))=
This equivalent expression for follows by variable substitution and integration by parts when F2 invertible (so 2(=) ( (7) = i (T)), but the general case requires significantly more care. We show that it holds for an arbitrary CDF Fzi-).
In addition our regret bound, we provide several other useful results for MDPs with risk-sensitive objectives. In particular, optimal policies for risk-sensitive objectives may be non-Markov. For C'aRR objectives. is known that the optimal policy only needs to depend on the cumulative return accrued so far [3].. We prove that this holds in general for objectives of the form (I) (Theorem (.1). Furthermore, the cumulative return so is a continuous component; we prove that discretizing this component yields arbitrarily close approximation of the true MDP (Theorem 3.2).
Related work. To the best of our knowledge, the only prior work on regret bounds for risk sensisvee reinforcement learning is specific to the entropic risk objective 7 8
((r) 3
log Ezo,
where 3 E R250 is a hyperparameter. As 3 - O, this objective recovers the expected return objective; for 3 < 0, it encourages risk aversion by upweighting negative returns; and for 3 > 0, it encourages risk seeking behaviors by upweighting positive returns. This objective is amenable theoretical analysis since the value function satisfies a variant of the Bellman equation called the exponential Bellman equation; however, it a narrow family of risk measures and is not widely used in practice.
In contrast, we focus on a much broader class of risk measures including the popular CVaR objec- tive [. which is used to minimize tail losses. To the best of our knowledge, we provide the first regret bounds for the CVaR objective and for the wide range of objectives given by (T..
Problem Formulation
Markov decision process. We consider Markov decision process (MDP) M (,P.P.
with finite state space S, finite action space A, initial state distribution (ss), finite time horizon T, transition probabilities P(s') s, s, and reward measure PR(a,j;; without loss of generality, assume E [0. I] with probability one. A history is sequence
g 2 = U Z t=1
where
= A S
Intuitively, history captures the interaction between an agent and M up to step We consider stochastic, time-varying, history- depeede- policies n, (ax (t). where is the time step. Given æ, the history = generated by a up to step t is a random variable with probability measure
P (G)) = ((1))
ift=1
s/ (E--1) ma(a, I E--) P Pr(saaa P(s st. az) otherwise,
where for all 7 E [T] we use the notation
& ((51, a,, (1.

---

Finally, an episode (or rollout) is a history & E 2x of length T generated by given policy x. Bellman equation. The return of π step t is the random variable (Z.) Σi Tt. where čr ~ Pp Pap | = - it is the reward from step t given that the current history is &t- Defining 2 (5, 8) = the distributional Bellman equation
94
F 22-0 (6) (1) (1) Σ Te(a (a 5) 1(d((S())))) S F 22 (Eo(ano)))) -) ((),)(())
aEA
S'E8
where S(5) 8 for { (...,s) 8) is the current state in history ç, and Fx the cumulative distribution function (CDF) of random variable X. Finally, the cumulative return of π is Z(7) (E,) where
Ç (s) E 2, for s D is the initial history; in particular, have
Fz (x) = F (D)))
dD(s).
Risk-sensitive objective. The quantile function of a random variable X is (T) inf {a R (x(x)) r)
Note that if Fx strictly monotone, then is invertible and we have Fx) 100==xx10 (T). Now, our objective is given by the Riemann-Stieljer integral
S. F (r)
& (M)
where G(T) is given CDF over quantiles 7 E [0. 1]. This objective was originally studied in [5] for the reinforcement learning setting. For example, choosing G(T) min(T/a, 1} (i.e.. the CDF of the distribution Uniform (0, al)) for a E [0, yields the a-conditional value at risk (CVaR) objective; furthermore, taking addition, choosing G(T) = ( S a) for a E [0. 1] yields the a value at risk (VaR) objective. Other
yields the usual expected cumulative reward objective. In
risk sensitive-objectives can also be captured in this form, for example the Wang measure [16), and the cumulative probability weighting (CPW) metric [1]. We call any policy
TM E arg max (M)
an optimal policy- i.e., maximizes the given objective for M.
Assumptions. First, we have the following assumption on the quantile function for Z(m); Assumption 2.1. Ft x (1) T.
Since T is the maximum reward attainable in episode, this assumption says that the maximum reward is attained with some nontrivial probability. This assumption is very minor; for any given MDP M, we can modify M include path achieving reward I with arbitrarily low probability. Assumption 2.2. G Li-Liscciit continuous for some LG E Ryo, and G(0) = 0.
For example, for the o-C objective, we have LG = 1/a.
Assumption 2.3. We are given an algorithm for computing TM for a given MDP M.
For CVaR objectives, existing algorithms 1 can compute J' with any desired approximation error. For completeness, we give formal description of the procedure in Appendix D When unambiguous,
drop the dependence on M and simply write ..
Finally, our goal is learn while interacting with the MDP M across a fixed number of episodes K.
In particular, the beginning of each episode & [K]. our algorithm chooses a policy (*)) 2 (HH)). where H₂ = {Er.. )==1 is the random set of episodes observed so far, use for the duration of episode k. Then, our goal is to design an algorithm 21 that aims to minimize regret, which measures the expected sub-optimality with respect n²:
regret (2l)
E
Σ x(TT)) (b)((a) [E[K]
Finally, for simplicity, we assume that the initial state distribution known; in practice, we can remove this assumption using standard strategy.
3

---

3 Optimal Risk-Sensitive Policies
In this section, we characterize properties of the optimal risk-sensitive policy T.. First, we show that it suffices to consider policies dependent on the current state and the cumulative rewards obtained far, rather than the entire history. Second, the cumulative reward is continuous quantity, making it difficult to compute the optimal policy; we prove that discretizing this component does not significantly reduce the objective value. For CVaR objectives, these results imply that existing algorithms can be used to compute the optimal risk-sensitive policy [13].
Augmented state space. We show there exists optimal policy के (ax yt, 8t) that only depends on the current state 8t and cumulative reward y/ ((Ee) E 7+ obtained so far. To this end, let Zi s) = {E E Z, J(G) S y A St s}
be the set of length t histories & with cumulative reward at most so far, and current state s. For any history-depender policy x. define the alternative policy by
(a & E E
(e( ) - e (JE
Note that only depends on &, through yr (Et) and 8r, we can define (, Ex) #t(( y/. 8t). Theorem 3.1. For any policy we have ( (T).
We give a proof in Appendix A In particular, given any optimal policy x we have ((#*)= o(x*)) thus, we have ** E arg max, ((T). Finally, we note that this result has already been shown for CVaR objectives [3] our theorem generalizes the existing result to any risk sensiivne objective that can be expressed as weighted integral of the quantile function.
Augmented MDP. As a consequence of Theorem 3.1 it suffices to consider the augmented MDP M = (8, A, D, P, P, T). First, S = S IR is the augmented state space; for state (s, S, the first component encodes the current state and the second encodes the cumulative rewards so far. The initial state distribution is a probability measure
D((5, v)) = D(s) 6z())
where dg the Dirac delta measure placing all probability mass on y (i.e., the cumulative reward so far is initially zero). The transitions are given by the product measure
P((s', v/) (s, v). a) = P(s' s, s,a) PR(s.a) - y),
i... the second component of the state space is incremented as y' y + r, where is the reward achieved in the original MDP. Finally, the rewards are now only provided on the final step:
(r) ift=
P PRi((es)) (T) {0
otherwise,
i.e,, the reward the end of a rollout is simply the cumulative reward far, encoded by the second component of the state. By Theorem 3.1 it suffices compute the optimal policy for M over history-independent policies <1 8c):
max + (T) max (MT,,,
Elllas
where Tina is the set of history-indepe iidepry-indepeedent policies. Once we have "ie use it in M by defining <M((a { s) "nn(( (a s).
Discretized augmented MDP. Planning over M is complicated by the fact that the second compo- nent of its state space is continuous. Thus, we consider an dddierretization of M, for some E Ryo- To this end, we modify the reward function so that it only produces rewards in - N {n-n n n e N). by always rounding the reward up. Then, sums of these rewards are contained in ') N, so we can replace the second component of Š with 1) N. In particular, we consider the discretized MDP M = A, D. P, T), where S = S (n N), and transition probability measure P((s', v/) (s, v). = P(s' s. s,a) R(sa) o "0' v)

---

want to consider where ((r) 17- [r/n]. That is, Pr(s.a) is replaced with the pushforward measure IP R((s,a) o Φ which gives reward r7 i with probability Pn(s,a) (17 (i- < S 17 i].
Now, prove that the optimal policy "M for the discretized augmented MDP M achieves objective value close to the optimal policy TM for the original MDP M. Importantly, measure performance of both policies based on the objective & M of the original MDP M. To do so, need way to use J in M.. Note that " depends only on the state & = (s. y), where E S is state of the original MDP M, and y 17 NN is discretized version of the cumulative reward obtained so far. Thus, we can run क .M in M by simply rounding the reward ra at each step up to the nearest value ft E 17 N at each step i.e., Å o(ri): then, we increment the internal state as Yt = yt-1 + fr. We call the resulting policy ти the version of क adapted M. Then, our next result says that the performance of T not too much worse than the performance of JM
Theorem 3.2. Let Th be the optimal policy for the discretized augmented MDP M, let TM be the policy Hh adapted to the original MDP M, and let x I' be the optimal for the original MDP M. Then, we have
policy
(M((M) 2 MM((TM) -1
We give a proof Appendix B Note that we can set rj to be sufficiently small achieve any desired error level (i.e., choose e/T, where is the desired error). The only cost is in computation time. Note that the number of states in M is still infinite; however, since the cumulative return satisfies E [0, HJ. it suffices to take $ = S x (e ([H/u]]); then, M has |S| [H/v] states.
Upper Confidence Bound Algorithm
Here, we present upper confidence bound (UCB) algorithm (summarized in Algorithm I At high level, for each episode, our algorithm constructs estimate M of the underlying MDP M based on the prior episodes i E l 1]: to ensure exploration, it optimistically inflates the estimate of the reward probability measure IP. Then, plans in (R to obtain an optimistic policy π (k) x Mo) and uses this policy to act in the MDP for episode k.
Optimistic MDP. We define ( Without loss of generality, we assume S includes a distinguished
state 8o with rewards FRis....)) (r) 1(r 2 1) (i.e., achieve the maximum reward 1 with probability onc), and transitions P(sxx s, s,a) = 1(s sx0) and P(s' sxx, a) 1(s' 5o0) (i.e., inaccessible from other states and only transitions itself). Our construction of Mn(k) uses 8:0 for optimism. Now, let M(kk) be the MDP using the empirical estimates of the transitions and rewards:
as,
(()) ss,a)
N8,(8,,))
k-1 ΣΣ 1(rssnd (8i. = s A Sa, = a).
FROM) (F)
(N.e(s, a)
Then, let (k) be the optimistic MDP; in particular, its transitions
1(s' 3o0)
if 900
(() (s,a) Evesy(ew ((0) (s,0) max (())( 8 a) - e (4) (s, o}
if 8' 800 otherwise
transition to the optimistic state 8o0 when uncertain, and its rewards
1)
if 80c if otherwise
(e (r)
1
('RR (r) (k) (s, 0f
max
optimistically shift the reward CDF downwards. Here, (+) (s, a) and e (s, a) are defined in Section 5 intuitively, they are high-probabilityy upper bounds the errors of the empirical estimates
p. a) and F (s.) of the transitions and rewards, respectively.
5

---

Algorithm Upper Confidence Bound Algorithm
1: for k [K] do
2: Compute (M and (A)) "M "MM(i)) using prior episodes (5(0) i E [k: 1}}
3: Execute ((k) the true MDP M and observe episode g(A) [skk,e Ok . 1k, U [s,
4: end for
Theoretical guarantees. We have the following upper bound on the regret of Algorithm |
Theorem 4.1. Denote Algorithm 1 by 21. For any 5 E (0, 1], with probability at least 1 - 8, we have
4|8
|AI K
5|S| |A| K log regret(2)) S 4//3/2. LG 16.11)-
Ö(VK).
We briefly compare our bound to existing ones in the setting of expected return objectives. The dependence the number of episodes K matches existing bounds [1] since this is optimal in the setting of expected return, and expected return is a special case of our setting (with G(T) = r), bound is also optimal in K. In terms of the dependence on the number of states |8|, our bound has an extra / S| factor compared to the UCRL2 algorithm [TI, and an extra [S] factor compared to the improved bound of the UCBVI algorithm [12]. One extra VIS comes from down-shifting transitions uniformly in the construction of the optimistic MDP (1)) This V[Si may be removed by more careful construction of the optimistic MDP. Another extra v S] compared to UCBVI comes from bounding the estimation eπrоr of the reward distribution. We believe it may be possible to remove this vISl through more careful treatment of the estimation error, similar to the one in UCBVI. We leave both of these potential refinements to future work.
In terms of the dependence the number of actions [A], our bound matches the order of V in both UCRL2 and UCBVI. Our dependence on the horizon length T T3/2, compared to the same order of 73/2 in UCBVI and T in a variant of UCBVI [22 utilizing carefully designed variance-based bonus.
5 Proof of Theorem 4.1
We prove Theorem 4.1 we defer proofs of several lemmas to Appendix C
At a high level, the proof proceeds in three steps. First, we prove our key Lemma 5.1 which expresses the objective & in terms of an integral of the weighted CDF of the return. This lemma allows us to translate bounds on the difference between CDFs of the estimated return (() and the true return ((²) into bounds the difference between corresponding objective values. The proof of this lemma
divided into three parts that deal with different sets of points in the domain of the quantile function F : (i) discontinuous; (ii) continuous and strictly monotone; (iii) continuous and non-strictly monotone. This result is used throughout the remainder of the proof.
Second, we define & to be the event where the optimistic estimated MDP (i(1) falls into a certain confidence set around the true MDP M for each & [K]: in Lemma 5.2 we prove that holds with high probability. Then, Lemma 5.6 we prove that under event E, the objective values (Q((s) and M are close. To prove this lemma, we separately show that (i) the objective values of the estimated MDP (M( (estimated without optimism) and M are close (Lemma 5.4). and (ii) the objective values of (k) and (M(k) are close (Lemma 5.5
Third, in Lemma 5.7 we prove that under event E, the MDP ( is indeed optimistic. Together, these results imply the regret bound using the standard UCB proof strategy.
We proceed with the proof. First, we have our key result providing an equivalent expression for 4: Lemma 5.1. We have
((^)= = T G(Fz)o (x)) dx.

---

Proof. First, note that by integration by parts, we have
((T)) S (T)) (t) GG) - S.' G(T) dF (T)
= [- G(T) dF (T),
where the last line follows by Assumptions 2.1 & 2.2 Thus, suffices to show that
J. G(T)- dFt
/ G(Fz(>)(z)) dr.
(r) 20m
The quantile function F is monotonically increasing and left-continuous [8]. so this integral is
equivalently Lebesgue-Stieltjee integral [9] Dividing the unit interval 7 = [0, 1] into disjoint sets
( = {r I
Ft 26) (T) is discontinuous}
[ {r 1
Ft 2mm (T) is continuous and strictly monotone)
((0) = [T E I
Fl 200 (T) is continuous and non-strictly monotone),
then we have
S G(T) dft (T) f G(T) dFt (T) + f G(T) dFt ( (T) S G(T) dFt ( (T).
We consider each of the three terms separately and then combine them to finish the proof.
First term. Note that (2) = {T: (1) ) is countable since monotone functions can have countably
many discontinuities. Also, for each E N, the measure assigned to Ti (1) by dFt 26x
dFF Z (1T/ 2
lim +
(2) (T) - (T: (1) = (1) xx xx
Thus, we have
00+
f G(T) -dF) zin)
(7) (7) Σ
G(T: (1) (1)+ - -x (11)))
(z)
Σ
G(T,"))
dx
10)
a(
m=l
(1)
G(F2()) dr s
G(F2(n dr
F-1
(t))))
f F-1 (10)
G(Fzcn(z)) dr.
On the second line, we have used the fact that F2 (x) (x) 7. for all x E {x 24 .x (1)+), To see this
fact, note that since x 2 x. (1) by monotonicity of Fz have Ezin (x) 2 Fzio (x( T. (1)
Furthermore, if F2 (x) > (1) then we would have
[1)+ lim (T) lim inf(x' E R Fz 2 7} 2 +++
T-
< inf E IR Fzw)(z)) 2 Fzw)(1)
x,
where the first inequality follows since Pz6 (x) 2 for t sufficiently close 7, (1) and the second since
{x E
R Fz (x') 2 (x)). Since have assumed x x (1)+ have
7

---

contradiction, F2(+) (2)) S T. Thus, it follows that F2c:: (x) (1) as claimed. The third line follows since
7 (T(0)) = [ag 24
(1) )
or 7z (1T, (T/ (1) . 1.
In particular, for any F (T())))) we have F2 (r) Ti so
inf E R Fzo (x) 2 74 ) = =x (1)
Conversely, we have
0+ lim -
F (T)
= lim inf E Pzi (x') 2 2 2x
T 0+
since Fzim (x²) S i < for all x' S x so the infimum must be 2 x. These two arguments show
(1)
that F (z (1) }) S [a. ()) x (1+ The fact that [x]") " ((++)) C f ((T,"))) follows by the same line follows since the sets
argument as for the second line. The claim follows. Finally, the
Fzl, (1T, }) are disjoint.
Second term. For any T E 7(2), then F exists at т, and we have F Fixm (T) Fzim) (T). Thus, by substitution Fz (I), we have
J G(T) dFt 2G 26) (T)
Jrn G(F2(=((x) dx.
p- (
Third term. We can divide (3) into union of disjoint intervals ((3) = U (00) where
()) {r E [0, 1] (T) = 2! (8))
for some zi rational number). Then, we have
R: there are only be countably many such intervals (since each one contains distinet
J G(T)
dFl 2(0 (T) = -
G(F2())))) dr,
F (131)
since (
(3) f li has measure zero according the Lebesgue measure dr.
Final proof. Finally, note that ((()) Fzzz (1(2)), and Fzzz (1(3)) cover l2 and are disjoint except possibly on a set of measure zero, so
S Sastitao ((F)())(z)) dr S (121))
G(Fzim dx f
(100) G(Fz()) dx
= = -[((P2(())) dr.
The claim follows.
Next, given 8 Ryo, define to be the event where the following hold:
2|S]
[|S] [A]
[1000 s, - P(-1,,))ll <
log
= (s (
(V( (s,a)) a)
6
(Ffi)))s.)) FR(s. 5
log
G)S] [A]
K
ER (s.a) (YsE
(k)
V (M)
8
[150))( (s,a) (sa)) 13-P(
16.1/,,))ll> (H)
1
log
6|S]
[A| K
En (s,a) (
8
Lemma 5.2. We have PIE| ())
> 1 8.

---

Next, let =),:=) and (k.,a) be the returns for policy π for (( and M respectively. let $b = чM- ((H) Tb Man, and (b() = + Mi()), and let x¹ iM ((k) (Qun> and (*() " "Mae Now, we prove two key results: (i) (()) is close to D, and (ii) (b))) is optimistic compared to 2. To this end, we have the following key lemma; its proof depends critically on Lemma [.11
Lemma 5.3. Consider MDPs M (S,A, D, P.P.T) and M' (S, D, D PI,, TT, such that [| 8, - P(. 8,a) (p(s, a) and ( FR(sa) |o I cn(s, a). Then, we have
0 (T) - (T)) - T LG B(T)
(Vk E [),,
where
T
cp(st, 0z) + cn((s, 00) Σ
B(T) = Engr
Our next lemma characterizes the connection between (()) and
Lemma 5.4. On event and conditioned on (N(() (s, a) ()) we have
( (()) T LG (T)
(Ak E [K],T),
where
T
Proof. The result follows since on event and conditioned on (5) and M satisfy the conditions of Lemma 5.3 for all k E [K].
(Bb) (T) =
Engom By
Σ
(8) (8t, az) + en (8,, ax) p
M()
Our next lemma characterizes the connection between ((k) and (1))
Lemma 5.5. For each k E [K] and any policy we have
(b<h)) - (TT)) < T La VISI (T).
Proof. The result follows since by definition of M(k), M and M satisfy the condition of
Lemma 5.3 with Ep(s, a) = 2|S] (k) (s. a) S v Ep (s,a) and en(s,a) = En (s, a) for all
(k)
[K]
Now, we prove the first key claim -.e. (k) is close to +. Lemma 5.6. On event E, for all k: E [K] and any policy n, we have
(T)))(T) - ((T)) S 2T La VISI (T).
Proof. Note that
(1)) (()) < (T) - (10 + (+( D(T) 2T Lo vIs (T)
where the second inequality follows by Lemmas 5.4 5.5
Now, we prove the second key claim i.e. (k) is optimistic compared to 4.
Lemma 5.7. On event ε, we have $ (k) (T) 2 (T) for all k E [K] and all policies m.
With these two key claims, the proof of Theorem follows by a standard upper confidence bound argument; we give the proof in Appendix C.4

---

100
Our Apontten
k/th a/2t
UCfi respected
Gready Exploatton
10
70-
0
09
382
80
102
Roloodes
Roloodes
Figure 1: Results the frozen lake environment. Left: Regret of our algorithm UCBVI (with expected return) and a greedy exploration strategy. Right: Regret our algorithm across different a values. We show mean and standard deviation across five random seeds.
Experiments
We consider classic frozen lake problem with finite horizon. The agent moves block next its current state at each timestep and has a slipping probability of 0.1 its moving direction the next state is ice block. The objective is to maximize the cumulative reward without falling into holes. The agent needs to choose among paths which correspond to different levels of risk and rewards. In other words, the agent should account for the tradeoff between the cumulative reward and risk of slipping into holes. We use a map with four paths the same lengths that have different rewards at the end and different levels of risk of falling into holes. We consider which correspond to optimal policies of choosing paths with best possible returns of {6, 4, 2, 1 and success probabilities of {0.729, 0.81, 0.9, 1). respectively (failure corresponds zero return).
{0,40, 0.33, 0.25, 0.01},
Figure D (left) shows the comparison in cumulative regret between our algorithm, UCBVI (which maximizes expected returns, not risk-sensitive objective), and the algorithm that optimizes risk-sensitive objective but explores a greedy way (i.e., use the best policy for the current estimated MDP without any optimism), for 0.33. The regret is measured in terms of the CVaR objective with respect to the optimal policy for the same CVaR objective. While UCBVI outperforms greedy, neither of them converge; in contrast, algorithm converges within 40 episodes.
Figure (right) compares the regret between our algorithm under different values of a using the CVaR objective. Note that smaller values of tend to lead our algorithm to converge more slowly; this result matches our theory since smaller a corresponds to larger LG. Intuitively, more samples needed to get good estimate of the objective becomes small since the CVaR objective is the average return over a tiny fraction of samples, causing high variance in our estimate of the objective.
7 Conclusion
We have proposed novel regret bound for risk sensitive reinforcement learning that applies broad class of objective functions, including the popular conditional value-at-risk (CVaR) objective. Our results recover the usual vK dependence on the number of episodes, and also highlights dependence on the Lipschitz constant Le of the integral of the weighting function G used define the objective. Future work includes extending these ideas to the setting of function approximation and understanding whether alternative exploration strategies such as Thompson sampling are applicable.
Acknowledgments and Disclosure of Funding
This work is funded in part by NSF Award 191-199 NSF Award CCF-1917852, and ARO Award W91 1NF-20-1--000 The U.S. Government authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
10

---

References
[1] Tyrrell Rockafellar and Stanislav Uryasev. Conditional value-at-risk for general loss distribu- tions. Journal of banking & finance, 26(7):1443-1471, 2002.
[2] Yichuan Charlie Tang, Jian Zhang. and Ruslan Salakhutdinov. Worst cases policy gradients. arXiv preprint arXiv: Eet.e9111.0.0 0.06618,, 2019.
[3] Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone. Risk-constrained reinforcement learning with percentile risk criteria. The Journal of Machine Learning Research, 18(1):6070-6120, 2017.
[4] Yecheng Ma, Dinesh Jayaraman, and Osbert Bastani. Conservative offline distributional reinforcement learning. Advances in Neural Information Processing Systems, 34, 2021.
[5] Aviv Tamar, Yonatan Glassner, and Shie Mannor. Optimizing the cvar via sampling. In Twenty-Ninth AAAI Conference Artificial Intelligence, 2015.
[6] Yinlam Chow and Mohammad Ghavamzadeh. Algorithms for evar optimization in mdps. Advances neural information processing systems, 27, 2014.
[7] Yingjie Fei, Zhuoran Yang, Yudong Chen, and Zhaoran Wang. Exponential bellman equation and improved regret bounds for risk-sensitive reinforcement learning. Advances in Neural Information Processing Systems, 34, 2021.
[8] Yingjie Fei, Zhuoran Yang, and Zhaoran Wang. Risk-sensitive reinforcement learning with function approximation: A debiasing approach. In International Conference on Machine Learning, pages 3198-3207. PMLR, 2021.
[9] Ramtin Keramati, Christoph Dann, Alex Tamkin, and Emma Brunskill. Being optimistic to be conservative: Quickly learning a ovar policy. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34 no. 04, pages 4436-4443, 2020.
[10] Will Dabney, Mark Rowland, Mare Bellemare, and Rémi Munos. Distributional reinforce- ment learning with quantile regression. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32 no. 01, 2018.
[11] Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008
[12] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272. PMLR, 2017.
[13] Nicole Bäuerle and Jonathan Ott. Markov decision processes with average-valuu-attrisk criteria. Mathematical Methods of Operations Research, 74(3):361-379, 2011.
[14] Mare G Bellemare, Will Dabney, and Rémi Munos. distributional perspective on reinforce- ment learning. In International Conference Machine Learning, pages 449-458 PMLR, 2017.
[15] Will Dabney, Georg Ostrovski, David Silver, and Rémi Munos. Implicit quantile networks for distributional reinforcement learning. In International conference machine learning, pages 1096-1105. PMLR, 2018
[16] Shaun S Wang. A class of distortion operators for pricing financial and insurance risks. Journal of risk and insurance, pages 15-36, 2000.
[17] Amos Tversky and Daniel Kahneman. Advances in prospect theory: Cumulative representation of uncertainty. Journal of Risk and uncertainty, 5(4):297-323, 1992.
[18] Paul Embrechts and Marius Hofert. A note on generalized inverses. Mathematical Methods of Operations Research, 77(3):423 432, 2013.
[19] Elias M Stein and Rami Shakarchi. Real analysis. In Real Analysis. Princeton University Press, 2009.


Reviews:
[{"review_id": "jsHHP-WbE0h", "reviewer": "Reviewer_bBTj", "summary": "This paper proposes an exploration learning algorithm for risk-sensitive reinforcement learning algorithm with provable guarantees on its performance using the metric of regret. ", "questions": "Please see \"Weaknesses' above. ", "limitations": "Limitations are specified in the form of the assumptions. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n1. This paper presents a general approach for addressing the risk-sensitive reinforcement learning problems and use this approach to get provable regret guarantees. In particular, the paper considers the general formulation given Eq. (1). One of the most popular risk-sensitive criteria CVaR will become a special case of this formulation. \n\n2. According to this reviewer, the key contribution of this paper is the result given in Lemma 5.1. Risk-sensitive RL is difficult mainly because of the complicated form of the objective function. Lemma 5.1 converts this to a clearly tractably form, which can be used to bound the difference in the objective function due to two policies by the difference in quantile functions of the cumulative rewards induced by those policies. This result is possibly useful in many other research problems, including in the analysis of policy gradient algorithms. \n\n3. The paper also presents a new style of UCB algorithm which is different from the standard optimism in the face of uncertainty (OFU) algorithm. Most of the standard algorithms finds an optimistic model by searching within a ball around the empirical estimate of the model in such a way to maximize the objective. This paper seems to be directly selecting a model by subtracting a penalty term (corresponding to the visitation counts) from the estimated model. This will reduce the computational complexity compared to the standard OFU algorithm which requires approaches such as extended value iteration. \n\n\n\nWeaknesses:\n\n1. Proofs are rather compressed. Please provide intuitive explanation general proof ideas. Also, please provide explanation for the intermediate steps. \n2. The motivation for using a different style of UCB approach is not clear. Is this approach used in prior works? What are the advantages or disadvantages of this approach? \n3. The computational feasibility of the proposed generalized form is not clear. Even for the CVaR setting, how is the oracle policy computed? For general setting, is there a standard algorithm? \n4. This reviewer acknowledges that this is a theoretical paper. However, given that it proposes a new algorithm, and deals only with tabular setting, it is important to include the experimental results which demonstrate the performance of the algorithm.  \n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RJ9j8OIlRsS", "reviewer": "Reviewer_yvdY", "summary": "The paper studies the problem of risk-sensitive RL, and prove regret bound under a class of risk-sensitive objectives, including CVaR. The results build on a novel CVaR objective and optimistic MDP. ", "questions": "- It would be nice to provide some explanations to explicitly connect the formulation here with existing settings. \n- Also, while def. (1) appears to be more general, it would still help if the paper can discuss how it generalizes existing objectives. \n- The reviewer would suggest adding a thorough comparison with existing works. In particular, how are the dependence on different parameters compared to existing results? The paper only mentions the dependence on K. \n- The algorithmic aspect of the paper does not appear significant. In particular, the main results in the paper focus on showing equivalence or transformation. The proposed algorithm 1 does not appear to be novel (although this has nothing to do with its performance). The authors could perhaps better highlight the novelty of the results. \n", "limitations": "- The algorithmic part of the paper does not appear strong. \n- A better comparison with recent results would be helpful. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The problem of risk-sensitive RL is interesting and important. \n\nWeaknesses\n- The algorithmic part of the paper does not appear strong. \n- A better comparison with recent results would be helpful. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Hn5_n_IwR5Z", "reviewer": "Reviewer_TTmD", "summary": "This paper presented a novel regret bound analysis for risk-sensitive reinforcement learning. The analysis is based on an optimistic MDP formulation. The regret bound could be applied to more general problem formulations compared to existing regret bound analyses. Overall, I am not quite familiar with the related work of regret bounds of the risk-sensitive RL, and the authors also did not explain too much about related works in the main paper. Therefore, I am not sure if the claim of the first regret bound is right. However, the results are reasonable on CVaR problem formulation and seem plausible. Therefore, I have a positive impression of this paper. I also suggest that the author could explain more about related work (even though there might not be many) to help better understand this paper.", "questions": "1. It seems that the results rely heavily on the Lipschitz constant $L_G$. What if the $L_G$ is not Lipschitz?\n2. Are there any other requirements of the MDP, such as stationary or non-stationary?", "limitations": "The author adequately addressed the limitations and there is no potential social impact of this work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\nThe paper gave a thorough analysis of regret bound of risk-sensitive reinforcement learning. The notions are clear and the authors also explained many intuitions behind the proof.\n\nWeakness:\nThe claim of the first regret bound might be too strong, and the logic of the whole paper could be further improved (e.g., there are many lemmas placed at the end that makes me confused initially. )", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "65X0TOd6e0k", "reviewer": "Reviewer_wVQ7", "summary": "\nThis paper describes an optimistic algorithm for a general class of Risk-Sensitive RL, where the quantiles of the return distribution are weighted according to a function G.\nThe paper proves a regret-bound linear with respect to Lipschitz constant $L_G$ of the weight function.", "questions": "\n- Between lines 113 and 114 should the left hand side of the equation be $\\max_{\\pi \\in \\Pi_{\\text{Ind}}}\\Phi_{\\mathcal{\\tilde{M}}}(\\pi)$?\n- In the right-hand side of the bottom equation after line 193, should it be $\\epsilon_{R}^{(k)}$?", "limitations": "\nThe paper clearly states the assumptions necessary to achieve the regret bounds claimed.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n### Strenghts\n\n- The paper provides a novel analysis of a general class of Risk-sensitive RL problems.\n- The paper is well written and well structured. The main results are proved in the main document and only the support material is left in the appendix.\n- Overall, the paper provides an excellent presentation of the problem and the derivations.\n\n### Weaknesses\n\n- The motivation to study this general class of problems could be expanded to clarify further the significance of the proposed approach.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept