Exponential Bellman Equation and Improved Regret Bounds for Risk-Sensitive Reinforcement Learning
Year: 2021

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.

heading: 1 Introduction
text: Risk-sensitive reinforcement learning (RL) is important for practical and high-stake applications, such as self-driving and robotic surgery. In contrast with standard and risk-neutral RL, it optimizes some risk measure of 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 π = 1
β log{Eπ[eβR]},
with respect to the policy π, where β 6= 0 is a given risk parameter and R denotes the cumulative rewards.
Recently, the works of [20, 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) . e|β|H 2 · e |β|H − 1 |β|H
√ poly(H) ·K
without assuming knowledge of the transition distribution or access to a simulator. They also provide a lower bound (informally presented as)
Regret(K) & e|β|H ′ − 1 |β|H
√ poly(H) ·K
that any algorithm has to incur, where H ′ is a linear function of H . Despite the non-asymptotic nature of their results, it is not hard to see that a wide gap exists between the two bounds. Specifically,
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
the upper bound has an additional e|β|H 2
factor compared to the lower bound, and even worse, this factor is dominating in the upper bound since the quadratic exponent in e|β|H 2
makes it exponentially larger than e
|β|H−1 |β|H even for moderate values of |β| and H . It is unclear whether the factor of e |β|H2
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 an 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 risk-sensitive RL algorithms that are based on the principle of optimism. The analysis further motivates a 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 to propose two 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|β|H 2
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 RL algorithms equipped with the novel bonus.
3. The novel analytic framework and bonus design together enable us to prove that the preceding algorithms achieve nearly optimal regret bounds, which improve upon existing ones by an exponential factor in terms of the horizon length and risk sensitivity.

heading: 2 Related works
text: 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–8, 13, 16–18, 22, 23, 25, 26, 31, 33, 37, 38, 40, 41, 43]. However, the algorithms from this line of works require knowledge of the transition kernel or assume access to a 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-asymptotic regret or sample complexity guarantees under the tabular setting. Building upon [20], the authors of [21] extend the results to the function approximation setting, by considering linear and general function approximations of the underlying MDPs. Nevertheless, as discussed in Section 1, 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-sensitive RL [2, 5], this is the first time that it is explored for deriving regret and sample complexity guarantees of risk-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] := {1, 2, . . . , n}. For two non-negative sequences {ai} and {bi}, we write ai . bi if there exists a universal constant C > 0 such that ai ≤ Cbi for all i, and write ai bi if ai . bi and bi . ai. We use Õ(·) to denote O(·) while hiding logarithmic factors. For functions f, g : U → R, where U denotes their domain, we write f ≥ g if f(u) ≥ g(u) for any u ∈ U . We denote by I{·} the indicator function.

heading: 3 Problem background

heading: 3.1 Episodic and finite-horizon MDP
text: The setting of episodic Markov decision processes can be denoted by MDP(S,A, H,P,R), where S is the set of states,A is the set of actions,H ∈ Z>0 is the length of each episode, and P = {Ph}h∈[H] and R = {rh}h∈[H] are the sets of transition kernels and reward functions, respectively. We let S := |S| and A := |A|, and we assume S,A < ∞. We let Ph(· | s, a) denote the probability distribution over successor states of step h+ 1 if action a is executed in state s at step h. We assume that the reward function rh : S ×A → [0, 1] is deterministic. We also assume that both P andR are unknown to learning agents.
Under the setting of an episodic MDP, the agent aims to learn the optimal policy by interacting with the environment throughout K > 0 episodes, described as follows. At the beginning of episode k, an initial state sk1 is selected by the environment and we assume s k 1 stays the same for all k ∈ [K]. In each step h ∈ [H] of episode k, the agent observes state skh ∈ S, executes an action akh ∈ A, and receives a reward equal to rh(skh, a k h) from the environment. The MDP then transitions into state skh+1 randomly drawn from the transition kernel Ph(· | skh, akh). The episode terminates at step H + 1, in which the agent does not take actions or receive rewards. We define a policy π = {πh}h∈[H] as a collection of functions πh : S → A, where πh(s) is the action that the agent takes in state s at step h of the episode.

heading: 3.2 Risk-sensitive RL
text: For each h ∈ [H], we define the value function V πh : S → R of a policy π as the cumulative utility of the agent at state s of step h under the entropic risk measure, assuming that the agent commits to policy π in later steps. Specifically, we define
∀(h, s) ∈ [H]× S, V πh (s) := 1 β log { E [ eβ ∑H i=h ri(si,πi(si)) ∣∣∣ sh = s]} , (1) where β 6= 0 is a given risk parameter. The agent aims to maximize his cumulative utility in step 1, that is, to find a policy π such that V π1 (s) is maximized for all state s ∈ S. Under this setting, if β > 0, the agent is risk-seeking and if β < 0, the agent is risk-averse. Furthermore, as β → 0 the agent tends to be risk-neutral and V πh (s) tends to the classical value function.
We may also define the action-value function Qπh : S ×A → R, which is the cumulative utility of the agent who follows policy π, conditional on a particular state-action pair; formally, this is given by
∀(h, s, a) ∈ [H]× S ×A, Qπh(s, a) := 1 β log { E [ eβ ∑H i=h ri(si,ai) ∣∣∣ sh = s, ah = a]} , (2) Under some mild regularity conditions [2], there always exists an optimal policy, which we denote as π∗, that yields the optimal value V ∗h (s) := supπ V π h (s) for all (h, s) ∈ [H]× S .
Bellman equations. For all (s, a) ∈ S × A, the Bellman equation associated with a policy π is given by
Qπh(s, a) = rh(s, a) + 1 β log { Es′∼Ph(· | s,a) [ eβ·V π h+1(s ′) ]} , (3)
V πh (s) = Q π h(s, π(s)), V π H+1(s) = 0
for h ∈ [H]. In Equation (3), it can be seen that the action value Qπh of step h is a non-linear function of the value function V πh+1 of the later step. This is in contrast with the linear Bellman equations in the risk-neutral setting (β → 0), where Qπh(s, a) = rh(s, a) +Es′ [V πh+1(s′)]. Based on Equation (3), for h ∈ [H], the Bellman optimality equation is given by
Q∗h(s, a) = rh(s, a) + 1 β log { Es′∼Ph(· | s,a) [ eβ·V ∗ h+1(s ′) ]} , (4)
V ∗h (s) = max a∈A Q∗h(s, a), V ∗ H+1(s) = 0.
Exponential Bellman equation. We introduce the exponential Bellman equation, which is an exponential transformation of Equations (3) and (4) (by taking exponential on both sides): for any policy π and tuple (h, s, a), we have
eβ·Q π h(s,a) = Es′∼Ph(· | s,a)
[ eβ(rh(s,a)+V π h+1(s ′)) ] . (5)
When π = π∗, we obtain the corresponding optimality equation
eβ·Q ∗ h(s,a) = Es′∼Ph(· | s,a)
[ eβ(rh(s,a)+V ∗ h+1(s ′)) ] . (6)
Note that Equation (5) associates the current and future cumulative utilities (Qπh and V π h+1) in a multiplicative way. An implication of Equation (5) is that one may estimate eβ·Q π h(s,a) by a quantity of the form
wh(s, a) = SampAvg({eβ(rh(sh,ah)+Vh+1(sh+1)) : (sh, ah) = (s, a)}) (7)
given some estimate of the value function Vh+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 h + 1. Equation (5) also suggests the following policy improvement procedure for a risk-sensitive policy π:
πh(s)← argmax a′∈A Qh(s, a ′) =
{ argmaxa′∈A e
β·Qh(s,a′), if β > 0 argmina′∈A e β·Qh(s,a′), if β < 0, (8)
where Qh 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 a novel analytic framework for risk-sensitive RL. Before proceeding, we introduce a performance metric for the agent. For each episode k, recall that sk1 is the initial state chosen by the environment and let πk be the policy of the agent at the beginning of episode k. Then the difference V ∗1 (s k 1)−V π k 1 (s k 1) 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) := ∑ k∈[K] [V ∗1 (s k 1)− V π k 1 (s k 1)], (9)
which serves as the key performance metric studied in this paper.

heading: 4 Analysis of risk-sensitive RL

heading: 4.1 Mechanism of existing analysis
text: In this section, we provide an informal overview of the mechanism underlying the existing analysis of risk-sensitive RL. Let us focus on the case β > 0 for simplicity of exposition; similar reasoning holds for β < 0. A key step in the existing regret analysis of RL algorithms is to establish a recursion on the difference V kh − V π k
h over h ∈ [H], where V kh is the iterate of an algorithm in step h of episode k and V π k
h is the value function of the policy used in episode k. Such approach can be commonly found in the literature of algorithms that use the upper confidence bound [27, 28], in which the recursion takes the form of
V kh − V π k h ≤ V kh+1 − V π k h+1 + ψ k h, (10)
for β → 0 and some quantity ψkh. The work of [20], which studies the risk-sensitive setting under the entropic risk measure, also follows this approach and derives regret bounds by establishing the recursion of the form
V kh − V π k h ≤ eβH ( V kh+1 − V π k h+1 ) + 1
β b̃kh + e βHm̃kh, (11)
where b̃kh denotes the bonus which enforces the upper confidence bound and leads to the inequality V kh ≥ V πh for any policy π, and m̃kh is part of a martingale difference sequence. The derivation of Equation (11) is based on the Bellman equation (3), which shows that the action value Qπ k
h is the sum of the reward rh and the entropic risk measure of V π k
h+1. Following [20], we may then unroll the recursion (11) from h = H to h = 1 to get
V k1 − V π k 1 ≤ 1
β eβH 2 ∑ h b̃kh + e βH2 ∑ h m̃kh, (12)
given that V kH+1 = V πk H+1 = 0. Using the inequality Regret(K) ≤ ∑ k(V k 1 − V π k 1 ), ∑ k,h b̃ k h . (eβH − 1) √ K and ∑ k,h m̃ k h . √ K, we obtain the regret bound in [20] as Regret(K) . eβH 2 eβH−1
βH
√ K. Therefore, it can be seen that the dominating factor eβH 2
in their regret bound originates in Equation (12), which can be further traced back to the exponential factor eβH in the error dynamics (11).

heading: 4.2 Refined approach via exponential Bellman equation
text: While the existing analysis in (11) is motivated by the Bellman equation of the form given in (3), we propose to work on the exponential Bellman equation (5). Equation (5) operates on the quantities eβ·Q π h and eβ·V π h+1 , which can be thought of as the MGFs of the current and future values, while the reward function rh is involved as a multiplicative term. This motivates us to derive a new recursion:
eβ·V k h − eβ·V
πk h ≤ eβ·r k h ( eβ·V k h+1 − eβ·V πk h+1 )
+ bkh +m k h, (13)
where bkh,m k h denote some bonus and martingale terms, respectively, and r k h stands for the reward in step h of episode k. Unrolling Equation (13) yields
eβ·V k 1 − eβ·V
πk 1 ≤ ∑ h eβ·D k h(bkh +m k h), (14)
where Dkh = ∑ i∈[h−1] r k i . In words, the error of e β·V k1 − eβ·V π k 1 is bounded by the weighted sum of bonus and martingale difference terms, where the weights are given by eβ·D k h , the exponential rewards up to step h− 1. We may then apply a localized linearization of the logarithmic function, which gives Regret(K) ≤ 1β ∑ k(e β·V k1 − eβ·V π k
1 ), and arrives at a regret upper bound (the formal regret bounds will be established in Theorems 1 and 2 below). Different from Equation (11) where rewards are only implicitly encoded in V kh , in Equation (13) rewards are explicitly involved in the error dynamics via an exponential term.
To see why Equation (13) is intuitively correct, we may divide both sides of the equation by β and take β → 0. By doing so, we should expect to obtain quantities from the error dynamics (10) of risk-neutral RL. Since the function fβ(x) = (eβx − 1)/β satisfies that fβ(x)→ x as β → 0 for any fixed x, we have
lim β→0
1 β (eβ·V k h − eβ·V πk h ) = V kh − V π k h ,
lim β→0
1 β (eβ·r k h(eβ·V k h+1 − eβ·V πk h+1)) = rkh + V k h+1 − (rkh + V π k h+1) = V k h+1 − V π k h+1,
recovering terms in (10). Therefore, the recursion (13) can be seen as generalizing those in the analysis of risk-neutral RL.
By comparing Equations (13) and (11), we see that while both error dynamics are derived from the same underlying Bellman equation, they inspire drastically different forms of recursion. Note that
Algorithm 1 RSVI2 1: Qh(·, ·), Vh(·)← H − h+ 1, Nh(·, ·)← 0 and wh(·, ·)← 0 for all h ∈ [H + 1] 2: for episode k = 1, . . . ,K do 3: for step h = H, . . . , 1 do 4: for (s, a) ∈ S ×A such that Nh(s, a) ≥ 1 do 5: wh(s, a)← 1Nh(s,a) ∑ τ∈[k−1] I{(sτh, aτh) = (s, a)} · e β[rh(s,a)+Vh+1(s τ h+1)]
6: bh(s, a)← c|eβ(H−h+1) − 1| √
S log(HSAK/δ) Nh(s,a) where c > 0 is a universal constant 7: Gh(s, a)← {
min{wh(s, a) + bh(s, a), eβ(H−h+1)}, if β > 0 max{wh(s, a)− bh(s, a), eβ(H−h+1)}, if β < 0
8: Vh(s)← maxa′∈A 1β log{Gh(s, a ′)}
9: end for 10: end for 11: ∀h ∈ [H], take ah ← argmaxa′∈A 1β log{Gh(sh, a
′)}; observe rh(sh, ah), sh+1 12: Add 1 to Nh(sh, ah) 13: end for
the multiplicative factor eβ·r k h in Equation (13) is milder than the factor eβH in Equation (11), since rkh ∈ [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 {bkh}, as an improper choice would blow up the error eβ·V k 1 − eβ·V π
k
1 . This observation motivates our novel bonus design, as we explain next in Section 5.

heading: 5 Algorithms

heading: 5.1 Overview of algorithms
text: In this section, we propose two model-free algorithms for RL with the entropic risk measure. We first present RSVI2, which is based on value iteration, in Algorithm 1. The algorithm has two main stages: it first estimates the value function using data accumulated up to episode k − 1 (Line 3–10) and then executes the estimated policy to collect new trajectory (Line 11). In value function estimation, it computes the weights wh, or the empirical MGF of some estimated cumulative rewards evaluated at β, which can be seen as a 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, it computes an augmented estimate Gh by combining wh with a bonus term bh (defined in Line 6). This is followed by thresholding to put Gh in the proper range. Note that Gh is an optimistic estimator of the quantity eβ·Q π h in Equation (5): the construction of Gh is augmented by bh so that it encourages exploration of rarely visited state-action pairs in future episodes, and thereby follows the principle of Risk-Sensitive Optimism in the Face of Uncertainty [20]. When β < 0, the bonus is subtracted from wh, since a higher level of optimism corresponds to a smaller value of the estimate. In addition, Line 11 follows the reasoning of policy improvement suggested in Equation (8).
Next, we introduce RSQ2 in Algorithm 2, which is based on Q-learning. Similar to Algorithm 1, it consists of value estimation (Line 8–11) and policy execution (Line 6) steps. By combining Lines 9 and 10, we see that Algorithm 2 computes the optimistic estimateGh as a projection of an exponential moving average of empirical MGFs:
Gh(sh, ah)← Πh{EMA({eβ[rh(sh,ah)+Vh+1(sh+1)]})}, (15) where Πh denotes a projection that depends on step h. In particular, Line 9 can be interpreted as a computation of empirical MGFs evaluated at β and thus a concrete implementation of Equation (7) using an exponential moving average. This is in contrast with the simple moving average update in Algorithm 1.
Although Algorithms 1 and 2 are inspired by RSVI and RSQ of [20], respectively, we note that the main novelty of our algorithms lies in the bonus terms (bh in Algorithm 1 and bh,t in Algorithm 2), which we call the doubly decaying bonus. We discuss this new bonus design in the following.
Algorithm 2 RSQ2 1: Qh(·, ·), Vh(·)← H − h+ 1 if β > 0; Qh(·, ·), Vh(·)← 0 otherwise, for all h ∈ [H + 1] 2: Nh(·, ·)← 0 for all h ∈ [H]; αu ← H+1H+u for u ∈ Z 3: for episode k = 1, . . . ,K do 4: Receive the initial state s1 5: for step h = 1, . . . ,H do 6: Take action ah ← argmaxa′∈A 1β log{Gh(sh, a
′)} and observe rh(sh, ah) and sh+1 7: Add 1 to Nh(sh, ah); t← Nh(sh, ah) 8: bh,t ← c|eβ(H−h+1) − 1| √ H log(HSAK/δ)
t for some universal constant c > 0
9: wh(sh, ah)← (1− αt) ·Gh(sh, ah) + αt · eβ[rh(sh,ah)+Vh+1(sh+1)] 10: Gh(sh, ah)← {
min{wh(sh, ah) + αtbh,t, eβ(H−h+1)}, if β > 0 max{wh(sh, ah)− αtbh,t, eβ(H−h+1)}, if β < 0
11: Vh(sh)← maxa′∈A 1β log{Gh(sh, a ′)} 12: end for 13: end for

heading: 5.2 Doubly decaying bonus
text: Let us focus on β > 0 for this discussion. In optimism-based algorithms, the bonus term is used to enforce the upper confidence bound in order to encourage sufficient exploration in uncertain environments. It takes the form of a multiplier times a factor that is inversely proportional to visit counts {Nh}. Our bonus follows this structure and is given by
bh(s, a) ∝ (eβ(H−h+1) − 1)
√ 1
Nh(s, a) , (16)
ignoring factors that do not vary in (h, s, a). In Equation (16), the quantity eβ(H−h+1) plays the role of the multiplier and √ 1/Nh(s, a) is the factor that decreases in the visit count. While
the component √
1/Nh(s, a) is common in bonus terms, our new bonus is designed to shrink its multiplier deterministically and exponentially across the horizon steps, as eβ(H−h+1) − 1 decreases from eβH − 1 in step h = 1 to eβ − 1 in step h = H . This is in sharp contrast with the bonus terms typically found in risk-neutral RL algorithms, where the multipliers are kept constant in h (usually as a constant multiple of H). Furthermore, our bonus design is also in contrast with that in RSVI and RSQ proposed by [20], whose multiplier is eβH − 1 and kept fixed along the horizon. Because bh decays both in the visit countNh(s, a) (across episodes) and the multiplier eβ(H−h+1)−1 (across the horizon), we name it as doubly decaying bonus. We remark that this is a novel feature of Algorithms 1 and 2, compared to RSVI and RSQ. Let us discuss how this new exploration mechanism is motivated from the error dynamics (14).
Motivation of exponential decay. From Equation (14), we see that the error of the iterate is bounded by the sum of weighted bonus terms, where the weights are of the form eβ·Dh and Dh ∈ [0, h− 1]. Choosing bh ∝ eβ(H−h+1)− 1 ensures that the weighted bonus is on the order of eβH − 1 at maximum. On the other hand, if we use the bonus as in [20], which is proportional to eβH − 1, then we would end up with a multiplicative factor e2βH − 1 in regret, which is exponentially larger than eβH − 1. An alternative way to understanding the exponential decay of our bonus is as follows. At step h, the estimated value function is Vh ∈ [0, H−h+ 1], which implies eβ·Vh ∈ [1, eβ(H−h+1)]. The iterate Gh (of Algorithm 1 or 2) is used to estimate eβ·Q π h , with its estimation error given by
|eβ·Q π h −Gh| ≈ |eβ·Q π h − P̂heβ(rh+Vh+1)| ≤ eβ(H−h+1) − 1,
where P̂h denotes an empirical average operator over historical data in step h. Therefore, the estimation error of Gh shrinks exponentially across the horizon. Since bonus is used to compensate for and dominate the estimation error, the minimal order of bh required is thus eβ(H−h+1)− 1, which is exactly the multiplier in Equation (16).
As a passing note, we remark that the decaying multiplier is not necessary in risk-neutral RL algorithms, since the estimation error therein satisfies |Qh − P̂h(rh + Vh+1)| ≤ H − h+ 1, which is upper bounded by H for all h ∈ [H]. This implies that it suffices to simply set the bonus multiplier as a constant multiple of H . In contrast, as we have explained, the estimation error of our algorithms decays exponentially in step h, and an adaptive and exponentially decaying bonus is needed.
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 [1, 27]. The Bernstein-type bonus takes the form of
b̄h(s, a) ∝
√ H + V̂ar(Vh+1)
Nh(s, a) + o
(√ 1
Nh(s, a)
) , (17)
where V̂ar(·) denotes an empirical variance operator over historical data and o(·) denotes a vanishing term as Nh(s, a) → ∞. Our bonus in Equation (16) is different from the Bernstein-type bonus in Equation (17) in mechanism: our bonus features the multiplier eβ(H−h+1)−1 which decays exponentially and deterministically over h ∈ [H], whereas the Bernstein-type bonus uses √ H + V̂ar(Vh+1)
as the multiplier (ignoring the vanishing term). The term V̂ar(Vh+1) 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.

heading: 6 Main results
text: In this section, we present and discuss our main theoretical results for Algorithms 1 and 2. Theorem 1. For any δ ∈ (0, 1], with probability at least 1− δ there exists a universal constant c > 0 (used in Algorithm 1), such that the regret of Algorithm 1 is bounded by
Regret(K) . e|β|H − 1 |β|H
√ H4S2AK log2(HSAK/δ).
Theorem 2. For any δ ∈ (0, 1], with probability at least 1− δ and when K is sufficiently large, there exists a universal constant c > 0 (used in Algorithm 2) such that the regret of Algorithm 2 obeys
Regret(K) . e|β|H − 1 |β|H
√ H3SAK log(HSAK/δ).
The proof of the two theorems are provided in Appendices B and C, respectively. Note that the above results generalize those in the literature of risk-neutral RL: when β → 0, we recover the same regret bounds of LSVI in [28] and Q-learning in [27].
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) . e|β|H 2 · e |β|H − 1 |β|H
√ poly(H) ·K, (18)
and a lower bound incurred by any algorithm
Regret(K) & e|β|H ′ − 1 |β|H
√ poly(H) ·K, (19)
where H ′ is a linear function in H; for simplicity of presentation, we exclude polynomial dependencies on other parameters and logarithmic factors from the two bounds. In particular, the proof of the lower bound is based on reducing an hard instance of MDP to a multi-armed bandit. It is a priori unclear whether the extra exponential factor e|β|H 2
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|β|H 2
factor in the upper bound (18) is to use a sufficiently small |β| in the algorithms of [20] (e.g., |β| ≤ 1H2 so that e |β|H2 . 1), such a small |β| defeats the
very purpose of have an appropriate degree of risk-sensitivity in the algorithms. Hence, an answer for all β 6= 0 would be desirable. In view of Theorems 1 and 2, we see that our Algorithms 1 and 2 achieve regret bounds that are exponentially sharper than those of RSVI and RSQ. In particular, our results eliminate the e|β|H 2 factor from Equation (18) thanks to 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 (19).
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.

Review summaries:
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. 

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.

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.