Exponential Bellman Equation and Improved Regret Bounds for Risk-Sensitive Reinforcement Learning
Authors: Yingjie Fei
Zhuoran Yang
Yudong Chen
Zhaoran Wang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Reinforcement learning
risk-sensitive reinforcement learning

Abstract: We study risk-sensitive reinforcement learning (RL) based on the entropic risk measure. Although existing works have established non-asymptotic regret guarantees for this problem, they leave open an exponential gap between the upper and lower bounds. We identify the deficiencies in existing algorithms and their analysis that result in such a gap. To remedy these deficiencies, we investigate a simple transformation of the risk-sensitive Bellman equations, which we call the exponential Bellman equation. The exponential Bellman equation inspires us to develop a novel analysis of Bellman backup procedures in risk-sensitive RL algorithms, and further motivates the design of a novel exploration mechanism. We show that these analytic and algorithmic innovations together lead to improved regret upper bounds over existing ones.

Exponential Bellman Equation and Improved Regret Bounds for Risk-Sensitive Reinforcement Learning
Yingjie Feil
Zhuoran Yang² Yudong Chen Zhaoran Wang
Northwestern University; yf275@cornel1. edu, zhaoranvang@gmail.
Princeton University; zyéāprinceton.cm edu
University of Wisconsin-Madison, yudong chen@wisc.edu
Abstract
We study risk-sensitive reinforcement learning (RL) based the entropic risk measure. Although existing works have established non-asymptotic regret guar- antees for this problem, they leave open an exponential gap between the upper and lower bounds. We identify the deficiencies in existing algorithms and their analysis that result in such a gap. To remedy these deficiencies, we investigate a simple transformation of the risk-sensitive Bellman equations, which we call the exponential Bellman equation. The exponential Bellman equation inspires us to develop novel analysis of Bellman backup procedures in risk-sensitive RI. algorithms, and further motivates the design of a novel exploration mechanism. We show that these analytic and algorithmic innovations together lead to improved regret upper bounds over existing ones.
Introduction
Risk-sensitive reinforcement learning (RL) is important for practical and high-stake applications, such self-driving and robotie surgery. In contrast with standard and risk- RL, it optimizes some risk measure cumulative rewards instead of their expectation. One foundational framework for risk-sensitive RL maximizes the entropic risk measure of the reward, which takes the form of
V log (e 1)
3
with respect to the policy n, where 3 + 0 is given risk parameter and R denotes the cumulative rewards.
Recently, the works of 220 21 investigate the online setting of the above risk-sensitive RL problem. Under K-episode MDPs with horizon length of H, they propose two model-free algorithms, namely RSVI and RSQ, and prove that their algorithms achieve the regret upper bound (with its informal form given by)
Regret(K) S 2
V (H) K
without assuming knowledge of the transition distribution access simulator. They also provide a lower bound (informally presented as)
eld) H'
Regret(K) K) Z
Vpoly(H) K
B
that any algorithm has to incur, where H' is a linear function of H. Despite the aon-ssympiotic nature their results, not hard to see that wide gap exists between the two bounds. Specifically,
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

the upper bound has an additional ela) factor compared to the lower bound, and even worse, this factor is dominating in the upper bound since the quadratic exponent in el@) makes it exponentially larger than 2 1a even for moderate values of [3] and H. It is unclear whether the factor of e!
is intrinsic in the upper bound.
In this paper, we show that the additional factor in the upper bound is not intrinsic for the upper bound and can be eliminated by a refined algorithmic design and analysis. We identify two deficiencies in the existing algorithms and their analysis: (1) the main element of the analysis follows existing analysis of risk-neutral RL algorithms, which fails to exploit the special structure of the Bellman equations of risk-sensitive RL; (2) the existing algorithms use excessively large bonus that results in the exponential blow-up in the regret upper bound.
To address the above shortcomings, we consider a simple transformation of the Bellman equations analyzed so far in the literature, which we call the exponential Bellman equation. A distinctive feature of the exponential Bellman equation is that they associate the instantaneous reward and value function of the next step in a multiplicative way, rather than in an additive way as in the standard Bellman equations. From the exponential Bellman equation, we develop a novel analysis of the Bellman backup procedure for rens-sensi RL algorithms that are based on the principle of optimism. The analysis further motivates novel exploration mechanism called doubly decaying bonus, which helps the algorithms adapt to their estimation error over each horizon step while at the same time exploring efficiently. These discoveries enable us propose model-free algorithms for RL with the entropic risk measure based on the novel bonus. By combining the new analysis and bonus design, we prove that the preceding algorithms attain nearly optimal regret bounds under episodic and finite-horizon MDPs. Compared to prior results, our regret bounds feature an exponential improvement with respect to the horizon length and risk parameter, removing the factor of e !! from existing upper bounds. This significantly narrows the gap between upper bounds and the existing lower bound of regret.
In summary, we make the following theoretical contributions in this paper.
1. We investigate the gap between existing upper and lower regret bounds in the context of risk-sensitive RL, and identify deficiencies of the existing algorithms and analysis;
2. We consider the exponential Bellman equation, which inspires us to propose a novel analysis of the Bellman backup procedure for RL algorithms based on the entropic risk measure. It further motivates a novel bonus design called doubly decaying bonus. We then design two model-free risk-sensitive RI. algorithms equipped with the novel bonus.
3. The novel analytic framework and bonus design together enable us to prove that the preced- ing algorithms achieve nearly optimal regret bounds, which improve upon existing ones by an exponential factor in terms of the horizon length and risk sensitivity.
2
Related works
The problem of RL with respect to the entropic risk measure is first proposed by the classical work of 24 and has since inspired a large body of studies 2 4 I3 16
22 23 25 26
B1 33 B7]
38 40
43 However, the algorithms from this line of works require knowledge of the transition kernel assume access to simulator of the underlying environment. Theoretical properties of these algorithms are investigated based on these assumptions, but the results are mostly of asymptotic nature, which do not shed light on their dependency on key parameters of the environment and agent.
The work of (20) represents the first effort to investigate the setting where transitions are unknown and simulators of the environment are unavailable. It establishes the first non-asymplotic regret or sample complexity guarantees under the tabular setting. Building upon (20). the authors of [2T] extend the results to the function approximation setting, by considering linear and general function approximations of the underlying MDPs. Nevertheless, as discussed in Section [ both works leave open an exponential gap between the regret upper and lower bounds, which the present work aims to address via novel algorithms and analysis motivated by the exponential Bellman equation.
We remark that although the exponential Bellman equation has been previously investigated in the literature of risk-sensitiiv RI. 22 5 this is the first time that it is explored for deriving regret and sample complexity guarantees of senk-sensitive RL algorithms. In Appendix A
we also make

---

connections between risk-sensitive RL and distributional RL through the exponential Bellman equation.
Notations. For a positive integer n. we let [n] ==
For two non-negative sequences {a:} and {b;], we write a; S b, there exists a universal constant > 0 such that o; S Cb; for all and write a; = by a; S b, and b; S az. We use (() to denote O+)) while hiding logarithmic factors. For functions J.g l - IR, where U denotes their domain, we write f 2 g if f'()) 2 g(u) for any u E U. We denote by 11-} the indicator function.
Problem background
3.1 Episodic and finite-horizon MDP
The setting of episodic Markov decision processes can be denoted by is the set of states, A is the set of actions, H E Z>o is the length of each episode, and P {Ph helm and R (ra [H( are the sets of transition kernels and reward functions, respectively. We let S = | and A = I and we assume S, A < oc. We let Pa s, a) denote the probability distribution over successor states of step + 1 action executed in state s step h. We assume that the reward function yy : S x A + [0, 1] is deterministic. We also assume that both P and R are unknown learning agents.
where S
Under the setting of an episodic MDP, the agent aims to learn the optimal policy by interacting with the environment throughout K episodes, described as follows. At the beginning episode k, an initial state sf is selected by the environment and we assume sf stays the same for all k E [K]. In each step [H] of episode k, the agent observes state sy E S, executes an action a E A, and receives a reward equal to Th. (s aa))) from the environment. The MDP then transitions into state + randomly drawn from the transition kernel Pa sh, af.). The episode terminates at step H which the agent does not take actions or receive rewards. We define a policy = {TT)ee[H as (s) (s) is the action that the agent takes state s step collection of functions Th S A, where Ty of the episode.
3.2 Risk-sensitive RL
For each [H], define the value function V S + R of a policy the cumulative utility of the agent at state 8 of step h under the entropic risk measure, assuming that the agent commits to define
policy in later steps. Specifically,
Ahh s) E [H] X S, (s) =
B log
84 =
(1)
where B is given risk parameter. The agent aims maximize his cumulative utility in step
1, that is, to find a policy such that V/T is maximized for all state & E S. Under this setting, 0, the agent is risk-seeking and if B 0, the agent is risk-averse. Furthermore, B the agent tends to be ristrneutral and Vy[(s) (s) tends to the classical value function.
We may also define the action-value function Q S x A + IR, which is the cumulative utility of the agent who follows policy म. conditional on a particular state-action pair; formally, this is given by
v(h, a) E [ x S x A,
(T(,,a)= = log
1
IF
8, as = =a}
(2)
22. there always exists an optimal policy, which we denote as n² that yields the optimal value (s) == sup, (s) for all (h E [H] S.
Under some mild regularity conditions
Bellman equations. given by
For all (s, a) E S A, the Bellman equation associated with policy n
(ī(s, = = + log (Ep-P)(1) [
(3)
(s) (T(s, Vi+ =
3

---

for h E [H]. In Equation of the value function h++1 of the later step. This is in contrast with the linear Bellman equations in the risk-neutral setting (3 + 0), where (% a) = rs(s, a) + Eg (V 1 Based on Equation for h E [H], the Bellman optimality equation given by
B it can be seen that the action value Q7 of step h is non-linear function
(%,s, = (s a) + log (E
(4)
3 (8) max ()) aEA
(s)+())=00.
Exponential Bellman equation. We introduce the exponential Bellman equation, which is an exponential transformation of Equations (3 and ( (by taking exponential both sides): for any policy π and tuple (h, 8, a), we have
@ (.()))))))))))))))) E. ( ( ( (69)).
(5)
When π = x², we obtain the corresponding optimality equation 8 (s.0) Ex (et
(6)
Note that Equation associates the current and future cumulative utilities (Q) and V441) in
multiplicative way. An implication of Equation 5 is that one may estimate (.Q by quantity of the form
wh (s, a) = SampAvg((e (attga/eeeeeet....aaaaaaaa
(sh, (n),aa)= = (s,
given some estimate of the value function VR+1. Here, we denote by SampAvg(X) the sample average computed over elements in the set X' throughout past episodes, and it can be seen as an empirical MGF of cumulative rewards from step 1. Equation (5) also suggests the following policy improvement procedure for a risk-sensitive policy π:
argmax EA (n(na,,)) argmin e Qulaaa)
if 1
Th (s) f argmax Qu(s,
(8)
a'EAA
if < 0,
where Qn, denotes some estimated action-value function, possibly obtained from the quantity wh.
In the next section, we will discuss how the exponential Bellman equation (5) inspires the development of novel analytic framework for risk-sensitive RL. Before proceeding, we introduce a performance metric for the agent. For each episode kt recall that sf is the initial state chosen by the environment and let n be the policy of the agent at the beginning of episode k. Then the difference V1 (if) VI** (sf) is called the regret of the agent in episode k. Therefore, after K episodes, the total regret for the agent is given by
Regret(K) = Σ (V
(xt)).
(9)
KE[K]
which serves as the key performance metric studied in this paper.
Analysis of risk-sensitive RL
4.1 Mechanism of existing analysis
In this section, we provide an informal overview the mechanism underlying the existing analysis of risk-sensitive RL. Let us focus the case for simplicity of exposition; similar reasoning holds for 3 < A key step in the existing regret analysis RL algorithms to establish a recursion on the difference V V*** over h E [H) where V/A is the iterate of an algorithm in step h of episode k and Vir the value function of the policy used episode Such approach can commonly found in the literature of algorithms that use the upper confidence bound [27 28 in which the recursion takes the form of
Vi Vi-" < V
Vitii + th.
(10)

---

for 3 + 0 and some quantity viy. The work of (20), which studies the resk-sensitive setting under the entropic risk measure, also follows this approach and derives regret bounds by establishing the recursion of the form
Vi-" S E (Vi+t
Vi++1) t + B b% + 2H mi
1
(11)
where if denotes the bonus which enforces the upper confidence bound and leads the inequality VÍ 2 Vir for any policy æ, and غ is part of martingale difference sequence. The derivation of (3) which shows that the action value Q7, is the we may then unroll the
Equation (IT is based on the Bellman equation
sum of the reward ra and the entropic risk measure of V Following (20), recursion 11 from h = H to to get
1 V1 VI=" I JOBHH
Σ
b/ +
9H2
Σ mh:
(12)
h
given that V H+1 VØt1 = 0. Using the inequality Regret(K) S Ex VT*),, En, Uh (cOH 1WK and ΣE,, m S VK, we obtain the regret bound in (20] as Regret( k) S eHH 2a -1
VV.. Therefore, it can be seen that the dominating factor @H in their regret bound originates in Equation 12 which can be further traced back to the exponential factor e in the error dynamics 11
4.2 Refined approach via exponential Bellman equation
While the existing analysis in is motivated by the Bellman equation the form given in 3 we propose to work on the exponential Bellman equation (5). Equation (5) operates on the quantities eB.2% and e V+,,, which can be thought of as the MGFs of the current and future values, while the reward function Th is involved as a multiplicative term. This motivates us to derive a new recursion:
(e
ed e + 6% + m
(13)
where b/g m. denote some bonus and martingale terms, respectively, and r stands for the reward in step h of episode k. Unrolling Equation (13) yields
B.V B.V I
Σ
a DE (b) + m,
(14)
where D = -EEEAA- In words, the error of e 3.V7"" is bounded by the weighted sum of bonus and martingale difference terms, where the weights are given by ea the exponential rewards up to step h 1. We may then apply a localized linearization of the logarithmic function, which gives Regret(K)) S + Ex (e -VV and arrives at regret upper bound (the formal regret bounds will be established in Theorems rewards are only implicitly encoded in V/A in Equation [33 rewards are explicitly involved in the error dynamics via an exponential term.
I and 2 below). Different from Equation (IT) where
To see why Equation (33 is intuitively correct, we may divide both sides of the equation by 8 and take 3 By doing so, we should expect to obtain quantities from the error dynamics (10) of risk-ncutral RL. Since the function fa(x) (e 1)/3 satisfies that fa(x) + x as B + 0 for any fixed x, we have
g (c e.V ===v V. Via".
lim 8-0
lim a ( - = + + Vhl - (r + V.rii) V/ 3-0
V
recovering terms in 10.. Therefore, the recursion 15) can be seen as generalizing those in the analysis of risk-neutral RL.
By comparing Equations 13 and (T). we see that while both error dynamics are derived from the same underlying Bellman equation, they inspire drastically different forms of recursion. Note that
5

---

Algorithm RSVI2
Qi(s.)), (-) 11 h 1, (:
0 and wa(:-) for all 111
2: for episode k = I,... do
3: for step .H,...,Idd
4:
for (s ES x A such that (s, 2 1 do
5:
wh (8, < Nalo,a) E E T[ (6/,, a1 = (s.a)) (rr (V+
6:
(s, t deal -+11) h+1)
1 v 9 (HoKHHAA//)) where > 0 is a universal constant
Nn(e.0)
() min (s, bs, -
if 3 > 0 if <
7:
(s, by ((H-)ht)),,
8:
Va((s) t max.'e log (o,
9:
end for end for
11:
vh E [ take an + argmax log (8h, a d')}: observe Tn (sh, an), 8h++1
12: Add I to (sh,
13: end for
the multiplicative factor B.r. in Equation (3) is milder than the factor @H in Equation (TT), since r [0. 1]. This is the source of an improvement of our refined analysis over existing works. On the
other hand, the success of applying the error dynamics (13) in our analysis crucially depends on the
choice of bonus terms (b%
improper choice would blow up the error B B.V""" This
observation motivates our novel bonus design, as we explain next in Section 5
Algorithms
5.1 Overview of algorithms
In this section, we propose two model-free algorithms for RL with the entropic risk measure. We first present RSV12, which is based value iteration, in Algorithm [ The algorithm has two main stages: first estimates the value function using data accumulated up to episode k 1 (Line 10 and then executes the estimated policy collect new trajectory (Line [T]. In value function estimation, computes the weights Wh, or the empirical MGF of some estimated cumulative rewards evaluated 8, which can be seen simple moving average over [k - 1]. Therefore, Line 5 functions as a concrete implementation of Equation 7 where the sample average is instantiated as a simple moving average. Then in Line 7 computes an augmented estimate G₁, by combining wy, with bonus term by, (defined in Line This is followed by thresholding to put G₁, in the proper range. Note that GR is an optimistic estimator of the quantity e-Q in Equation (5) the construction of Gn augmented by by that it encourages exploration of rarely visited state-action pairs in future episodes, and thereby follows the principle of Risk-Sensitive Optimism
the Face of Uncertainty 20).. When 3 < the bonus subtracted from wh. since a higher level of optimism corresponds a smaller value of the estimate. In addition, Line I follows the reasoning of policy improvement suggested in Equation (
Next, we introduce RSQ2 in Algorithm which is based on Q-learning. Similar to Algorithm I consists of value estimation (Line g and policy execution (Line 6 steps. By combining Lines
[O] we see that Algorithmm2 2 computes the optimistic estimate G₁, as a projection of an exponential moving average of empirical MGFs:
GA an) < ПI (EMA (EMA((e on) Va-
(15)
where 1I, denotes projection that depends on step ht In particular, Line can be interpreted as computation of empirical MGFs evaluated at 3 and thus concrete implementation of Equation 7
using exponential moving average. This is in contrast with the simple moving average update in Algorithm|]
Although Algorithms D and are inspired by RSVI and RSQ of 20 respectively, we note that the
main novelty our algorithms lies in the bonus terms (b, Algorithm and by : in Algorithm ( which we call the doubly decaying bonus. We discuss this new bonus design in the following.

---

Algorithm 2 RSQ2
1: Qa(5.), Vi(() 11 h if Qn(:))), V+(()) 0 otherwise, for all h E /// +1
2: Na(s.) 0 for all h [M]: Ot
#+1 for H+a
3: for episode k 1 ,, K do
4: Receive the initial state 81
5: for step h ,...,, H do
6:
Take action aд <- argmax d'EA 3 log (Sn((,,,, and observe ry an) and 86+1
7: Add 1 to (M,, an); 1 t Na(sn, ab)
8:
by,t f cl (011()-++1]__ - 1/ -11V
Hog HSAK/0 for some universal constant c
9:
(h(Sh, ah) (1 (1-a)) Gn(sn; an) + or (on (on.as) (V-=)(
04)
Gn(s), - [mnn(un wnn. (sh, an) + aebras e (H1))
if 0
max{ wn (sh: an) - arbs, e ((H)), if < 0
11:
VA (sh) t max 3
12: end for
end for
5.2 Doubly decaying bonus
Let us focus on 3 > 0 for this discussion. In optimism-based algorithms, the bonus term is used enforce the upper confidence bound order encourage sufficient exploration in uncertain environments. It takes the form of a multiplier times a factor that is inversely proportional to visit counts ]. Our bonus follows this structure and is given by
ba as) x (H) - VV Nu(s,a)'
1
(16)
ignoring factors that do not vary in s.a. In Equation (T), the quantity e -++1)
plays
the role of the multiplier and VI/Na a) is the factor that decreases in the visit count. While
the component (s, a) is common in bonus terms, our new bonus is designed to shrink its multiplier deterministically and exponentially across the horizon steps, as 3(H- from @0 - in step h to e - in step h H. This is in sharp contrast with the bonus terms typically found in risk-neutral RI. algorithms, where the multipliers are kept constant in h (usually as constant multiple of H). Furthermore, RSQ proposed by (20). whose multiplier is SH - 1 and kept fixed along the horizon. Because by. decays both in the visit count (s, a) (across episodes) and the multiplier (HH 1++ (across the horizon), name it as doubly decaying bonus. We remark that this is a novel feature of Algorithms @ compared RSVI and RSQ. Let us discuss how this new exploration mechanism is motivated from the error dynamics
decreases
bonus design is also in contrast with that in RSVI and
Motivation of exponential decay. From Equation (4), we see that the error of the iterate is bounded by the sum of weighted bonus terms, where the weights are of the form B-Dn and Dr,
[0, h [1-1] 1). maximum. On the other hand, if we use the bonus as in (00] which proportional to 3
Choosing by x (HHH-h+1)
ensures that the weighted bonus on the order of a
then we would end up with a multiplicative factor 22HH 1 in regret, which is exponentially larger than @a
An alternative way to understanding the exponential decay of our bonus is follows.
At step h, the estimated value function is Vn E [0, H h + 1). which implies eBVV E [1, B(H is used to estimate e Q% with its estimation error given by
The iterate Gn, (of Algorithm 1 2
le
GAl 1 P < (HH-h-1) -1
where PA denotes empirical average operator over historical data in step h. Therefore, the
estimation error of G₁, shrinks exponentially across the horizon. Since bonus is used to compensate for and dominate the estimation error, the minimal order of by required is thus ((H-h+) 1, which is exactly the multiplier in Equation (16)
7

---

As a passing note, we remark that the decaying multiplier is not necessary in resk-neutral RL algorithms, since the estimation enror therein satisfies [Qn - (ra + Vh+1)l S. H - h----11 1, which is upper bounded by H for all h E [H]] This implies that it suffices to simply set the bonus multiplier constant multiple of H. In contrast, decays exponentially step h, and an adaptive and exponentially decaying bonus is needed.
have explained, the estimation error of our algorithms
Comparison with Bernstein-type bonus. We also compare our bonus in Equation (16) with the Bernstein-type bonus commonly used to improve sample efficiency of risk-neutral RL algorithms 1127] The Bernstein-type bonus takes the form of
(s, 0) x V + Var(Vn++1) + ( (n,ssaa) (s,a)
(17)
where Var(-) denotes empirical variance operator over historical data and o(-) denotes vanishing term as (s, a) + Dc. Our bonus in Equation (16) is different from the Bernstein-type bonus in
Equation (17) in mechanism: our bonus features the multiplier (HHH+++ 1 which decays exponen-
tially and deterministically over h E [M]. whereas the Bernstein-type bonus uses v Hl Var(Vn++1
the multiplier (ignoring the vanishing term). The term Var(V depends on the trajectory of the learning process. Therefore the multiplier is stochastic and stays on the polynomial order of H across the horizon. Moreover, it is unclear how the multiplier behaves in terms of step h.
6
Main results
In this section, we present and discuss our main theoretical results for Algorithms [
Theorem 1. For any 8 (o, 1I, with probability at least there exists a universal constant c >> (used in Algorithm 77, such that the regret of Algorithm
7 is bounded by
e101 -1 V HH (
Regret(K)
|
Theorem 2. For any 8 (0, 1), with probability at least - 6 and when K is sufficiently large, there
exists a universal constant e >> 0 (used in Algorithm 2 such that the regret of Algorithm 2 obeyy
e
Regret( K) S
HASAK log logSAKlg(HHSS HSAK/8)).
18|H
The proof of the two theorems are provided in Appendices B and respectively. Note that the above results generalize those in the literature of risk-neutral RL: when 3 + 0, we recover the same regret bounds of LSVI in (28 and Q-learning in 227
Let us discuss the connections between our results and those in 20 The work of 20 proposes two algorithms, RSVI and RSQ, that attain the regret bound
Regret(K) S e 112 d -
V Ho) K,
(18)
18111
and lower bound incurred by any algorithm
el H' -1
Reg 2
V poly (H) K,
(19)
|3|
where H' is a linear function in H:; for simplicity of presentation, we exclude polynomial dependen- cies on other parameters and logarithmic factors from the two bounds. particular, the proof of the lower bound is based on reducing an hard instance of MDP to multi-armed bandit. It is priori unclear whether the extra exponential factor el8)#r? in the upper bound (18) is fundamental in the MDP setting, or is due to suboptimal analysis or algorithmic design. We would like to mention that although one trivial way of avoiding the e|a|# factor in the upper bound (18) is to use sufficiently
small [8] in the algorithms of [20] (c.g.. |8| 1 H7 so that 18)82 H² < 1), such small | defeats the
8

---

very purpose of have an appropriate degree of risk-sensitivity in the algorithms. Hence, an answer for all * would be desirable.
In view of Theorems and 2 we see that our Algorithms and achieve regret bounds that are
exponentially sharper than those of RSVI and RSQ. In particular, our results eliminate the ela factor from Equation (18) thanks the novel analysis and doubly decaying bonus in our algorithms, which are inspired by the exponential Bellman equation (5) As a result, our bounds significantly narrow the gap between upper bounds and the lower bound
Acknowledgments and Disclosure of Funding
We thank the reviewers for their constructive feedback. Z. Yang acknowledges Simons Institute (Theory of Reinforcement Learning). Y. Chen is partially supported by NSF grant CCF-1704828 and CAREER Award CCF-2047910. Z. Wang acknowledges National Science Foundation (Awards 2048075, 2008827, 2015568, 1934931), Simons Institute (Theory of Reinforcement Learning), Amazon, J.P. Morgan, and Two Sigma for their supports.
References
[1] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Leurning, pages 263-272, 2017.
[2] Nicole Bäuerle and Ulrich Rieder. More risk-sensitive Markov decision processes. Mathematics of Operations Research, 39(1):105-120, 2014.
[3] Mare G. Bellemare, Will Dabney, and Rémi Munos. A distributional perspective on reinforce- ment learning. In International Conference on Machine Learning, pages 449-458. PMLR. 2017.
[4] Vivek Borkar. A sensitivity formula for risk-sensitive cost and the actor-critic algorithm. Systems & Control Letters, 44(5):339-346 2001.
[5] Vivek S. Borkar. Q-learning for risk-sensitive control. Mathematics of Operations Research, 27(2):294-311, 2002.
[6] Vivek S. Borkar. Learning algorithms for risk-sensitive control. In Proceedings of the 19th International Symposium Mathematical Theory of Networks and Systems pages 55-60, 2010.
[7] Vivek Borkar and Sean P. Meyn. Risk-sensitive optimal control for Markov decision processes with monotone cost. Mathematics of Operations Research, 27(1):122-209 2002.
[8] Rolando Cavazos- Cadinn and Daniel Hernandez-Hernándeer Discounted approximations for risk-sensitive average criteria in Markov decision chains with finite state space. Mathematics of Operations Research, 36(1):133-146, 2011.
[9] Lin Chen, Yifei Min, Mikhail Belkin, and Amin Karbasi. Multiple descent: Design your own generalization curve. In Advances in Neural Information Processing Systems, 2021.
[10] Lin Chen, Bruno Scherrer, and Peter L Bartlett. Infinite-horizon offline reinforcement learning with linear function approximation: Curse of dimensionality and algorithm. arXiv preprini arXiv:2103.098447 2021.
[11] Lin Chen and Sheng Xu. Deep neural tangent kernel and laplace kernel have the same rkhs, In International Conference on Learning Representations, 2021.
[12] Lin Chen, Qian Yu, Hannah Lawrence, and Amin Karbasi. Minimax regret of switching- constrained online convex optimization: No phase transition. In Advances in Neural Information Processing Systems, 2020.

---

[13] Stefano P. Coraluppi and Steven I. Marcus. Risk-sensitive, minimax, and mixed risk- neutral/minimax control of Markov decision processes. Stochastic Analysis, Control, Opti- mization and Applications, pages 21-40. Springer, 1999.
[14) 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.
[15] 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, 2018.
[16] Giovanni B. Di Masi and Lukasz Stettner. Risk-sensitive control discrete- tecreete-time Markov processes with infinite horizon. SIAM Journal on Control and Optimization, 38(1 1:61778, 1999.
[17] Giovanni B. Di Masi and Lukasz Stettner. Infinite horizon risk sensitive control of discrete time Markov processes with small risk. Systems & Control Letters, 40(1):15-20 20, 2000.
[18] Giovanni B. Di Masi and Lukasz Stettner. Infinite horizon risk sensitive control of discrete time Markov processes under minorization property. SIAM Journal on Control and Optimization, 46(1):231-252 2007.
[19] Amir-massoud Farahmand. Value function in frequency domain and the characteristic value iteration algorithm. In Advances in Neural Information Processing Systems, 2019.
[20] Yingjie Fei, Zhuoran Yang, Yudong Chen, Zhaoran Wang, and Qiaomin Xie. Risk-sensitive reinforcement learning: Near-optimal risk-sample tradeoff in regret. In Advances in Neural Information Processing Systems, 2020.
[21] Yingjie Fei, Zhuoran Yang, and Zhaoran Wang. Risk-sensitive reinforcement learning with function approximation: debiasing approach. In International Conference on Machine Learning, pages 3198-3207. PMLR, 2021.
[22] Wendell Fleming and William McEneaney, Risk-sensitive control on an infinite time horizon. SIAM Journal on Control and Optimization, 33(6):1881-191) 1995.
[23] Daniel Beemännde-HHennndde and Steven I. Marcus. Risk sensitive control Markov processes in countable state space. Systems & Control Letters, 29(3):147-155, 1996.
[24] Ronald A. Howard and James E. Matheson. Risk-sensitive Markov decision processes. Man- agement Science, 18(7):356-366 1972.
[25] Wenjie Huang and William Haskell. Stochastic approximation for aware markov decision processes. IEEE Transactions Automatic Control, 6613):1314-1320, 2020.
[26] Anna Jaskiewicz. Average optimality for risk-sensitive control with general state space. The Annals of Applied Probability, 17 17(2):654-675, 2007.
[27] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I. Jordan. Is Q-learning provably efficient? In Advances Neural Information Processing Systems, pages 4863-4873, 2018.
[28] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I. Jordan. Provably efficient reinforcement learning with linear function approximation. arXiv preprint arXiv: 2019.
[29] Joel Z Leibo, Cyprien de Masson d' Autume, Daniel Zoran, David Amos, Charles Beattie, Keith Anderson, Antonio García Castañeda, Manuel Sanchez, Simon Green, Audrunas Gruslys, et al. Psychlab: psychology laboratory for deep reinforcement learning agents. arXiv preprint arXiv: 1801.08 16, 2018
[30] Shuyang Ling, Ruitu Xu, and Afonso S Bandeira. On the landscape of synchronization networks: perspective from nonconvex optimization. SIAM Journal on Optimization, 2973):189-11977, 2019.
10

---

[31] Steven I. Marcus, Emmanual Femnndez-GGuuherran Daniel Hernández Germändez-Hernandeez Stefano Coraluppi, and Pedram Fard. Risk sensitive Markov decision processes. In Systems and Control in the Twenty-first Century, pages 263-279. Springer, 1997.
[32] Borislav Mavrin, Hengshuai Yao, Linglong Kong, Kaiwen Wu, and Yaoliang Yu. Distributional reinforcement learning for efficient exploration. In International Conference on Machine Learning, pages 4434-4434. PMLR, 2019.
[33] Oliver Mihatsch and Ralph Neuneier. Risk- reinforcement learning. Machine Learning, 49(2-3):267-290, 2002.
[34] Tetsuro Morimura, Masashi Sugiyama, Hisashi Kashima, Hirotaka Hachiya, and Toshiyuki Tanaka. Nonparametrie return distribution approximation for reinforcement learning. In International Conference on Machine Learning. 2010.
[35] Tetsuro Morimura, Masashi Sugiyama, Hisashi Kashima, Hirotaka Hachiya, and Toshiyuki Tanaka. Parametric return density estimation for reinforcement learning. arXiv preprint arXiv: 1233:3700.34997, 2012.
[36] Yael Niv, Jeffrre A. Edlund, Peter Dayan, and John P. O'Doherty. Neural prediction emrors reveal a risk-sensitive ciiforremenntleamming process in the human brain. Journal of Neuroscience, 32(2):551-562, 2012.
[37] Takayuki Osogami. Robustness and risk-sensitivity in Markov decision processes. In Advances in Neural Information Processing Systems, pages 233-241, 2012.
[38] Stephen D. Patek. On terminating Markov decision processes with risk-averse objective function. Automatica, 37(9):1379-133 1386, 2001.
[39] Mark Rowland, Mare Bellemare, Will Dabney, Rémi Munos, and Yee Whye Teh. An analysis of categorical distributional reinforcement learning. In International Conference Artificial Intelligence and Statistics, pages 29-37. PMLR, 2018
[40] Yun Shen, Wilhelm Stannat, and Klaus Obermayer. Risk-sensitive Markov control processes. SIAM Journal Control and Optimization, ((5):3622-667) 2013.
[41] Yun Shen, Michael J. Tobia, Tobias Sommer, and Klaus Obermayer. Risk-sensitive reinforce- ment learning. Neural Computation, 26(7):1298- 1328, 2014.
[42] Ganlin Song, Ruitu Xu, and John Lafferty. Convergence and alignment of gradient descentwith random back propagation weights. arXiv preprint arXiv:2106. 06044, 2021.
[43] Peter Whittle. Risk-sensitive Optimal Control, volume 20. Wiley New York, 1990.
[44] Ruitu Xu, Lin Chen, and Amin Karbasi. Meta learning in the continuous time limit, In International Conference Artificial Intelligence and Statistics, pages 3052-3060. PMLR, 2021.
[45] Derek Yang, Li Zhao, Zichuan Lin, Tao Qin, Jiang Bian, and Tie- Yan Liu. Fully parameterized quantile function for distributional reinforcement learning. Advances in neural information processing systems, 92:6193-6202,20 2019.


Reviews:
[{"review_id": "xrak967go36", "reviewer": "Reviewer_7Bjf", "summary": "This paper proposes an algorithm and regret analysis of risk sensitive reinforcement learning. Their regret guarantee is significantly tighter than prior work; in particular, it helps close the gap compared to the lower bound.", "questions": "", "limitations": "", "rating": 6, "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": "Strengths\n- Important problem\n- Significantly tighter regret analysis compared to prior work\n\nWeaknesses\n- Unclear connection to distributional reinforcement learning\n- Unclear exactly what novelty is being claimed in terms of connection to entropic risk measure\n\nOverall, I think this paper is studying an interesting and important problem, and includes several new insights that allow them to improve upon prior work.\n\nMy main concern with this paper involves some significant issues with its exposition, in particular, regarding the claimed connection to distribution reinforcement learning. First, the connection to distributional reinforcement learning is itself unclear. As far as I understand, the connection is simply that the exponential value function is the moment generating function of the distributional value function. However, this connection seems to be completely irrelevant to the remainder of the paper. They also do not make this connection very precise, and it is also unclear to me whether this connection is novel.\n\nThe authors also claim in their contributions that the connection is in terms of the “entropic risk measure”; I didn’t understand what the authors meant here.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "WyJm6I61ds5", "reviewer": "Reviewer_YKaB", "summary": "In this work a theoretical analysis is conducted in the context of risk-sensitive reinforcement learning with entropic risk measures. This allows connecting distributional RL and risk-sensitive RL. Two algorithms are proposed with a novel exploration scheme based on two bonuses. Regrets bounds are provided that improve previous analyses by an exponential term.\n", "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": "Originality:\n\nThe paper relies heavily on  a previous paper [16]. However, the authors improve [16] by a simple procedure re-formulating a recursion using an exponential form. The result of this re-formulation gives insight on how to obtain a tighter bound which translate in very simple modifications to existent algorithms (RSVI and RSQ from [16]). Although the change is small it has considerable implications in the regret bound.\n\nI also think the literature is fairly represented, specially the section commenting on the paper [16] since it is the closest one to this work.\n\nQuality: \n\n- I believe the work is technically sound. \n\n- I am unsure about the connection to distributional RL claimed by the authors. Maybe they could elaborate more on that? As far as I can see Equation 4 is just a simple re-arrangement of Equation 8 which is very well known in the community (see N Tishby, PA Ortega, J Grau-Moya, R Fox, D Polani works to name a few) and also derived in [16]. How exactly this connects to distributional RL?\n\n- It would be interesting to see if the authors can comment how their work could be extended to infinite horizon settings or to the online setting (non-episodic). Since the algorithm requires revisiting states at time \"h\" in order to have good estimates of Equation 5 I wonder if the presented work breaks down in this case.\n\n- Shouldn't Line 8 of Algorithm 1 contain a log e.g. 1/beta log G? Hand-wavy explanation: Since V=max Q and exp(beta Q) = G--> V = max 1/beta log G?\n\n- Actually looking again at this line, the authors could comment what happens when there is only 1 sample to estimate w? In that case one would obtain a risk-neutral estimate of V right?\n\nClarity: \n\nI want to thank the authors for producing such a well explained work. It is well organized, the explanations of the problems in [16] were good, and the method the authors used to solve it was also very well explained.\n\nSignificance: \n\nI think since the bound improvements are fairly easy to re-construct, this work might be a reference  that future researchers might use. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think the authors could have done a better job stating the limitations of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "WTP0zYZX_Gq", "reviewer": "Reviewer_tvfS", "summary": "The paper considers risk-sensive decision-making in reinforcement learning as modeled by an exponential utility function. In contrast to a previous work by Fei et al. (2016), the authors propose to consider the exponential Bellman equations, which allows to provide a smaller regret upperbound of their proposed algorithms.", "questions": "", "limitations": "", "rating": 7, "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": "The paper is generally well-written and the contributions (Algorithms with doubly decaying bonus and theoretical analysis that reduces the gap between the upperbound and lowerbound) are clearly presented. However, I think the exposition would be clearer if Sec.3.3 happens before Sec.3.2 because the exponential Bellman equation makes sense only after the corresponding value function has been introduced.\n\nRegarding the related work about distributional RL, the authors may want to also cite the following paper:\nD. Yang, L. Zhao, Z. Lin, T. Qin, J. Bian, and T. Liu, “Fully Parameterized Quantile Function for Distributional Reinforcement Learning,” NeurIPS 2019\n\nTypos:\n- line 96: large -> larger\n- (2): Z_{H+1} = 0 should be added\n- (3): Z_{h+1} -> Z\n- line 217: differerent\n- Algorithm 1 should also include the case when \\beta < 0 in lines 8 an 11\n- line 286: aveage\n- line 288: miminial \n- line 306: Algorithm -> Algorithms", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No suggestion is needed since the work is more fundamental.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "IC44cMPjUTN", "reviewer": "Reviewer_nUcE", "summary": "The paper studies the exponential Bellman equation that arises in risk sensitive reinforcement learning when using entropic risk measure as the risk measure. It claims to \"offer a route for connecting distributional RL and risk sensitive RL\", although this question is never seriously addressed. The main result of their analysis consists in design and analyse two novel RL algorithms that employ a novel exploration mechanism. The regret bounds on this mechanism improves by an exponential factor.", "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": "\nGenerally, the paper is well written and tackles an interesting problem. I consider the main contribution to be the said algorithms that exploit a new exploration strategy and its analysis in terms of regret, which leads to a regret bound that is O(exp(H)) instead of O(exp(H^2)) for previously proposed algorithm for this problem. From a theoretical point of view, this seems to be a relatively important contribution. On the other hand, I find that the claimed second contribution which relates to distributional RL is rather under-developed and trivial in its current state. The paper also might also lack a concrete application where one can confirm that the theoretical performance improvement translates in actual speed-ups in convergence rate during training.\n\nRegarding the connection with distributional RL, the authors claim in the abstract and introduction that the paper answers to the need of identifying an algorithm that can optimize non-heuristically risk-sensitive policies in a distributional RL framework. Yet, the only support to this claim comes in the form of an observation that the use of a recursive entropic risk measure in distributional RL might motivate encoding the distribution of the \"total cost to go\" through its moment generating function. Implications of this observation are completely missing from the paper while the details of a rigorous algorithmic method to do risk-sensitive distributional RL are undisclosed.\n\n\nOther comments:\n\nWhy focus on finite horizon MDPs? This assumption significantly restricts the scope of the paper.\n\nEquation (4) is misleading as it seems to indicate that the same Q_h function needs to satisfy the equality constraint for all values of \\mu. In general, I suspect that this is impossible to satisfy and that the authors meant that given any fixed \\mu, one could impose the condition described in equation (4). In particular, in a distributional RL setting, my understanding is that the Q_pi function would need to have four input parameters: h, s, a, \\mu.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not see anything special to report here.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers believe that the improved regret bound in this paper makes a significant contribution and that the paper should be considered for acceptance on the basis of that contribution alone.  

However, the one sticking point during reviewer discussion concerned the distributional RL connections in the paper.  More precisely, a long nested discussion starting with nUcE's initial review concerns about the mostly undeveloped link to Distributional RL (also reflected in other reviews) and continued towards the end of the discussion chain with reviewer tvfS.  The authors presented a detailed mathematical presentation in their final nested comment that convinced reviewer tvfS of the connection being claimed.  

While ultimately the reviewer concerns were addressed with this final author response, it is critically important that this mathematical presentation and discussion be included on revision, perhaps in an Appendix.  Furthermore, while reviewer tvfS is satisfied with the author response, reviewer nUcE would still prefer that a revised paper focus on the regret bound contributions and focus on the distributional RL discussion as a "a side remark that opens to future interesting research directions".  The authors are asked to carefully consider all of these comments as they prepare their final version.
Decision: Accept (Poster)