{'fraction_non_alphanumeric': 0.06018155979001711, 'fraction_numerical': 0.018271991647089533, 'mean_word_length': 3.916583487808356, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 18, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Cascaded Gaps: Towards Gap-Dependent Regret for Risk-Sensitive Reinforcement Learning

In this paper, we study gap-dependent regret guarantees for risk-sensitive reinforcement learning based on the entropic risk measure. We propose a novel definition of sub-optimality gaps, which we call cascaded gaps, and we discuss their key components that adapt to the underlying structures of the problem. Based on the cascaded gaps, we derive non-asymptotic and logarithmic regret bounds for two model-free algorithms under episodic Markov decision processes. We show that, in appropriate settings, these bounds feature exponential improvement over existing ones that are independent of gaps. We also prove gap-dependent lower bounds, which certify the near optimality of the upper bounds.


Introduction
We study the problem of risk-sensitive reinforcement learning (RL) based on the entropic risk measure, in which we aim to identify a decision making rule (or policy) π that solves the following optimization problem: where R denotes the cumulative reward and β = 0 is the risk parameter that induces risk-seeking learning when β > 0 and risk-averse learning when β < 0. The (standard) risk-neutral objective function used in RL, which is simply E π [R], can be recovered from Eq. (1.1) by setting β → 0. Moreover, the objective of (1.1) in the form of entropic risk measure admits a Taylor expansion V π = E π [R] + β 2 Var π (R) + O(β 2 ), which represents a trade-off between the expectation and the variance (and possibly higher-order statistics) of the reward. Several lines of research on related problems have witnessed fruitful applications in a wide range of domains, including neuroscience (Niv et al., 2012;Shen et al., 2014), robotics (Nass et al., 2019;Williams et al., 2016Williams et al., , 2017, economics (Hansen & Sargent, 2011), and etc. The formulation (1.1) has been related to notions of robustness (Föllmer & Knispel, 2011;Hansen & Sargent, 2011;Osogami, 2012) and bounded rationality (Ortega & Stocker, 2016;Simon, 1955) in decision making and behavioral studies. A thermodynamic view on such formulation has also been proposed for understanding sequential decision making systems (Ortega & Braun, 2013).
For problem (1.1), much recent work has been devoted to designing algorithms that attain finite-sample regret bounds under Markov decision processes (MDPs). Although the existing bounds are nearly optimal in the minimax sense, they are overly pessimistic as they generally fail to exploit particular structures of the underlying MDPs, such as sub-optimality gaps, which quantify the easiness of learning optimal policies under the MDPs. Although previous work has explored and provided gap-dependent results for risk-neutral RL, it is unclear how the sub-optimality gaps should be constructed in the risk-sensitive setting. In particular, the definition of existing sub-optimality gaps, as we will elaborate in Section 4, crucially hinges on the linear structures of the risk-neutral setting, which no longer hold in the risk-sensitive setting characterized by the non-linear objective (1.1). It therefore begs the following natural questions: 1) how sub-optimality gaps should be characterized in risk-sensitive RL, and 2) whether we can obtain refined bounds on regret and sample complexity by taking advantage of the gap structures.
To answer the above questions, we study gap-dependent regret bounds for risk-sensitive RL based on the entropic risk measure. In particular, we identify two key conditions for a proper definition of sub-optimality gaps for risk-sensitive RL: Bellman difference condition and risk consistency condition. The Bellman difference condition states that the gaps induce a Bellman equation in which they play the role of reward functions; the risk consistency condition stipulates that the gaps stay on the same order of magnitude for both risk-averse and risk-seeking settings given fixed risk sensitivity |β|, and they reduce to risk-neutral gaps as |β| vanishes. Motivated by the two conditions, we propose a novel characterization of sub-optimality gaps for risk-sensitive RL, which we call cascaded gaps. Cascaded gaps consist of three key components: 1) the difference of rewards along trajectories controlled by an optimal policy, 2) the reward functions evaluated along a free trajectory (not controlled by any policy), and 3) a normalization factor that depends on the risk parameter. The first two components together exhibit a cascading property and address the Bellman difference condition, whereas the third component facilitates risk consistency.
Based on the cascaded gaps, we derive non-asymptotic regret bounds for two existing risk-sensitive RL algorithms, RSVI2 and RSQ2, that scale logarithmically in the number of episodes and decay in the cascaded gaps. The proof is based on a unified framework for both algorithms. We demonstrate that under proper settings, our regret bounds attain an exponential improvement over existing results with respect to the number of episodes, as well as an exponential improvement in terms of risk sensitivity and horizon over existing sample complexity bounds. We further show that the provided upper bounds are nearly optimal by deriving compatible lower bounds. To the best of our knowledge, this is the first work that studies sub-optimality gaps in risk-sensitive RL with the entropic risk measure and derives gap-dependent regret bounds.

Contributions.
In summary, we make the following theoretical contributions in this paper: 1. We propose a novel notion of sub-optimality gaps for risk-sensitive RL based on the entropic risk measure, which we call cascaded gaps. We discuss essential components of cascaded gaps tailored to the unique structure of risk-sensitive RL, and compare them with sub-optimality gaps in the riskneutral setting.

Related Works
Initiated by Howard & Matheson (1972); Jacobson (1973), risk-sensitive RL based on the entropic risk measure has been the focus of long-standing research efforts for the past decades (Bäuerle & Rieder, 2014;Borkar, 2001Borkar, , 2002Borkar & Meyn, 2002;Coraluppi & Marcus, 1999;Di Masi & Stettner, 1999;Fleming & McEneaney, 1995;Mihatsch & Neuneier, 2002;Osogami, 2012;Shen et al., 2013;Whittle, 1990). Most related to our work are perhaps those by Fei et al. (2021aFei et al. ( , 2021b: under the episodic and finite-horizon MDPs, they propose computationally efficient algorithms for risk-sensitive RL and provide finite-sample and nearly optimal regret guarantees in both tabular and linear settings. These results are general, holding without access to transitions or simulators. However, they fail to exploit particular structures of the underlying MDPs, such as sub-optimality gaps, and are therefore overly conservative under certain settings. For risk-neutral RL, a series of works has established non-asymptotic and gap-dependent regret bounds for optimistic algorithms, starting from Simchowitz & Jamieson (2019). Specifically, logarithmic regret are derived for optimistic Q-learning (Yang et al., 2021) and value iteration (He et al., 2021). Despite these recent developments, it remains unclear whether the defintion of sub-optimality gaps in risk-neutral RL is appropriate for the risk-sensitive setting, which the present work aims to address.

Episodic and Finite-Horizon MDPs
We focus on the setting of tabular MDPs, represented by a tuple (S, A, H, K, P, r

Risk-Sensitive RL
We define policy π := {π h : S → A} as a collection of functions that map states to actions. In risk-sensitive RL based on entropic risk measure, we define the state-value function with respect to any π: for each h ∈ [H] and s ∈ S, where the expectation is taken over the transition kernel P. The quantity β = 0 is the risk parameter of the entropic risk measure. In particular, β > 0 yields a risk-seeking value function, while β < 0 induces a risk-averse value function. The risk-neutral definition of the value function can be recovered through taking β → 0. Similarly, we define the corresponding action-value function as Note that we omit the dependency of V π h and Q π h on β for simplicity. Consequently, the Bellman equation for risk-sensitive RL is given by which relates the action-value function Q π h to the state-value function V π h+1 of the next step. Note that the Bellman equation is non-linear in the value function due to the non-linearity of the entropic risk measure. It can be shown that there always exists an optimal policy π * with the optimal value V * h (s) := V π * h (s) = sup π V π h (s) for every h ∈ [H] and s ∈ S; we also write Q * h : Under episodic MDPs, the agent aims to learn an optimal policy π * by interacting with the environment for K episodes. We measure the performance of the agent that follows policies {π k } k∈ [K] via the notion of regret, which is defined as

Bellman Difference Condition
Since both regret and sub-optimality gaps represent some notion of sub-optimality with respect to an optimal policy π * , it would be instrumental to associate the two through a unified lens. We do so by introducing the following condition, which later plays a key role in our analysis.
where D π h := Z * h − Z π h and a := π h (s). Condition 4.1 stipulates that for any fixed policy π, the gaps induce a form of Bellman equation where the action follows policy π. The function D π h , itself being the difference of two functionals with respect to some π * (optimal with respect to {Z π h }) and π, takes the role of the value function, and the gap takes the role of the reward function. Indeed, Condition 4.1 associates the sub-optimality induced by D π h with that embedded in gap h . The condition also suggests that when π = π * , we have D π * h = 0 and therefore gap h (s, π * h (s)) = 0. As an example, we show that the sub-optimality gaps defined in risk-neutral RL meets Condition 4.1. Recall the risk-neutral value functions for (h, s, a) ∈ [H] × S × A and policy π, with Q * h and V * h being the corresponding optimal value functions. In existing literature, the sub-optimality gaps for risk-neutral RL are given by He et al., 2021;Simchowitz & Jamieson, 2019;Yang et al., 2021). Note that the gap in Eq. (4.1) computes the difference in values between the optimal action π * (s) and action a. As stated and proved below, it satisfies Condition 4.1 in the risk-neutral setting.  Proof. Recall that in the risk-neutral setting, the Bellman equation for any policy π is given by for any (h, s, a ′ ) ∈ [H] × S × A. We fix a tuple (h, s, a) where a = π h (s), and let Z π , where step (i) is due to the Bellman equation (4.2).
Given Fact 4.2, a connection between regret and sub-optimality gaps can be established: since regret in the risk-neutral setting is defined as R h as implied in Fact 4.2). In words, the regret can be written as the sum of {D π k 1 } defined for the Bellman difference condition, in which sub-optimality gaps take the role of rewards.
The proof of Fact 4.2 exploits the Bellman equations under the risk-neutral setting and, in particular, the linearity of Q π h in terms of r h and V π h+1 . However, such linear properties are not available in risk-sensitive RL, as seen in Eq. (3.1), where the non-linearity is induced by the entropic risk measure X → 1 β log(E[e βX ]). This suggests that a simple definition of sub-optimality gaps such as Eq. (4.1) may not be appropriate, and an alternative definition is necessary.

Cascading Structure
To introduce sub-optimality gaps for risk-sensitive RL, we need a few additional notations. We denote by τ a trajectory of length H, which is a series of state-action pairs {(s j , a j )} j∈ [H] , and we let T be the set of all possible trajectories. For any trajectory τ ∈ T and h ∈ [H], we let τ h denote the trajectory that consists of the first h elements in τ , and we define the set T h := {τ h : τ ∈ T}. Note that τ H = τ and T H = T. We also let τ 0 be an empty trajectory and T 0 := ∅. We further define the cumulative reward function R on trajectories such that R(τ 0 ) := 0 and R(τ h ) : Motivated by the discussion in Section 4.1, we propose the following definition of sub-optimality gaps for risk-sensitive RL: for any step h and trajectory τ , we let where ψ β := 1/β for β > 0 and ψ β := e −βH /β for β < 0. It is not hard to see that ∆ h,β ≥ 0 for any β = 0.
Let us remark on several noteworthy properties of this gap definition. First, in contrast with ∆ h defined in Eq. (4.1) for the risk-neutral setting, which only depends on π * and a single state-action pair (s, a) at step h, the gap ∆ h,β defined in Eq. (4.3) additionally depends on the trajectory prior to step h. Specifically, the gap consists of two components: the factor e β·R(τ h−1 ) , which is with respect to an uncontrolled trajectory τ h−1 up to step h − 1, as well as a quantity e β·V * h (s) − e β·Q * h (s,a) , which is with respect to the trajectory controlled by an optimal policy π * starting from step h and state-action pair (s, a) (actions in the expectation of V * h and Q * h follow π * after step h). This means that ∆ h,β contains both uncontrolled and optimally controlled trajectories. Second, given a trajectory τ and for β > 0, as h increases, the multiplicative factor e β·R( Fig. 1 for an illustration of this property. In view of their special structure, we name these gaps as cascaded gaps.
We will soon discuss the factor ψ β , another distinctive and important feature of cascaded gaps, but for now let us show that the gaps satisfy Condition 4.1.

Fact 4.3. For any
Proof. Let us consider an arbitrary policy π and fix a tuple (h, s, a) such that a = π h (s). We also fix a trajectory τ whose h-th element is (s, a). We have

Risk-Neutral Gaps
Figure 1: A comparison of the cascaded gaps (4.3) in the risk-sensitive setting (β > 0) and risk-neutral gaps (4.1) for H = 3. The blue blocks illustrate π * -controlled trajectories, whereas the red blocks illustrate uncontrolled trajectories. Note that for the top cascaded gap, the uncontrolled trajectory part e β·R(τ0) = 1 since R(τ 0 ) = 0 by definition.
where step (i) holds by taking exponential on both sides of the Bellman equation (3.1), and the last step holds by the definition of D π h in Condition 4.1 and that of Z π h .
The proof crucially exploits the multiplicative property of the Bellman equation (3.1) raised to exponential 1 as well as the cascading structure of ∆ h,β . Based on ∆ h,β , we define the minimal cascaded gap ∆ min,β as the minimum non-zero cascaded gap over tuples (h, s, a) ∈ [H] × S × A and trajectories τ ∈ T, i.e., For any fixed β, the minimal gap serves as a measure for the difficulty of the corresponding MDP problem. We assume ∆ min,β > 0 throughout the paper to avoid triviality.

Normalization for Risk Consistency
One might notice that our notion of cascaded gaps is not the only gap definition that satisfies Condition 4.1. Indeed, another candidate for the gap definition would be ∆ , with the only difference, compared to ∆ h,β , being that it replaces the normalization factor ψ β with the sign of β. It is not hard to show that this alternative definition also meets Condition 4.1.
Yet, we demonstrate that the normalizer ψ β is crucial for the gap ∆ h,β to showcase risk consistency: the gap has the same order of magnitude when |β| is fixed and recovers the risk neutral gap ∆ h as |β| → 0. To illustrate this point (as well as the deficiency of the alternative ∆ ′ h,β ), let us consider an MDP with arbitrary transition kernels and its reward function satisfying r h (s, a) = 1 for (h, s, a) ∈ [H − 1] × S × A, r H (s, a * ) = 1 for some action a * ∈ A, and r H (s, a) = 0 for A \ {a * }. That is, this MDP has all its rewards equal to 1 except for the last step when sub-optimal actions are taken (which yields zero rewards).
For β > 0, the alternative gap ∆ ′ h,β of the above MDP is on the order of e βH − 1 (which grows exponentially in β), but for β < 0, its order is of 1 − e βH (which is upper bounded by 1 for any β < 0). Therefore, the magnitude of ∆ ′ h,β is inconsistent under different signs of β. On the other hand, it can be verified that our definition ∆ h,β is on the same order of (e |β|H − 1)/|β| for all β = 0, thanks to the risk-dependent normalization factor ψ β . In addition, as for any (h, s, a, τ ) by L'Hospital's rule, thereby recovering the definition of sub-optimality gaps in the risk-neutral setting; nevertheless, ∆ ′ h,β tends to 0 and becomes degenerate as β → 0.

Algorithms
We consider two model-free algorithms for risk-sensitive RL, RSVI2 (Algorithm 1) and RSQ2 (Algorithm 2), both of which are proposed in Fei et al. (2021a).
Algorithm 1 is based on value iteration that features an optimistic estimate Q h of the action value with a bonus term. In episode k, we compute at each step h the sample average (5.1) over prior episodes for all visited state-action pairs (s, a). The bonus is given by where c > 0 is a universal constant. It decays in both step h and the number of visits N h , thus also known as the doubly decaying bonus (Fei et al., 2021a), and enforces the principle of Risk-Sensitive Optimism in the Face of Uncertainty that encourages more exploration of less frequently visited state-action pairs. We then compute the optimistic estimate of the action-value function through Note that for β > 0, the addition of the bonus term b h represents optimism in risk-seeking decision making, whereas for β < 0 the subtraction of the bonus term corresponds to optimism in risk-averse decision making. Finally, in the policy execution stage, action a h is taken following the policy that maximizes Q h (s h , ·) over A.
On the other hand, Algorithm 2 follows the paradigm of Q-learning. In step h it computes the (exponential) moving average estimate through online updates instead of batch updates as used in Algorithm 1. However, it uses a similar doubly decaying bonus term for some universal constant c > 0, in enforcing optimism for efficient exploration. Similarly, the optimistic estimation of the value function is set as where the update on the exponential value function and truncation are given by Algorithm 1 RSVI2 Require: number of episodes K, confidence level δ ∈ (0, 1], and risk parameter β = 0 Update w h (s, a) following (5.1)

Main Results
In this section, we present gap-dependent regret bounds for risk-sensitive RL. We first provide regret upper bounds for Algorithms 1 and 2, and then we present a regret lower bound that any algorithm has to incur. For notational simplicity, we write ∆ min := ∆ min,β and ∆ h := ∆ h,β in short by dropping their dependency on β.

Regret Upper Bounds
The following theorem provides the gap-dependent performance of Algorithm 1.

Moreover, the expected regret is upper bounded by
The proof is provided in Appendix B.2. The above bounds are general as they hold for any β = 0. They also imply results obtained under the risk-neutral setting when |β| → 0. This is verified given that (e |β|H − 1)/|β| → H and ∆ min → ∆ min (where we let ∆ min denote the minimal sub-optimality gap for the risk-neutral setting). It can thus be seen that when |β| → 0, Theorem 6.1 provides a result that matches the risk-neutral bound O((H 5 d 3 / ∆ min ) log(HSAK/δ) 2 ) (where d = SA under our setting) in He et al. (2021, Theorem 4.4) with respect to K and H.
Next we provide regret guarantees for Algorithm 2.

Moreover, the expected regret is upper bounded by
The proof is provided in Appendix B.3. Note that the above regret bounds have the same factor (e |β|H −1) 2 |β| 2 ∆min as in Theorem 6.1; we will show in Section 6.2 that such dependency is nearly optimal. Applying the same argument as for Theorem 6.1, when |β| → 0, Theorem 6.2 recovers the risk-neutral bound O((H 6 SA/ ∆ min ) log(SAHK)) proved in Yang et al. (2021, Theorem 3.1) for a Q-learning algorithm.
Under this setting, we attain an exponential improvement in K over the existing regret bounds in Fei et al. (2021a), reducing the polynomial dependency on K (specifically the O(K 1/2 ) dependency) to a logarithmic one. In sharp contrast, the regret bounds of Fei et al. (2021a) that are independent of sub-optimality gaps, i.e., R(K) ≤ min HK, e |β|H − 1 |β| K 1/2 poly(H, S, A; K, 1/δ) .
must incur the exponential factor e |β|H −1 |β| for gaining only a polynomial improvement in K. When µ log(K) √ K , the regret bound (6.1) is dominated by the existing O(K 1/2 ) bound.
Our gap-dependent regret bounds also imply an exponential improvement in terms of sample complexity. Based on an argument in Jin et al. (2018), our Theorems 6.1 and 6.2 imply that Algorithms 1 and 2 find ε-optimal policies in the PAC setting with Ω (e |β|H −1) 2 |β| 2 ∆minε poly(H, S, A) samples for any ε > 0. On the other hand, the regret bounds in Fei et al. (2021a)

Regret Lower Bounds
Below we present regret lower bounds that complement the upper bounds in Theorems 6.1 and 6.2. We provide the proof in Appendix C. When β is sufficiently large, Theorem 6.4 provides a lower bound with exponential dependence on |β| and H, thus nearly matching the upper bound in Theorem 6.1 in terms of the exponential dependency and up to a logarithmic factor in K. Compared with the upper bound, the lower bound falls short of a term of e |β|(H−1) − 1 as well as polynomial factors in other parameters; it is not yet clear whether there exists a fundamental gap between the two bounds, and we leave the investigation for future work.
On the other hand, when |β| is sufficiently small, we achieve a lower bound that depends only polynomially on H and is independent of β (beyond potential dependence in ∆ min ). Consequently, this result nearly matches that of Corollary 6.3. Compared with existing risk-neutral lower bound of He et al. (2021, Theorem 5.4), our result specializes in the tabular setting and holds in the regime of non-vanishing β, while theirs adapts to linear function approximation but only in the risk-neutral regime (|β| → 0).
To the best of our knowledge, this work presents the first non-asymptotic and gap-dependent regret bounds for risk-sensitive RL based on the entropic risk measure.

A Unified Framework
In existing literature, algorithms based on value iteration and Q-learning are often analyzed in independent ways due to their distinctive characteristics and update mechanism. We instead employ a unified framework for analyzing the regret of Algorithms 1 and 2. To that end, we focus on the high-probability regret bounds, and the expectation bound can be obtained as a by-product of the analysis. For each k ∈ [K], let us define τ k := {(s k h , a k h )} h∈ [H] to be the sample trajectory in episode k. Thanks to Fact 4.3 that the cascaded gaps {∆ h } satisfy Condition 4.1, we may derive the following lemma on regret using a standard concentration result.
Lemma 6.5. For Algorithms 1 and 2 and any fixed δ ∈ (0, 1], it holds with probability at least 1 − δ/2 that The proof is given in Appendix B.1. In the above lemma, the regret R(K) plays a role similar to the expectation of the random variable k,h ∆ h (s k h , a k h ; τ k h−1 ), while the second term on the RHS can be interpreted as the deviation of the random variable from its expectation. With Lemma 6.5 in place, it remains to bound the first term of RHS for both algorithms. We do so in the next two lemmas. Lemma 6.6. For Algorithm 1 and any δ ∈ (0, 1], it holds with probability at least 1 − δ/2 that Lemma 6.7. For Algorithm 2 and any δ ∈ (0, 1], it holds with probability at least 1 − δ/2 that We provide the proofs in Appendices B.2.2 and B.3.2. By combining Lemma 6.5 with Lemmas 6.6 and 6.7, we arrive at Theorems 6.1 and 6.2, respectively. In addition, we remark that the bounds on expected regret can also be obtained from Lemmas 6.6 and 6.7 for corresponding algorithms by simple calculations.

Conclusion
We study gap-dependent regret for risk-sensitive RL with the entropic risk measure under episodic and finitehorizon MDPs. We propose a novel definition of sub-optimality gaps, named as cascaded gaps, tailored to the unique characteristics of risk-sensitive RL. We prove gap-dependent lower bounds on the regret to be incurred by any algorithm, and provide nearly matching upper bounds for two existing model-free algorithms. Under proper settings, we demonstrate that our upper bounds imply exponential improvement in bounds of both regret and sample complexity over existing results.

A Additional Definitions
Before diving into the proofs, we would like to provide additional definitions on several notion of gaps. We start with the definition of policy-controlled trajectories and sample trajectories as series of state-action pairs; we then define several notions of semi-normalized gaps that we use only in the proofs.
For a policy π, we define the π-controlled trajectory τ π := {(s j , π j (s j ))} j∈ [H] as a series of state-action pairs where the action follows π at every state. We define τ k be the sample trajectory of episode k, i.e., τ k := {(s k j , a k j )} j∈ [H] . Let us introduce some additional notion of gaps, based upon cascaded gaps, to assist our proofs. Without loss of generality, we fix β = 0, a trajectory τ , and (k, h, s, a) ∈ [K] × [H] × S × A. We define the semi-normalized sub-optimality gap as and we also pair the semi-normalized gap with a semi-normalizer Note that the cascaded gap ∆ h satisfies that ∆ h (s, a; τ h−1 ) =ψ β · ∆ h (s, a; τ h−1 ), which can be regarded as a further level of normalization. For any policy π, we also define the π-controlled sub-optimality gap as which characterizes the sub-optimality of policy π with respect to the optimal policy π * . Similar to the semi-normalized sub-optimality gap, we define the normalized π-controlled sub-optimality gap to be a) for any (s, a) ∈ S × A by definition, and the gaps are always non-negative quantities due to the monotonicity of exponential function and the normalization factor 1 β . The semi-normalizerψ β is designed to keep the gaps on the same magnitude for both β > 0 and β < 0.
We introduce a notion of optimism gap that represents the difference between the optimistic estimation Q k h by the algorithm and the optimal value function V * h . Similar to the cascaded gap, we define the semi-normalized optimism gap as and the normalized optimism gap as ∆ k h (s, a; τ h−1 ) :=ψ β · ∆ k h (s, a; τ h−1 ), with the same semi-normalizer applied.
Moreover, we define the (semi-normalized) minimal sub-optimality gap to be the minimal non-zero seminormalized sub-optimality gap over the tuple (h, s, a, τ ): Note that the dependency on β is implicit here. With the above definition, we recall the minimal suboptimality gap from Eq. (4.4), and have that ∆ min =ψ β ∆ min .
In the subsequent proofs we will leverage a peeling argument, for which we define a series of end points {ρ n } N n=1 , where ρ n := 2 n ∆ min , and they generate a series of intervals {I n } N n=1 with I n := [ρ n−1 , ρ n ) for all n ∈ [N ].
Recall that s k 1 is defined as the state in the first step of episode k; since we assume fixed initial state s 1 for all episodes, we have s k 1 = s 1 . We introduce the notion of exponential regret that sums over all the episodes the difference between exponential value functions of the optimal policy π * and that of any policy π k . Specifically, for any episodic MDP with K episodes, the exponential regret of policy {π k } K k=1 is defined as E(K) := 1 β k∈ [K] [e β·V * 1 − e β·V π k 1 ](s k 1 ).

B.1 Proof of Lemma 6.5
In this proof, we assume β > 0 without loss of generality, the proof where β < 0 can be similarly carried ](s k 1 ). Following from Lemma B.1, we have {Z k } k∈ [K] being a martingale difference sequence with respect to the filtration F k that represents all the randomness up to episode k. Further recall that the semi-normalized sub-optimality gap for any trajectory and we can thus control the magnitude of Z k by

For any trajectory {τ
Otherwise, if E(K) > B β , we lower bound the sum k∈[K] Z k following Freedman inequality from Lemma D.4. More specifically, notice that given the filtration F k , the variance and we can bound the RHS following a peeling argument. Notice that event G ⊆ where step (i) follows from the fact that E(K) ≤ K|e βH − 1|/|β|, step (ii) follows from stratifying the feasible range into ̺ = ⌈log K⌉ layers and applying union bound over all i ∈ [̺], and step (iii) follows from relaxing the quantity of E(K) within the stratified range 2 Combining both cases, with probability at least 1 − ̺ · e −ς , we have a lower bound The lower bound on k∈ [K] Z k implies an upper bound on exponential regret: and a sufficient condition gives that with probability at least 1 − δ/2 where ς = log(2⌈log K⌉/δ). Following Lemma D.1, with probability at least 1 − δ/2, the total regret R(K) is bounded by Lemma B.1. The quantity 1 β [e β·V * 1 − e β·V π k 1 ](s k 1 ) for episode k ∈ [K] admits the following decomposition: Proof. For any episode k ∈ [K], we have where the equality is due to Fact 4.3 and the expectation is taken over the transition probability P 1 (· | s 1 , π k 1 (s 1 )) given the policy π k . We expand the RHS of the equation recursively to get where the sub-optimality gap is defined over the entire trajectory τ π k h−1 and the expectation is over all trajectories reachable under the policy π k and transition probability P h (· | s h , π k h (s h )) for all h ∈ [H].
In the sections below, we provide for each algorithm a near-optimal upper bound of the sum of cascaded gaps k∈ [K] h∈ [H] ∆ h (s k h , a k h ; τ k h−1 ) following a peeling argument, a widely used technique for empirical processes (He et al., 2021;Yang et al., 2021). The final results, i.e., Theorems 6.1 and 6.2, follow from plugging in the upper bounds of the sum of cascaded gaps into Lemma 6.5.

B.2.2 Proof of Lemma 6.6
For any h ∈ [H] and k ∈ |β| (e |β|H − 1). Let us define N := ⌈log 2 ( 1 |β| (e |β|H − 1)/∆ min )⌉. Following Lemma B.2, with probability at least 1 − δ/2, we have where step (i) is due to the peeling argument that stratifies the range of ∆ min into N slices with end points Proof. Let us denote M h,n to be the number of episodes such that the sub-optimality of the episode at step h is no less than ρ n , i.e., M h,n : Especially, k 1 < . . . < k M h,n < k denote the selected indices of previous episodes such that ∆ π k i h (s ki h , a ki h ; τ ki h−1 ) ≥ ρ n at step h, and we further define R ki h := h j=1 r j (s ki j , a ki j ) to be the sum of rewards for the first h steps within the selected episodes. For the convenience of notation, we use ϑ to denote the logarithmic factor log(2HSAK/δ). Let us also define a shorthand [P h V ](s, a) := E s ′ [V (s ′ )] with respect to P h for any value function V : S → R and state-action pair (s, a) ∈ S × A.
Notice that we can make a recursive upper bound on the gap between the optimistic value function Q ki h and policy controlled value function Q π k i h as follows: for any ε > 0, which means with probability at least 1 − δ/2, h∈[H] i∈ [M h,n ] e β·(h−1) ζ ki h+1 ≤ |e βH − 1| 2HM h,n ϑ.
At the same time, we provide for the optimism gap a lower bound as follows: High-probability regret bound. By Lemmas 6.5 and 6.7, it holds with probability at least 1 − δ that where the last inequality is due to ∆ min ≤ 1 |β| (e |β|H − 1).

B.3.2 Proof of Lemma 6.7
With the help of Lemma B.3, it holds with probability at least 1 − δ/2 that Hence, with probability at least 1 − δ/2, the sum of the cascaded gaps is bounded by where N := ⌈log 2 ( 1 |β| (e |β|H − 1)/∆ min )⌉ and the last step follows from an infinite sum of geometric series. Recall the definition ρ n := 2 n ∆ min and interval I n := [ρ n−1 , ρ n ) for all n ∈ [N ]. Lemma B.3. Under Algorithm 2, with probability at least 1 − δ/2, it holds that for any n ∈ Z +

k∈[K] h∈[H]
Proof. We focus on the case of β > 0; the case for β < 0 follows a similar argument. We denote the shorthand ϑ := log(2HSAK/δ where L s,a := I{∃i ∈ [M h,n ] : κ(s, a, j) = k i }. Then we can also get an upper bound on the second term as where step (i) follows from (s,a)∈S×A L s,a = M h,n . For the third term, by rearranging the order of summations and taking advantage of the fact that Due to the design of the MDPs, ∆ h (s, a; τ h−1 ) = 0 for any h ≥ 2 and τ h−1 . For state s 1 , the minimal sub-optimality gap is therefore given by ∆ 1 (s 1 , a) := ∆ 1 (s 1 , a; τ 0 ) = 1 |β| (e β·V * 1 (s1) − e β·Q * 1 (s1,a) ) for some action a, which it is by design determined by a and the randomness of the environment. More specifically, ∆ 1 (s, a) = 0 if it takes the optimal action a = a * and the only non-zero sub-optimality gap is given by the action a = a ′ that takes the sub-optimal arm a ′ , i.e., where step (i) follows from Lattimore & Szepesvári (2020, Lemma 15.1), step (ii) follows from E p [ k∈ [K] I{a k = a ′ }] ≤ K and the definition of Kullback-Leibler (kl) divergence, step (iii) follows from log(1 + x) ≤ x, and step (iv) follows from |p 2 − q 2 | = 2ξ and p 2 ≤ q 2 ≤ 1 2 for β > 0 and 1 2 p 2 ≤ q 2 ≤ p 2 ≤ 1 2 for β < 0.
Proof. Recall that d dx log x = 1 x for all x > 0. Especially, d dx log x ≤ 1 for all x ≥ 1 and d dx log x ≤ e |β|H for all x ≥ e −|β|H . The regret can be upper bounded by the corresponding exponential regret as follows: where step (i) follows from the assumption that V k 1 (s) ≥ V π 1 (s) and step (ii) follows from mean value theorem. We provide the proof here for the sake of completeness, and similar proof can be found in Fei et al. (2021a).

Future directions and broad impact.
Given recent advancement in the research of deep neural networks, a promising direction of further research would be to investigate how neural approximation and its generalization properties Min et al., 2021a) would benefit risksensitive RL. Understanding and designing efficient algorithms for risk-sensitive RL in other settings, such as shortest path problems (Min et al., 2021b), off-policy evaluation (Min et al., 2021c) and offline learning (Chen et al., 2021b), may also be of great interest. Moreover, as risk-sensitive RL is closely related to human learning and behaviors, it would be intriguing to study how it synthesizes with relevant areas such as meta learning and bio-inspired learning (Song et al., 2021;Xu et al., 2021). Last but not least, exploring how risk sensitivity could be used to augment unsupervised learning algorithms (Fei & Chen, 2018a,b, 2020Ling et al., 2019) would be an important future topic as well.