Year: 2020

Abstract:
We study risk-sensitive reinforcement learning with the entropic risk measure and function approximation. We consider the finite-horizon episodic MDP setting, and propose a meta algorithm based on value iteration. We then derive two algorithms for linear and general function approximation, namely RSVI.L and RSVI.G, respectively, as special instances of the meta algorithm. We illustrate that the success of RSVI.L depends crucially on carefully designed feature mapping and regularization that adapt to risk sensitivity. In addition, both RSVI.L and RSVI.G maintain risk-sensitive optimism that facilitates efficient exploration. On the analytic side, we provide regret analysis for the algorithms by developing a meta analytic framework, at the core of which is a risk-sensitive optimism condition. We show that any instance of the meta algorithm that satisfies the condition yields a meta regret bound. We further verify the condition for RSVI.L and RSVI.G under respective function approximation settings to obtain concrete regret bounds that scale sublinearly in the number of episodes.

heading: 1 INTRODUCTION
text: Risk is one of the most important considerations in decision making, so should it be in reinforcement learning (RL). As a prominent paradigm in RL that performs learning while accounting for risk, risksensitive RL explicitly models risk of decisions via certain risk measures and optimizes for rewards simultaneously. It is poised to play an essential role in application domains where accounting for risk in decision making is crucial. A partial list of such domains includes autonomous driving (Buehler et al., 2009; Thrun, 2010), behavior modeling (Niv et al., 2012; Shen et al., 2014), realtime strategy games (Berner et al., 2019; Vinyals et al., 2019) and robotic surgery (Fagogenis et al., 2019; Shademan et al., 2016).
In this paper, we study risk-sensitive RL through the lens of function approximation, which is an important apparatus for scaling up and accelerating RL algorithms in applications of high dimension. We focus on risk-sensitive RL with the entropic risk measure, a classical framework established by the seminal work of Howard & Matheson (1972). Informally, for a fixed risk parameter β 6= 0, our goal is to maximize the objective
Vβ = 1
β log{EeβR}. (1)
The definition of Vβ will be made formal later in (2). The objective (1) admits a Taylor expansion Vβ = E[R] + β2 Var(R) + O(β
2). Comparing (1) with the risk-neutral objective V = E[R] studied in the standard RL setting, we see that β > 0 induces a risk-seeking objective and β < 0 induces a risk-averse one. Therefore, the formulation with the entropic risk measure in (1) accounts for both risk-seeking and risk-averse modes of decision making, whereas most others are restricted to the risk-averse setting (Fu et al., 2018). It can also be seen that Vβ tends to the risk-neutral V as β → 0. Existing works on function approximation for RL have mostly focused on the risk-neutral setting and heavily exploits the linearity of risk-neutral objective V in both transition dynamics (implicitly captured by the expectation) and the reward R, which is clearly not available in the risk-sensitive objective (1). It is also well known that even in the risk-neutral setting, improperly implemented function approximation could result in errors that scale exponentially in the size of the state space.
Combined with nonlinearity of the risk-sensitive objective (1), it compounds the difficulties of implementing function approximation in risk-sensitive RL with provable guarantees.
This work provides a principled solution to function approximation in risk-sensitive RL by overcoming the above difficulties. Under the finite-horizon MDP setting, we propose a meta algorithm based on value iteration, and from that we derive two concrete algorithms for linear and general function approximation, which we name RSVI.L and RSVI.G, respectively. By modeling a shifted exponential transformation of estimated value functions, RSVI.L and RSVI.G cater to the nonlinearity of the risk-sensitive objective (1) and adapt to both risk-seeking and risk-averse settings. Moreover, both RSVI.L and RSVI.G maintain risk-sensitive optimism in the face of uncertainty for effective exploration. In particular, RSVI.L exploits a synergistic relationship between feature mapping and regularization in a risk-sensitive fashion. The resulting structure of RSVI.L makes it more efficient in runtime and memory than RSVI.G under linear function approximation, while RSVI.G is more general and allows for function approximation beyond the linear setting.
Furthermore, we develop a meta regret analytic framework and identify a risk-sensitive optimism condition that serves as the core component of the framework. Under the optimism condition, we prove a meta regret bound incurred by any instance of the meta algorithm, regardless of function approximation settings. Furthermore, we show that both RSVI.L and RSVI.G satisfy the optimism condition under the respective function approximation and achieve regret that scales sublinearly in the number of episodes. The meta framework therefore helps us disentangle the analysis associated with function approximation from the generic analysis, shedding light on the role of function approximation in regret guarantees. We hope that our meta framework will motivate and benefit future studies of function approximation in risk-sensitive RL.
Our contributions. We may summarize the contributions of the present paper as follows:
• we study function approximation in risk-sensitive RL with the entropic risk measure; we provide a meta algorithm, from which we derive two concrete algorithms for linear and general function approximation, respectively; the concrete algorithms are both shown to adapt to all levels of risk sensitivity and maintain risk-sensitive optimism over the learning process;
• we develop a meta regret analytic framework and identify a risk-sensitive optimism condition, under which we prove a meta regret bound for the meta algorithm; furthermore, by showing that the optimism condition holds for both concrete algorithms, we establish regret bounds for them under linear and general function approximation, respectively.
Notations. For a positive integer n, we let [n] := {1, 2, . . . , n}. For a number u 6= 0, we define sign(u) = 1 if u > 0 and −1 if u < 0. 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 any ε > 0 and set X , we letNε(X , ‖ · ‖) be the ε-net of the set X with respect to the norm ‖ · ‖. We let ∆(X ) be the set of probability distributions supported on X . For any vector u ∈ Rn and symmetric and positive definite matrix Γ ∈ Rn×n, we let ‖u‖Γ := √ u>Γu. We denote by In the n × n identity matrix.

heading: 2 RELATED WORK
text: Initiated by the seminal work of Howard & Matheson (1972), risk-sensitive control/RL with the entropic risk measure has been studied in a vast body of literature (Bäuerle & Rieder, 2014; Borkar, 2001; 2002; 2010; Borkar & Meyn, 2002; Cavazos-Cadena & Hernández-Hernández, 2011; Coraluppi & Marcus, 1999; Di Masi & Stettner, 1999; 2000; 2007; Fleming & McEneaney, 1995; Hernández-Hernández & Marcus, 1996; Jaśkiewicz, 2007; Marcus et al., 1997; Mihatsch & Neuneier, 2002; Osogami, 2012; Patek, 2001; Shen et al., 2013; 2014; Whittle, 1990). Yet, this line of works either assumes known transition kernels or focuses on asymptotic behaviors of the problem/algorithms, and finite-sample/time results with unknown transitions have rarely been investigated.
The most relevant work to ours is perhaps Fei et al. (2020), who consider the same problem as ours under the tabular setting. They propose two algorithms based on value iteration and Q-learning. They prove regret bounds for their algorithms, which are then certified to be nearly optimal by a lower bound. However, their algorithms and analysis are restricted to the tabular setting. Compared to Fei et al. (2020), our paper provides a novel and unified framework of algorithms and analysis for function approximation. We study linear and general function approximation as two instances of the framework, both of which subsume the tabular setting.
We also briefly discuss existing works on function approximation with regret analysis, which so far have focused on the risk-neutral setting. The works of Cai et al. (2019); Jin et al. (2019); Wang et al. (2019); Yang & Wang (2019); Zhou et al. (2020) study linear function approximation, while Ayoub et al. (2020); Wang et al. (2020) investigate general function approximation. In addition, all these works prove Õ(K1/2)-regret for their algorithms, although dependence on other parameters varies in settings. As we have argued in the previous section, the nonlinear objective (1) makes algorithm design and regret analysis for function approximation much more challenging in risksensitive settings than in the standard risk-neutral one.

heading: 3 PROBLEM FORMULATION

heading: 3.1 EPISODIC MDP
text: An episodic MDP is parameterized by a tuple (K,H,S,A, {Ph}h∈[H], {rh}h∈[H]), where K is the number of episodes, H is the number of steps in each episode, S is the state space, A is the action space, Ph : S ×A → ∆(S) is the transition kernel at step h, and rh : S ×A → [0, 1] is the reward function at step h. We assume that {Ph} are unknown. For simplicity we also assume that {rh} are known and deterministic, as is done in existing works such as Yang & Wang (2019); Zhou et al. (2020).
We interact with the episodic MDP as follows. In the beginning of each episode k ∈ [K], the environment chooses an arbitrary initial state sk1 ∈ S . Then in each step h ∈ [H], we take an action akh ∈ A, receives a reward rh(skh, akh) and transitions to the next state skh+1 ∈ S sampled from Ph(· | skh, akh). Once we reach skH+1, the current episode terminates and we advance to the next episode unless k = K.

heading: 3.2 VALUE FUNCTIONS, BELLMAN EQUATIONS AND REGRET
text: We assume that β is fixed prior to the learning process, and for notational simplicity we omit it from quantities to be introduced subsequently. In risk-sensitive RL with the entropic risk measure, we aim to find a policy π = {πh : S → A} so as to maximize the value function given by
V πh (s) := 1
β log
{ E [ exp ( β
H∑ h′=h rh′(sh′ , πh′(sh′)) )] ∣∣∣∣∣ sh = s } , (2)
for all (h, s) ∈ [H] × S. Under some mild regularity conditions, there exists a greedy policy π∗ = {π∗h} which gives the optimal value V π ∗ h (s) = supπ V π h (s) for all (h, s) ∈ [H]× S (Bäuerle & Rieder, 2014). In addition to the value function, another key notion is the action-value function defined as
Qπh(s, a) := 1
β log
{ E [ exp ( β
H∑ h′=h rh′(sh′ , ah′) )∣∣∣∣∣ sh = s, ah = a ]} , (3)
for all (h, s, a) ∈ [H]× S ×A. The action-value function Qπh is closely associated with the value function V π h via the so-called Bellman equation:
Qπh(s, a) = rh(s, a) + 1 β log { Es′∼Ph(· | s,a) [ exp ( β · V πh+1(s′) )]} , (4)
V πh (s) = Q π h(s, πh(s)), V π H+1(s) = 0,
which holds for all (h, s, a) ∈ [H]× S ×A. Note that the identity of Qπh in (4) is a result of simple calculation based on (2) and (3). Similarly, the Bellman optimality equation is given by
Q∗h(s, a) = rh(s, a) + 1 β log { Es′∼Ph(· | s,a) [ exp ( β · V ∗h+1(s′) )]} , (5)
V ∗h (s) = max a∈A Q∗h(s, a), V ∗ H+1(s) = 0,
again for all (h, s, a) ∈ [H] × S × A. In the above, we use the shorthand Q∗h(·, ·) := Qπ ∗
h (·, ·) for all h ∈ [H] and V ∗h (·) is similarly defined. The identity V ∗h (·) = maxa∈AQ∗h(·, a) implies that the optimal π∗ is the greedy policy with respect to the optimal action-value function {Q∗h}h∈[H].
During the learning process, the policy πk in each episode k may be different from the optimal π∗. We quantify this difference over all K episodes through the notion of regret, defined as
Regret(K) := ∑ k∈[K] [ V ∗1 (s k 1)− V π k 1 (s k 1) ] . (6)
Since V ∗1 (s) ≥ V π1 (s) for any π and s ∈ S by definition, regret also characterizes the suboptimality of {πk} relative to the optimal π∗.

heading: 3.3 FUNCTION APPROXIMATION
text: In this paper, we focus on linear and general function approximation. We consider the following form of linear function approximation, which assumes that each transition kernel admits a linear form.
Assumption 1 We assume that the MDP is equipped with a known feature function ψ : S×A×S → Rd such that for any h ∈ [H], there exists a vector θh ∈ Rd with ‖θh‖2 ≤ √ d and the transition kernel is given by Ph(s
′ | s, a) = ψ(s, a, s′)>θh for any (s, a, s′) ∈ S ×A× S. We also assume that∥∥∥ ∫
S ψ(s, a, s′) · (eβ·V (s
′) − 1)ds′ ∥∥∥ 2 ≤ √ d · ∣∣eβv̄ − 1∣∣ ,
for any (s, a) ∈ S ×A and V : S → [0, v̄] where v̄ ≥ 0.
This form of linear function approximation is also studied in the work of Ayoub et al. (2020); Cai et al. (2019); Zhou et al. (2020), whose setting is equivalent to ours when β → 0. The setting of Assumption 1 may be reduced to the tabular setting in which ψ(s, a, s′) is a canonical basis vector in Rd with d = |S|2 |A|, i.e., the (s, a, s′)-th entry of ψ(s, a, s′) is equal to one and the other entries are equal to zero. It also subsumes various settings of function approximation including linear combinations of base models (Modi et al., 2020) and the matrix bandit setting (Yang & Wang, 2019); we refer readers to (Zhou et al., 2020) for more details on the generality of Assumption 1.
For general function approximation, we make the following assumption.
Assumption 2 We assume that we have access to a function set1 P such that the transition kernel Ph ∈ P for all h ∈ [H].
This setting is also considered in Ayoub et al. (2020). Under Assumption 2, we may measure the complexity of function sets using the notion of the so-called eluder dimension (Russo & Van Roy, 2014), which we define and discuss in Appendix A.
Note that although we focus on function approximation of transition kernels, a similar approach can be taken to apply function approximation to reward functions and our regret guarantees presented below would still hold, as argued in Yang & Wang (2019).
1Throughout the paper, we use function class and function set interchangeably.

heading: 4 ALGORITHMS
text: We first present the Meta algorithm for Risk-Sensitive Value Iteration (MetaRSVI) in Algorithm 1, which is a high-level framework including key features of algorithms based on value iteration (Bradtke & Barto, 1996; Osband et al., 2014; Jin et al., 2019). It mainly consists of a value estimation step and policy execution step. In the value estimation step, the algorithm estimates the optimal {Q∗h} by its iterates {Qkh} based on historical data. Since we focus on greedy policies, in Line 5 the estimated value function V kh (·) is simply taken as the maximum among {Qkh(·, a′)}a′∈A. The primary machinery of value estimation, known as Risk-Sensitive Temporal Difference or RSTD, is presented in an abstract way in Line 4; this is because its concrete form would depend on function approximation of the underlying MDP and algorithmic implementation. In the policy execution step, the algorithm uses the policy learned so far (represented by {Qkh}) to collect data for subsequent learning stages. We remark that Algorithm 1 is flexible and general enough to allow for any function approximation. In the remaining of this section, we derive two special instances of Algorithm 1 for linear and general function approximation, respectively, by providing concrete implementation of RSTD.
Algorithm 1 MetaRSVI Input: risk parameter β, number of episodes K
1: for episode k = 1, . . . ,K do 2: V kH+1(·)← 0 3: for step h = H,H − 1, . . . , 1 do . value estimation 4: Qkh(·, ·)← RSTD(k, h, β, {V τh+1}τ∈[k]) 5: V kh (·)← maxa′∈AQkh(·, a′) 6: end for 7: Receive the initial state sk1 from the environment 8: for step h = 1, 2, . . . ,H do . policy execution 9: Take action akh ← argmaxa′∈AQkh(skh, a′)
10: Receive the reward rh(skh, a k h) and the next state s k h+1 11: end for 12: end for
We introduce Risk-Sensitive Value Iteration for Linear function approximation, or RSVI.L, in Algorithm 2 under the setting of Assumption 1. This algorithm is inspired by RSVI proposed in Fei et al. (2020) that specializes in the tabular setting. It replaces the abstract function RSTD in Algorithm 1 with a concrete implementation for the linear function approximation. In Line 4 the iterate wkh can be interpreted as the solution of the following least-squares problem:
wkh ← argmin w∈Rd ∑ τ∈[k−1] [eβ·V τ h+1(s τ h+1) − 1− w>φτh(sτh, aτh)]2 + λ‖w‖22, (7)
where the surrogate feature mappings {φτh(·, ·)}τ∈[k−1] are constructed in Line 5 and λ ≥ 0 is the regularization parameter to be set by users. The above regression problem essentially computes an estimate of θh, the parameter of the transition kernel Ph, by taking advantage of the linear form Es′∼Ph(· | s,a)[e β·V πh+1(s ′)] in the Bellman equation (4). Note that the regression targets are set as a shifted exponential transformation of estimated value functions, i.e., {eβ·V τ h+1(s τ h+1) − 1}. Similar construction is applied to the surrogate features φkh(·, ·) in Line 5. Mechanically, such design ensures that when V kh+1(·) = 0, we would have φkh(·, ·) = 0 and therefore by definition Qkh(·, ·) = rh(·, ·); this is a similar behavior exhibited by risk-neutral algorithms for linear function approximation, e.g., Algorithm 1 in Cai et al. (2019) whose surrogate features are given by replacing eβ·V k h+1(·) − 1 in Line 5 with V kh+1(·). To update Qkh(·, ·) in Line 7, we use the quantity
qkh,L(·, ·) := { min{eβ(H−h), 〈 φkh(·, ·), wkh 〉 + 1 + bkh(·, ·)}, if β > 0,
max{eβ(H−h), 〈 φkh(·, ·), wkh 〉 + 1− bkh(·, ·)}, if β < 0.
(8)
Informally, with bkh taking the role of bonus, q k h,L can be seen as an “optimistic” and risk-adaptive estimate for the expected value of eβ·V k h+1(·) under the (unknown) transition kernel Ph. The term
Algorithm 2 RSVI.L Input: risk parameter β, number of episodes K, bonus multiplier γL, regularization parameter λ
1: Run Algorithm 1 with RSTD() therein overloaded by the following subroutine: 2: procedure RSTD(k, h, β, {V τh+1}τ∈[k], γL, λ) 3: Λkh ← ∑ τ∈[k−1] φ τ h(s τ h, a τ h)φ τ h(s τ h, a τ h) > + λId
4: wkh ← (Λkh)−1 ∑ τ∈[k−1] φ τ h(s τ h, a τ h) · (eβ·V τ h+1(s τ h+1) − 1)
5: φkh(·, ·)← ∫ S ψ(·, ·, s ′) · (eβ·V k h+1(s
′) − 1)ds′ 6: bkh(·, ·)← γL · [φkh(·, ·)>(Λkh)−1φkh(·, ·)]1/2 7: return Qkh(·, ·)← rh(·, ·) + 1β log(q k h,L(·, ·)), where qkh,L(·, ·) is defined in (8) 8: end procedure
〈 φkh(·, ·), wkh 〉 + 1 serves as a correction of the shifted quantity eβ·V k h+1(·) − 1 in both φkh(·, ·) and wkh, so as to align the structure of Line 7 to that of the Bellman equation (4). A proper definition of bonus bkh (with γL therein formally given in Theorem 2 below) and the truncation at e
β(H−h) would put qkh,L within [1, e
β(H−h)] entrywise. This ensures that the estimate Qkh(·, ·) is on the same scale as the optimal Q∗h(·, ·) ∈ [0, H − h+ 1]. We note that there is a significant difference between Algorithm 2 and RSVI introduced in Fei et al. (2020). Since RSVI is designed only for the tabular setting, it suffices to set λ = 0 and update the entries in Qkh whose corresponding state-action pairs have been visited in the history. In the linear setting, however, the entire Qkh is updated at once and it’s imperative to prevent the singularity of the covariance matrix Λkh. This boils down to having a proper choice of the regularization parameter λ. If λ is too small, Λkh would be nearly singular; if λ is too large, the spectrum of Λ k h would be dominated by λ for prohibitively many episodes with the algorithm making little progress in learning. Intuitively, since ‖φτh(·, ·)‖2 ∝ |eβH − 1|, an ideal λ should depend on β and be on the order of (eβH − 1)2, so that the spectrums of the matrices φτh(·, ·)φτh(·, ·)> and λId are close. Indeed, this intuition provides guidance to our choice of λ (see Theorem 2). Our Algorithm 2 hence demonstrates a synergistic relationship between the surrogate features and regularization in a risksensitive fashion. This is in great contrast with existing algorithms for linear function approximation in the risk-neutral setting, such as Cai et al. (2019); Zhou et al. (2020), in which the design of surrogate features and choice of regularization are decoupled.
For general function approximation under Assumption 2, we present Risk-Sensitive Value Iteration for General function approximation, abbreviated as RSVI.G, in Algorithm 3 of Appendix B. Despite their apparent difference, Algorithms 2 and 3 both implement the principle of Risk-Sensitive Optimism in the Face of Uncertainty (RS-OFU) (Fei et al., 2020), by adding bonus/maximizing over the confidence set when β > 0, and subtracting bonus/minimizing over the confidence set when β < 0. Such mechanism encourages the algorithms to explore actions that may have rarely been taken due to low estimated Q-values, while accounting for risk sensitivity at the same time.2

heading: 5 MAIN RESULTS
text: In this section, we present regret guarantees for our algorithms via a meta regret framework. We identify a risk-sensitive optimism condition, which certifies a certain form of optimism of an algorithm. Under the condition, we first provide a meta regret bound for Algorithm 1. We then instantiate the meta regret bound for Algorithms 2 and 3 under Assumptions 1 and 2, respectively.

heading: 5.1 META REGRET BOUND
text: Recall the iterates {Qkh} in Algorithm 1. For each tuple (k, h, s, a) ∈ [K] × [H] × S × A, we define Q k
h(s, a) := rh(s, a) + 1 β log{Es′∼Ph(· | s,a)e β·V kh+1(s ′)}. It can be seen that {Qkh} are the
2We also discuss computational aspects of our algorithms; see Appendix B.
ideal counterparts of {Qkh} that could be constructed if the transition kernels {Ph} were known. We set forth the following condition, which is the central component of our meta regret framework.
Condition 1 For all (k, h, s, a) ∈ [K] × [H] × S × A, we have Qkh(s, a) ∈ [0, H − h + 1], and there exist some quantities mkh(s, a) > 0, g ≥ 1 and universal constant c > 0 such that
0 ≤ Qkh(s, a)−Q k h(s, a) ≤ c · e|β|H − 1 |β| · g ·mkh(s, a).
Since {Qkh} are informally “optimistic” estimates of the ideal {Q k
h}, the difference Qkh(s, a) − Q k
h(s, a) in Condition 1 may be thought of as the level of optimism maintained by the algorithm for state-action pair (s, a) in step h of episode k, with its upper bound depending on risk sensitivity through the factor e
|β|H−1 |β| . Therefore, we say that Condition 1 is a risk-sensitive optimism condition.
In the upper bound of the condition, the actual values of g and mkh(s, a) may depend on function approximation and implementation of the abstract function RSTD. Let us recall that {(skh, akh)} are the state-action pairs visited by Algorithm 1, and we are ready to state the meta regret bound.
Theorem 1 Let M := g ∑ k∈[K] ∑ h∈[H] min{1,mkh(skh, akh)}, where g and {mkh} are as given in Condition 1. On the event of Condition 1, for any δ ∈ (0, 1], with probability at least 1−δ the regret of Algorithm 1 satisfies
Regret(K) . e|β|H − 1 |β| e|β|H 2
M + e|β|H 2√ KH3 log(1/δ).
The proof is given in Appendix D. Even though the actual form of M depends on specific function approximation, the derivation of Theorem 1 only requires the structure of Algorithm 1, which is agnostic of function approximation. In the above bound, the first term can be interpreted as the total optimism maintained by Algorithm 1, and is in fact a direct consequence of Condition 1. The second term can be seen as the total drift of iterates {V kh } from the value functions {V πk h }, which is the result of a martingale analysis. The factor e|β|H 2
shared by both terms is due to a local linearization of the nonlinear objective (2) as well as a standard backward induction analysis ofH-horizon MDPs. Soon we will show that M = Õ(K1/2) under both linear and general function approximation, so the first term in Theorem 1 would dominate in the regret bound. Similar to M , the exponential factor e
|β|H−1 |β| also comes into the bound from Condition 1. It has been shown as a distinctive
feature of risk-sensitive RL algorithms that represents a tradeoff between risk sensitivity and sample complexity; see Fei et al. (2020) for a detailed discussion on this point.

heading: 5.2 REGRET BOUND FOR LINEAR FUNCTION APPROXIMATION
text: We now present a regret bound for Algorithm 2 induced by Theorem 1. Let γL = cγ |eβH − 1| √ d log(2dKH/δ), (9)
where cγ > 0 is an appropriate universal constant. We have the following result.
Theorem 2 Let γL of (9) and λ = (eβH − 1)2 be input to Algorithm 2, and M be as defined in Theorem 1. Under Assumption 1, for any δ ∈ (0, 1], with probability at least 1 − δ, Condition 1 holds for Algorithm 2 so that M . [d2KH2 log2(2dKH/δ)]1/2. Therefore, Theorem 1 implies that the regret of Algorithm 2 satisfies
Regret(K) . e|β|H − 1 |β|
e|β|H 2 √ d2KH2 log2(2dKH/δ).
The proof is given in Appendix E. One may obtain a regret bound for the tabular setting by taking d = |S|2 |A| in Theorem 2, and the resulting bound can be seen to nearly match that of Fei et al. (2020, Theorem 1), except for the polynomial dependency on |S| and |A|.3 The bound obtained
3By inspecting the proof of Fei et al. (2020, Theorem 1), we see that they apply the bound (1/|β|)(exp(|β|H)− 1) exp(|β|H2) ≤ (1/|β|)(exp(C |β|H2)− 1) for some universal constant C > 0.
from specializing Theorem 2 to the tabular setting is also nearly optimal for small |β| (with respect to |β|, K and H) in view of the lower bound
E [Regret(K)] & e|β|H/2 − 1 |β|
√ K logK (10)
given by Fei et al. (2020, Theorem 3). In addition, as β → 0, the setting of risk-sensitive RL tends to that of standard risk-neutral RL. We have the following corollary as a precise characterization of Theorem 2 in that regime.
Corollary 1 Under the setting of Theorem 2 and when β → 0, with probability at least 1 − δ, the regret of Algorithm 2 satisfies
Regret(K) . √ d2KH4 log2(2dKH/δ).
The proof is given in Appendix F. Corollary 1 matches the standard result in the risk-neutral setting, e.g. Cai et al. (2019, Theorem 3.1), up to logarithmic factors.

heading: 5.3 REGRET BOUND FOR GENERAL FUNCTION APPROXIMATION
text: To present the regret guarantee for general function approximation, we need to set a few additional notations. Recall the function set P from Assumption 2. For any P ∈ P , (s, a) ∈ S × A and V : S → [0, H], we define the function set
Z := {zP : P ∈ P}, where zP (s, a, V ) := sign(β) ∫ S P (s′ | s, a) · (eβ·V (s ′) − 1)ds′, (11)
For any P, P ′ ∈ P , we define ‖P − P ′‖∞,1 := sup(s,a)∈S×A ‖P (· | s, a)− P ′(· | s, a)‖1. We let
dE := dimE(Z, |eβH − 1|/K)
be the (|eβH − 1|/K)-eluder dimension of function set Z ,4 and
ζ := log ( H · N1/K(P, ‖ · ‖∞,1)/δ ) + √ log(4K2H/δ). (12)
In Algorithm 3, we set γG = 10|eβH − 1| √ ζ. (13)
We now state our result for Algorithm 3, which is another instantiation of Theorem 1.
Theorem 3 Let γG of (13) be input to Algorithm 3 and M be as defined in Theorem 1. Under Assumption 2, for any δ ∈ (0, 1], with probability at least 1 − δ, Condition 1 holds for Algorithm 3 so that M . H min{dE ,K} + √ dEKH2ζ. Therefore, Theorem 1 implies that the regret of Algorithm 3 satisfies
Regret(K) . e|β|H − 1 |β|
e|β|H 2 ( H min{dE ,K}+ √ dEKH2ζ ) .
The proof is given in Appendix G. The term H min{dE ,K} above also appears in the regret bound for the multi-arm bandit problem with general function approximation (Russo & Van Roy, 2014), which is a special case of our finite-horizon episodic MDP setting. When K is sufficiently large, we have H min{dE ,K} . √ dEKH2ζ and therefore Theorem 3 yields Regret(K) = e|β|H−1 |β| e |β|H2Õ( √ dEKH2). In case that the transition kernels in P take the linear form as in Assumption 1, we have dE . d logK, and log(N1/K(P, ‖ · ‖∞,1)) . d logK so that ζ . d log(KH/δ). Then for sufficiently large K, the bound in Theorem 3 matches that in Theorem 2 up to a logarithmic factor. On the other hand, under the linear setting of Assumption 1, Algorithm 2 may be more efficient in runtime and memory than Algorithm 3, as discussed in Appendix B.
4Recall that the definition of the eluder dimension is formally given in Appendix A.

heading: A ELUDER DIMENSION
text: To introduce the eluder dimension, we need to set forth the concept of ε-independence.
Definition 1 For any ε > 0 and function set G whose elements are in the domain X , we say that an x ∈ X is ε-dependent on the set of elements Xn := {x1, x2, . . . , xn} ⊂ X with respect to G if any pair of functions g, g′ ∈ G satisfying ∑ i∈[n](g(xi)− g′(xi))2 ≤ ε2 also satisfies g(x)− g′(x) ≤ ε. We say that x is ε-independent of Xn with respect to G if x is not ε-dependent on Xn with respect to G.
Hence, ε-independence characterizes a notion of dissimilarity of a point x to the elements in subset Xn of function set G. Now we are ready to formally define the eluder dimension, which quantifies the length of the longest possible chain of dissimilar elements in a function set.
Definition 2 For any ε > 0 and function set G whose elements are in the domain X , the ε-eluder dimension dimE(G, ε) is defined as the length d′ of the longest sequence of elements in X such that, for some ε′ ≥ ε, every element is ε′-independent of its predecessors.
The eluder dimension extends the concept of dimension in linear spaces and generalizes to nonlinear function spaces. It is also related to the notions of Kolmogorov dimension and VC dimension. We refer readers to Russo & Van Roy (2014) for further details on the eluder dimension and its advantages compared to other complexity measures.

heading: B MORE ON ALGORITHMS
text: We present details of Algorithm 3 that we have omitted from the main text. For each (k, h) ∈ [K] × [H], transition kernels P, P ′ ∈ P and estimated value functions {V τh+1}τ∈[k−1], we define the squared error
Γkh(P, P ′) := k−1∑ τ=1 (∫ S P (s′ | sτh, aτh)eβ·V τ h+1(s ′)ds′ − ∫ S P ′(s′ | sτh, aτh)eβ·V τ h+1(s ′)ds′ )2 . (14)
In Algorithm 3, Line 3 computes an estimate P kh of the transition kernel Ph, by solving a leastsquares problem similar to (7). Line 4 then constructs a confidence set around the estimate P kh . This step is reminiscent of UCRL (Jaksch et al., 2010), where confidence sets are used to enforce the so-called Optimism in the Face of Uncertainty (OFU) principle for efficient exploration. Line 5 updates Qkh by solving an optimization problem over the confidence set Pkh with the definition
qkh,G(·, ·) :=
{ maxP∈Pkh ∫ S P (s ′ | ·, ·)eβ·V k h+1(s ′)ds′, if β > 0,
minP∈Pkh ∫ S P (s ′ | ·, ·)eβ·V k h+1(s ′)ds′, if β < 0. (15)
It is worth remarking that both Lines 3 and 4 implicitly operate with the shifted exponential transformation of estimated value functions: replacing eβ·V τ h+1(·) therein by eβ·V τ h+1(·) − 1 would not result in any difference for the algorithm.
Computational aspects. We briefly discuss computational aspects of Algorithms 2 and 3. It is not hard to see that the time and space complexities for Algorithm 2 are polynomial in key model parameters d,K andH . For Algorithm 3, it is unclear how the complexities scale under Assumption 2, where the structure of P is unknown. Nevertheless, under Assumption 1 in which the transition
Algorithm 3 RSVI.G Input: risk parameter β, number of episodes K, confidence width γG, function set P
1: Run Algorithm 1 with RSTD() therein overloaded by the following subroutine: 2: procedure RSTD(k, h, β, {V τh+1}τ∈[k], γG, P) 3: P kh ← argminP∈P ∑k−1 τ=1(e β·V τh+1(s τ h+1) − ∫ S P (s ′ | sτh, aτh)eβ·V τ h+1(s ′)ds′)2 4: Pkh ← {P ∈ P : Γkh(P, P kh ) ≤ γ2G}, where Γkh(·, ·) is defined in (14) 5: return Qkh(·, ·)← rh(·, ·) + 1β log(q k h,G(·, ·)), where qkh,G(·, ·) is defined in (15) 6: end procedure
kernels admit a linear form, Algorithm 3 also attains polynomial time and space complexities with respect to key model parameters. The actual runtime and memory consumption of Algorithm 3 may be higher than those of Algorithm 2 though, since the construction of confidence sets in Algorithm 3 requires solving linear programs which could be computationally cumbersome.

heading: C PRELIMINARIES TO PROOFS
text: We fix a tuple (k, h, s, a) ∈ [K]× [H]× S ×A and a policy π. For Algorithm 1 (which subsumes both Algorithms 2 and 3), define
q2 = q k h,2(s, a) := Es′∼Ph(· | s,a)e
β·V kh+1(s ′), (16)
and q3 = q k h,3(s, a) := Es′∼Ph(· | s,a)e β·V πh+1(s ′). (17)
In the above definitions, note that q2 and q3 depend on (k, h, s, a); we suppress such dependency for notational simplicity. We have the following bounds on q2 and q3.
Lemma 1 We have q2, q3 ∈ [min{1, eβ(H−h)},max{1, eβ(H−h)}].
Proof. The result for q2 and q3 can be seen if we recall their definitions and the fact that eβ·V (·) ∈ [min{1, eβ(H−h)},max{1, eβ(H−h)}] for any V : S → [0, H − h].
For any q′ > 0, define
G1(q ′) :=
1 β log{q′} − 1 β log{q2},
G2 := 1
β log{q2} −
1 β log{q3}.
(18)
Since q2, q3 > 0 by definition, G1(q′) and G2 are well-defined. By the Bellman equation (4), for any π we have
Qπh(s, a) = rh(s, a) + 1 β log { Es′∼Ph(· | s,a)e β·V πh+1(s ′) } .
We restate Condition 1 in the following.
Condition 2 (Restatement of Condition 1) Let G1(q′) be as defined in (18). For all (k, h, s, a) ∈ [K]× [H]×S×A, assumeQkh(s, a) ∈ [0, H] in Algorithm 1, then there exist some quantities g ≥ 1, mkh = m k h(s, a) > 0, q1 = q k h,1(s, a) ≥ min{1, eβ(H−h)} and universal constant c1 > 0 such that G1(q k h,1(s, a)) = Q k h(s, a)− 1β log{q k h,2(s, a)}, and
0 ≤ G1(qkh,1(s, a)) ≤ c1 · e|β|H − 1 |β| · g ·mkh.
It can be seen that G1(qkh,1(s, a)) = Q k h(s, a)−Q
k h(s, a), where Q k
h is defined in Section 5. Under Condition 2, it holds that
(Qkh −Qπh)(s, a) = 1
β log{q1} −
1 β log{q3} = G1 +G2, (19)
by the construction of Qkh in the algorithms, where we have let G1 := G1(q1). Condition 2 has unspecified quantities q1, {mkh} and g. The condition, along with those quantities therein, will be verified in Lemmas 6 and 11 under Assumptions 1 and 2, respectively.
For now let us focus on G2, and we need the following simple result to control it.
Fact 1 Consider x, y, b ∈ R such that x ≥ y.
(a) if y ≥ g0 for some g0 > 0, then log(x)− log(y) ≤ 1g (x− y);
(b) Assume further that y ≥ 0. If b ≥ 0 and x ≤ u for some u > 0, then ebx − eby ≤ bebu(x− y); if b < 0, then eby − ebx ≤ (−b)(x− y).
Proof. The results follow from Lipschitz continuity of the functions x 7→ log(x) and x 7→ ebx.
We next control G2, whose proof is agnostic of function approximation.
Lemma 2 For each (k, h, s, a) ∈ [K]× [H]× S ×A, if V kh+1(s′) ≥ V πh+1(s′) for all s′ ∈ S , then we have
0 ≤ G2 ≤ e|β|H · Es′∼Ph(· | s,a)[V k h+1(s ′)− V πh+1(s′)].
Proof. Case β > 0. The assumption V kh+1(s′) ≥ V πh+1(s′) for all s′ ∈ S implies that q2 ≥ q3 (by the definitions of q2 and q3 in (16) and (17)) and therefore G2 ≥ 0 by the definition (18). We also have
G2 ≤ 1
β (q2 − q3)
≤ e|β|HEs′∼Ph(· | s,a)[V k h+1(s ′)− V πh+1(s′)], where the first step holds by Fact 1(a) (with g0 = 1, x = q2, and y = q3) and the fact that q2 ≥ q3 ≥ 1 (implied by Lemma 1), and the second step holds by Fact 1(b) (with b = β, x = V kh+1(s), and y = V πh+1(s)) and H ≥ V kh+1(s) ≥ V πh+1(s) ≥ 0.
Case β < 0. The assumption V kh+1(s′) ≥ V πh+1(s′) for all s′ ∈ S implies that q2 ≤ q3 and therefore G2 ≥ 0 due to its definition (18). We also have
G2 = 1
(−β) (log{q3} − log{q2})
≤ e −βH
(−β) (q3 − q2)
≤ e|β|HEs′∼Ph(· | s,a)[V k h+1(s ′)− V πh+1(s′)], where the second step holds by Fact 1(a) (with g0 = eβH , x = q3, and y = q2) and the fact that q3 ≥ q2 ≥ eβH (suggested by Lemma 1), and the third step holds by Fact 1(b) (with b = β, x = V kh+1(s), and y = V π h+1(s)) and V k h+1(s) ≥ V πh+1(s) ≥ 0.
With the help of Lemma (2), we can show the “optimism” of Qkh in the following sense.
Lemma 3 Suppose (19) holds with G1 ≥ 0. We have Qkh(s, a) ≥ Qπh(s, a) for all (k, h, s, a) ∈ [K]× [H]× S ×A.
Proof. For the purpose of the proof, we set QπH+1(s, a) = Q ∗ H+1(s, a) = 0 for all (s, a) ∈ S ×A. We fix a tuple (k, s, a) ∈ [K]×S ×A and use strong induction on h. The base case for h = H + 1 is satisfied since (QkH+1 −QπH+1)(s, a) = 0 for k ∈ [K] by definition. Now we fix an h ∈ [H] and assume that 0 ≤ (Qkh+1 −Qπh+1)(s, a). By the induction assumption we have
V kh+1(s) = max a′∈A Qkh+1(s, a ′) ≥ max a′∈A Qπh+1(s, a ′) ≥ V πh+1(s). (20)
Applying (20) to Lemma 2 yields G2 ≥ 0. Since G1 ≥ 0 by assumption, it follows that (Qkh − Qπh)(s, a) ≥ 0 by (19). The induction is completed and so is the proof.
Lemma 3 implies an immediate but important corollary.
Lemma 4 Suppose (19) holds with G1 ≥ 0. We have V kh (s) ≥ V πh (s) for all (k, h, s) ∈ [K] × [H]× S .
Proof. The result follows from Lemma 3 and Equation (20).
We now have all the keys to proving the meta regret bound.

heading: D PROOF OF THEOREM 1
text: We work on the event of Condition 2 (which is a restatement of Condition 1), where g and {mkh} are defined. This means (19) also holds. Define δkh := V kh (skh) − V π k h (s k h), and ζ k h+1 := Es′∼Ph(· | skh,akh)[V k h+1(s
′) − V πkh+1(s′)] − δkh+1. Let {mkh} be as defined in Condition 2. For any (k, h) ∈ [K]× [H], we have
δkh = (Q k h −Qπ
k
h )(s k h, a k h)
≤ min{H, (Qkh −Qπ k h )(s k h, a k h)} (21) ≤ min { H, c1 ·
e|β|H − 1 |β| · g ·mkh(skh, akh) } + e|β|H · Es′∼Ph(· | skh,akh)[V k h+1(s ′)− V π k h+1(s ′)]
≤ c1 · e|β|H − 1 |β| · g ·min{1,mkh(skh, akh)}+ e|β|H · Es′∼Ph(· | skh,akh)[V k h+1(s ′)− V π k h+1(s ′)]
(22)
= c1 · e|β|H − 1 |β| · g ·min{1,mkh(skh, akh)}+ e|β|H(δkh+1 + ζkh+1). (23)
In the above equation, the first step holds by the construction of Algorithm 1 and the definition of V π k
h in (4); the second step is due to the fact that Q k h(·, ·) ≤ H and Qπ
k
h (·, ·) ≥ 0; the third step holds by (19) combined with Condition 2 and Lemma 2; the fourth step holds since c1, g ≥ 1 and e|β|H−1 |β| ≥ H; the last step follows from the definitions of δ k h and ζ k h+1.
Recalling from Algorithm 1 and the Bellman equation (4) that V kH+1(s) = V πk
H+1(s) = 0, as well as noting the fact that δkh+1 + ζ k h+1 ≥ 0 implied by Lemma 4, we can continue by expanding the recursion in Equation (23) and get
δk1 ≤ ∑ h∈[H] e|β|Hhζkh+1 + c1 · e|β|H − 1 |β| · ∑ h∈[H] e|β|H(h−1)g ·min{1,mkh(skh, akh)}. (24)
Therefore, we have Regret(K) = ∑ k∈[K] [ (V ∗1 − V π k 1 )(s k 1) ] ≤ ∑ k∈[K] δk1
≤ e|β|H 2 ∑ k∈[K] ∑ h∈[H] ζkh+1 + c1 · e|β|H − 1 |β| · e|β|H 2 · g ∑ k∈[K] ∑ h∈[H] min{1,mkh(skh, akh)},
(25)
where the second step holds by Lemma 4 with π therein set to the optimal policy, and in the last step we have applied (24) along with the Holder inequality.
We proceed to control the first term in Equation (25). Since the construction of V kh is independent of the new observation skh in episode k, we have that {ζkh+1} is a martingale difference sequence satisfying ∣∣ζkh∣∣ ≤ 2H for all (k, h) ∈ [K] × [H]. By the Azuma-Hoeffding inequality, we have for any t > 0,
P  ∑ k∈[K] ∑ h∈[H] ζkh+1 ≥ t  ≤ exp(− t2 2T ·H2 ) .
Hence, with probability 1− δ/2, there holds∑ k∈[K] ∑ h∈[H] ζkh+1 ≤ √ 2H2T · log(2/δ). (26)
Finally, plugging (26) into (25) yields
Regret(K) ≤ e|β|H 2√
2H2T · log(2/δ)+c1 · e|β|H − 1 |β| ·e|β|H 2 ·g ∑ k∈[K] ∑ h∈[H] min{1,mkh(skh, akh)}.
We then rescale δ properly and finish the proof of Theorem 1.
To obtain regret bounds for Algorithms 2 and 3, it remains to only specify quantities g and∑ k∈[K] ∑ h∈[H]m k h(s k h, a k h) in Condition 2. The next result prepares us for the quest.
Lemma 5 Let q2 = qkh(s, a) be as defined in (16). If for each (k, h, s, a) ∈ [K] × [H] × S × A, there exists some quantities g ≥ 1, mkh = mkh(s, a) > 0, q1 = qkh,1(s, a) ≥ min{1, eβ(H−h)} and universal constant c1 ≥ 1 such that G1(qkh,1(s, a)) = Qkh(s, a) − 1β log{q k h,2(s, a)}, and 0 ≤
q1 − q2 ≤ c1 ∣∣eβH − 1∣∣ g ·mkh for β > 0 and 0 ≤ q2 − q1 ≤ c1 ∣∣eβH − 1∣∣ g ·mkh for β < 0, then Condition 2 holds with the aforementioned c1, g, mkh and q1.
Proof. Case β > 0. By the definition of G1 in (19), the assumption 0 ≤ q1 − q2 implies that G1 ≥ 0. Moreover, Lemma 1 and Fact 1(a) (with g0 = 1, x = q1 and y = q2) together imply
G1 ≤ 1
β (q1 − q2).
Invoking the upper bound on q1 − q2 for β > 0 in the assumption completes the proof for the case. Case β < 0. By the definition of G1 in 18, the assumption 0 ≤ q2 − q1 implies that G1 ≥ 0. Furthermore, by Lemma 1 and Fact 1(a) (with g0 = eβH , x = q2 and y = q1), we further have
G1 = 1
(−β) (log{q2} − log{q1})
≤ e −βH
|β| (q2 − q1).
Invoking the upper bound on q2 − q1 and the fact that ∣∣eβH − 1∣∣ = 1 − eβH for β < 0 completes the proof for the case.

heading: E PROOF OF THEOREM 2
text: First of all, it can be seen that Line 7 in Algorithm 2 and the initial condition V kH+1(s, a) = 0 in Algorithm 1 ensure that Qkh(s, a) ∈ [0, H − h+ 1] for all (k, h, s, a) ∈ [K]× [H]×S ×A. We let λ = (eβH − 1)2 and γL set as in (9) for Algorithm 2. We define
q+1 = q k,+ h,1 (s, a) :=
{〈 φkh(s, a), w k h 〉 + 1 + bkh(s, a), if β > 0,〈
φkh(s, a), w k h 〉 + 1− bkh(s, a), if β < 0;
(27)
q1 = q k h,1(s, a) := { min{eβ(H−h), q+1 }, if β > 0, max{eβ(H−h), q+1 }, if β < 0.
(28)
Indeed, q1 defined above is equivalent to qkh,L defined in (8). It can also be verified that G1(q1) = Qkh(s, a)− 1β log{q2}, whereG1(·) is defined in (18) and q2 is defined in (16). We have the following result which shows that Algorithm 2 satisfies Condition 2 (a restatement of Condition 1) with high probability.
Lemma 6 Under Assumption 1, for any δ ∈ (0, 1], with probability at least 1−δ, Condition 2 holds for Algorithm 2 with c1 ≥ 1, g = √ d log(2dKH/δ). mkh(s, a) = √ φkh(s, a) >(Λkh) −1φkh(s, a) and q1 as defined in (28).
Proof. Let us fix a tuple (k, h, s, a) ∈ [K]× [H]× S ×A. Then, we have
φkh(s, a) >wkh + 1 = φ k h(s, a) >(Λkh) −1  ∑ τ∈[k−1] φτh(s τ h, a τ h) · [eβ·V τ h+1(s τ h+1) − 1] + 1 (29) by Line 4 of Algorithm 2, and
Es′∼Ph(· | s,a)e β·V kh+1(s ′) = ∫ S ψ(s, a, s′)>θh(e β·V kh+1(s ′) − 1)ds′ + 1
= φkh(s, a) >θh + 1 = φkh(s, a) >(Λkh) −1Λkhθh + 1
= φkh(s, a) >(Λkh) −1  ∑ τ∈[k−1] φτh(s τ h, a τ h)φ τ h(s τ h, a τ h) >θh + λ · θh + 1 = φkh(s, a) >(Λkh) −1  ∑ τ∈[k−1] φτh(s τ h, a τ h) · Es′∼Ph(· | sτh,aτh)[e β·V τh+1(s ′) − 1] + λ · θh + 1, (30)
where the first step follows from Assumption 1, the second step holds by Line 5 of Algorithm 2, the third step holds since Λkh is positive definite by construction, the fourth step holds by Line 3 of Algorithm 2, and the last step holds since
φτh(s, a) >θh = ∫ S ψ(s, a, s′)>θh · (eβ·V τ h+1(s ′) − 1)ds′ = Es′∼Ph(· | s,a)[e β·V τh+1(s ′) − 1]
for τ ∈ [K], which is due to Assumption 1. Now we consider the cases β > 0 and β < 0 separately.
Case β > 0. Recall q+1 defined in (27) and q2 in (16). To control G1, we can compute∣∣q+1 − q2 − bkh(s, a)∣∣ = ∣∣∣φkh(s, a)>wkh + 1− Es′∼Ph(· | s,a)eβ·V kh+1(s′)∣∣∣
= ∣∣∣∣∣φkh(s, a)>(Λkh)−1  ∑ τ∈[k−1] φτh(s τ h, a τ h) · ( eβ·V τ h+1(s τ h+1) − Es′∼Ph(· | sτh,aτh)[e β·V τh+1(s ′)] )
︸ ︷︷ ︸ S1
− λ · φkh(s, a)>(Λkh)−1θh︸ ︷︷ ︸ S2 ∣∣∣∣∣ ≤ |S1|+ |S2| , (31) where the first step holds by the definitions of q+1 and q2, and the second step is implied by (29) and (30). We control each of S1 and S2. For S1, we have
|S1| ≤ ∥∥∥ ∑ τ∈[k−1] φτh(s τ h, a τ h) · (eβ·V τ h+1(s τ h+1)−Es′∼Ph(· | sτh,aτh)e β·V τh+1(s ′)) ∥∥∥ (Λkh) −1 ‖φkh(s, a)‖(Λkh)−1
by the Cauchy-Schwarz inequality. On the event of Lemma 8, we further have |S1| ≤ c ∣∣eβH − 1∣∣√d log(2dKH/δ) · ‖φkh(s, a)‖(Λkh)−1
for some universal constant c > 0. Now for S2, we have
|S2| ≤ λ · ‖φkh(s, a)‖(Λkh)−1 · ‖θh‖(Λkh)−1
≤ √ λ · ‖φkh(s, a)‖(Λkh)−1 · ‖θh‖2 ≤ √ λd · ‖φkh(s, a)‖(Λkh)−1 ,
where the first step holds by the Cauchy-Schwarz inequality, the second step holds since Λkh λ·Id, and the last step holds by Assumption 1 that ‖θh‖2 ≤ √ d. Plugging the bounds on S1 and S2 into (31), and using the fact that λ = (eβH − 1)2 and the definition of bkh, we have∣∣∣φτh(s, a)>wkh + 1− Es′∼Ph(· | s,a)eβ·V kh+1 ∣∣∣ ≤ bkh(s, a). We choose cγ = c+ 1 in the definition of bkh(s, a) in Line 6 of Algorithm 2, and we have
0 ≤ q+1 − q2 ≤ 2cγ︸︷︷︸ c1
· ∣∣eβH − 1∣∣√d log(2dKH/δ)︸ ︷︷ ︸
g
· ‖φkh(s, a)‖(Λkh)−1︸ ︷︷ ︸ mkh(s,a) . (32)
Since (32) implies q+1 ≥ q2 and Lemma 1 implies q2 ≤ eβ(H−h), we can infer that q1 ≥ q2 from the definition of q1 = min{eβ(H−h), q+1 } in (28). Then we have 0 ≤ q1 − q2 ≤ q + 1 − q2. By Lemma 1, we also have q1 ≥ q2 ≥ 1. Case β < 0. Similar to the case of β > 0, we have∣∣q2 − q+1 − bkh(s, a)∣∣ ≤ c · ∣∣eβH − 1∣∣√d log(2dKH/δ) · ‖φkh(s, a)‖(Λkh)−1 . If we choose cγ = c + 1 in the definition of bkh(s, a) in Line 6 of Algorithm 2, the above equation implies
0 ≤ q2 − q+1 ≤ 2cγ︸︷︷︸ c1
· ∣∣eβH − 1∣∣√d log(2dKH/δ)︸ ︷︷ ︸
g
· ‖φkh(s, a)‖(Λkh)−1︸ ︷︷ ︸ mkh(s,a) . (33)
Therefore, using the same reasoning as in the case of β > 0, we have 0 ≤ q2 − q1 ≤ q2 − q+1 . Also, by the definition of q1 in (28), we have q1 ≥ eβ(H−h). The proof is completed by invoking Lemma 5 and recalling the identity ‖φkh(s, a)‖(Λkh)−1 =√ φkh(s, a) >(Λkh) −1φkh(s, a). Next, we give a bound for the quantity ∑ k∈[K] ∑ h∈[H] min{1,mkh(skh, akh)}.
Lemma 7 Under Assumption 1, let {mkh(s, a)} be as defined in Lemma 6 and we have∑ k∈[K] ∑ h∈[H] min{1,mkh(skh, akh)} ≤ √ 2dKH2ι,
where ι = log(2dK/δ).
Proof. We have ∑ k∈[K] ∑ h∈[H] min{1,mkh(skh, akh)}
≤ ∑ h∈[H] √ K √∑ k∈[K] min{1, φkh(skh, akh)>(Λkh)−1φkh(skh, akh)} ≤ H √ 2dKι.
where the first step holds by the Cauchy-Schwarz inequality, and the last step holds by Lemma 10.
Recall the definition of M from Theorem 1, and now its upper bound can be determined by combining Lemmas 6 and 7. Therefore, the proof of the theorem is completed.
E.1 AUXILIARY LEMMAS
We first present a concentration result.
Lemma 8 Let λ = (eβH − 1)2 in Algorithm 2. There exists a universal constant c > 0 such that for any δ ∈ (0, 1] and (k, h) ∈ [K]× [H], with probability 1− δ, we have∥∥∥ ∑ τ∈[k−1] φτh(s τ h, a τ h)·(eβ·V τ h+1(s τ h+1)−Es′∼Ph(· | sτh,aτh)e β·V τh+1(s ′)) ∥∥∥ (Λkh) −1 ≤ c ∣∣eβH − 1∣∣√d log(2dKH/δ) Proof. The proof is adapted from that of Cai et al. (2019, Lemma D.1) by using the fact that for any function V : S → [0, H], we have
sup (s,a,s′′)∈S×A×S ∣∣∣eβ·V (s′′) − Es′∼Ph(· | s,a)eβ·V (s′)∣∣∣ ≤ ∣∣eβH − 1∣∣ , and that Assumption 1 implies
sup (s,a)∈S×A ∥∥∥ ∫ S φ(s, a, s′) · (eβ·V (s ′) − 1)ds′ ∥∥∥ 2 ≤ √ d ∣∣eβH − 1∣∣ .
The next few lemmas can help control the sum of the terms {φkh(skh, akh)>(Λkh)−1φkh(skh, akh)}.
Lemma 9 (Cai et al. (2019, Lemma D.3)) Let {φj}j≥1 be a sequence in Rd. Let Λ0 ∈ Rd×d be a positive-definite matrix and Λt := Λ0 + ∑ j∈[t−1] φjφ
> j . Then for any t ∈ Z>0, we have∑
j∈[t]
min{1, φ>j Λ−1j φj} ≤ 2 log [ det(Λt+1)
det(Λ1)
] .
Lemma 10 Let λ = (eβH − 1)2 in Algorithm 2. For any h ∈ [H], we have∑ k∈[K] min{1, φkh(skh, akh)>(Λkh)−1φkh(skh, akh)} ≤ 2dι,
where ι = log(2dK/δ).
Proof. By construction of Algorithm 2, we may define Λ0h := λId so we have
Λkh = Λ 0 h + ∑ τ∈[k−1] φτh(s τ h, a τ h)φ τ h(s τ h, a τ h) >.
Since ‖φkh(skh, akh)‖2 ≤ √ d ∣∣eβH − 1∣∣ for all (k, h) ∈ [K] × [H] as implied by Assumption 1, we have for any h ∈ [H] that
ΛK+1h = ∑ k∈[K] φkh(s k h, a k h)φ k h(s k h, a k h) > + λId (dK|eβH − 1|2 + λ)Id.
Given λ = ∣∣eβH − 1∣∣2, we have for any h ∈ [H] that
log
[ det(ΛK+1h )
det(Λ1h)
] ≤ d log [ dK ∣∣eβH − 1∣∣2 + λ λ ] ≤ d log[dK + 1] ≤ dι.
We now apply Lemma 9 to get∑ k∈[K] min{1, φkh(skh, akh)>(Λkh)−1φkh(skh, akh)} ≤ 2 log [ det(ΛK+1h ) det(Λ1h) ] ≤ 2dι,
as desired.

heading: F PROOF OF COROLLARY 1
text: The result follows from Theorem 2, as well as the fact that limβ→0 e |β|H−1 |β| = H and limβ→0 e |β|H2 = 1.

heading: G PROOF OF THEOREM 3
text: First of all, it can be seen that Line 5 in Algorithm 3 and the initial condition V kH+1(s, a) = 0 in Algorithm 1 ensure that Qkh(s, a) ∈ [0, H − h+ 1] for all (k, h, s, a) ∈ [K]× [H]×S ×A. We fix a tuple (k, h, s, a) ∈ [K]× [H]× S ×A. Recall that γG is as defined in (13). For Algorithm 3, we let
q1 = q k h,1(s, a) :=
{ maxP∈Pkh ∫ S P (s ′ | s, a)eβ·V k h+1(s ′)ds′, if β > 0,
minP∈Pkh ∫ S P (s ′ | s, a)eβ·V k h+1(s ′)ds′, if β < 0, (34)
which is equivalent to qkh,G(s, a) defined in (15). Recall the definitions of zp and Z in (11). We have the result below, which verifies Condition 2 (a restatement of Condition 1) for Algorithm 3 under the general function approximation.
Lemma 11 Under Assumption 2, for any δ ∈ (0, 1] the following holds with probability at least 1−δ. For all (k, h, s, a) ∈ [K]×[H]×S×A, Condition 2 holds for Algorithm 3 with c1 = 1, g = 1, mkh(s, a) = 1 |eβH−1| [ maxP∈Pkh zP (s, a, V k h+1)−minP∈Pkh zP (s, a, V k h+1) ] and q1 as defined in (34).
Proof. It is not hard to see that by the definition of q1 in (34), we have
q1 ∈ [min{1, eβ(H−h)},max{1, eβ(H−h)}].
Recall the definitions of q2 in (16) and G1(·) in (18); it holds that G1(q1) = Qkh − 1β log{q2}. On the event of Lemma 14, we have Ph ∈ Pkh .
Case β > 0. By definitions of q1 and q2 and the fact that Ph ∈ Pkh , we have q1 ≥ q2. We can also derive
q1 − q2 = max P∈Pkh ∫ S P (s′ | s, a)eβ·V k h+1(s ′)ds′ − ∫ S Ph(s ′ | s, a)eβ·V k h+1(s ′)ds′
≤ max P∈Pkh ∫ S P (s′ | s, a)eβ·V k h+1(s ′)ds′ − min P∈Pkh ∫ S P (s′ | s, a)eβ·V k h+1(s ′)ds′
= max P∈Pkh ∫ S P (s′ | s, a)(eβ·V k h+1(s ′) − 1)ds′ − min P∈Pkh ∫ S P (s′ | s, a)(eβ·V k h+1(s ′) − 1)ds′
= ∣∣eβH − 1∣∣ g ·mkh(s, a),
where the second step holds since Ph ∈ Pkh , and the third step holds since ∫ S P (s ′ | s, a)ds′ = 1.
Case β < 0. By definitions of q1 and q2 and the fact that Ph ∈ Pkh , we may deduce that q1 ≤ q2. Also, we have
q2 − q1 = ∫ S Ph(s ′ | s, a)eβ·V k h+1(s ′)ds′ − min P∈Pkh ∫ S P (s′ | s, a)eβ·V k h+1(s ′)ds′
≤ max P∈Pkh ∫ S P (s′ | s, a)eβ·V k h+1(s ′)ds′ − min P∈Pkh ∫ S P (s′ | s, a)eβ·V k h+1(s ′)ds′
= − min P∈Pkh ∫ S P (s′ | s, a)(−eβ·V k h+1(s ′))ds′ − (−1) max P∈Pkh ∫ S P (s′ | s, a)(−eβ·V k h+1(s ′))ds′
= max P∈Pkh ∫ S P (s′ | s, a)(1− eβ·V k h+1(s ′))ds′ − min P∈Pkh ∫ S P (s′ | s, a)(1− eβ·V k h+1(s ′))ds′
= ∣∣eβH − 1∣∣ g ·mkh(s, a),
where the second step holds since Ph ∈ Pkh , and the fourth step holds since ∫ S P (s
′ | s, a)ds′ = 1. Finally, invoking Lemma 5 completes the proof. The following lemma controls ∑ k∈[K] ∑ h∈[H] min{1,mkh(skh, akh)}.
Lemma 12 Let d := dimE(Z, ∣∣eβH − 1∣∣ /K). Under Assumption 2, for any δ ∈ (0, 1], let {mkh(s, a)} be as defined in Lemma 11 and ζ be as defined in (12), then with probability at least 1− δ, we have ∑
k∈[K] ∑ h∈[H] min{1,mkh(skh, akh)} ≤ 2H min{d,K}+ 20H √ dKζ.
Proof. Since min {
1,mkh(s k h, a k h) } ≤ mkh(skh, akh) for all (k, h) ∈ [K] × [H]. For each fixed
h ∈ [H], by Lemma 15, we have∑ k∈[K] min{1,mkh(skh, akh)} ≤ 1 |eβH − 1| [∣∣eβH − 1∣∣+ ∣∣eβH − 1∣∣ ·min{d,K}+ 5√γ2dK] ≤ 1 |eβH − 1| [ 2 ∣∣eβH − 1∣∣ ·min{d,K}+ 5√γ2dK]
= 2 ·min{d,K}+ 5 |eβH − 1|
√ γ2dK
≤ 2 ·min{d,K}+ 20 √ dK [ log ( N1/K(P, ‖ · ‖∞,1) ·H/δ ) + √ log(4K2H/δ) ] ,
where the last step holds since γG = γ where γ is given in Lemma 14. Summing both sides of the above equations over h ∈ [H] results in the desired bound.
Recall the definition of M from Theorem 1, and now its upper bound can be determined by combining Lemmas 11 and 12. Therefore, the proof of the theorem is completed.
G.1 AUXILIARY LEMMAS
Let Z be a set of [0, D]-valued functions for some number D > 0. We define {(Xτ , Yτ )}τ∈[t] be a series of random variables such that each Xτ is in the domain of the elements of function set Z , and each Yτ ∈ R. Let F = {Fτ}τ≥1 be a set of filtrations such that for all τ ≥ 1, the random variables {X1, Y1, . . . , Xτ−1, Yτ−1, Xτ} is Fτ−1-measurable. Furthermore, we assume there exists a function z∗ ∈ Z such that E[Yτ | Fτ−1] = z∗(Xτ ). For any ε > 0, we denote byNε(Z, ‖·‖∞) the ε-covering number of Z with respect to the supremum norm ‖z1 − z2‖∞ = supx |z1(x)− z2(x)|. We define
ẑt := argmin z∈Z ∑ τ∈[t] (z(Xτ )− Yτ )2,
and for γ ≥ 0, let
Zt(γ) := z ∈ Z : ∑ τ∈[t] (z(Xτ )− ẑt(Xτ ))2 ≤ γ2  .
We record a concentration result.
Lemma 13 Suppose that for any τ ≥ 1, the random variable Yτ − z∗(Xτ ) is conditionally σ-subGaussian given filtration Fτ−1. Let
γ2t (δ, ε) := 8σ 2 log ( Nε(Z, ‖ · ‖∞)/δ ) + 4εt ( D + √ σ2 log(4t(t+ 1)/δ) ) .
Then for any ε > 0 and δ ∈ (0, 1], with probability at least 1− δ we have z∗ ∈ Zt(γt(δ, ε)).
Proof. The proof can be adapted from that of Russo & Van Roy (2014, Proposition 6).
In the following, we use the shorthand γ := γG, where γG is defined in (13) and used in Line 4 of Algorithm 3.
Lemma 14 For any δ ∈ (0, 1] and γ2 = 10 ∣∣eβH − 1∣∣2 [log (N1/K(P, ‖ · ‖∞,1) ·H/δ)+√log(4K2H/δ)] ,
then for all (k, h) ∈ [K]× [H] we have Ph ∈ Pkh with probability at least 1− δ.
Proof. We first note that for any (k, h) ∈ [K] × [H], Line 3 in Algorithm 3 can be equivalently written as
P kh ← argmin P∈P ∑ τ∈[k−1] ((eβ·V τ h+1(s τ h+1) − 1)− ∫ S P (s′ | sτh, aτh) · (eβ·V τ h+1(s ′) − 1)ds′)2,
since ∫ S P (s
′ | sτh, aτh)ds′ = 1. Recall the definition of zP in (11). For any (k, h) ∈ [K] × [H], we set Z = Z , Yk = eβ·V k h+1(s k h+1) − 1, Xk = (skh, akh, V kh+1) and z∗ = zPh . Then, we have that
Yτ − z∗(Xτ ) is conditionally ( ∣∣eβH − 1∣∣)-sub-Gaussian for τ ∈ [k − 1] given a properly defined filtration. By the definition of Pkh , we have Zk(γ) = {zP : P ∈ Pkh}. By definition of γ, we have
γ ≥ γk−1(δ/H, ∣∣eβH − 1∣∣ /K)
for all k ∈ [K], where γt(·, ·) is as defined in Lemma 13. By Lemma 13 with D = σ = ∣∣eβH − 1∣∣
and ε = ∣∣eβH − 1∣∣ /K, with probability at least 1− δ/H and for all k ∈ [K], we have
z∗ ∈ Zk(γk−1(δ/H, ∣∣eβH − 1∣∣ /K)) ⊂ Zk(γ),
thus implying Ph ∈ Pkh . Applying the union bound over h ∈ [H], we have that Ph ∈ Pkh with probability at least 1 − δ. Now we show that Nε(Z, ‖ · ‖∞) ≤ Nε/|eβH−1|(P, ‖ · ‖∞,1) for any ε > 0. Let V := {V : S → [0, H]}. For any P, P ′ ∈ P and their corresponding zP , zP ′ ∈ Z , we can compute
‖zP − zP ′‖∞ = sup (s,a,V )∈S×A×V ∣∣∣∣∫ S P (s′ | s, a)(eβ·V (s ′) − 1)ds′ − ∫ S P ′(s′ | s, a)(eβ·V (s ′) − 1)ds′ ∣∣∣∣
≤ ∣∣eβH − 1∣∣ · sup
(s,a)∈S×A ∫ S |P (s′ | s, a)− P ′(s′ | s, a)|ds′
= ∣∣eβH − 1∣∣ · ‖P − P ′‖∞,1,
as desired.
We have the following result on the eluder dimension. Lemma 15 Let Z = Z and d = dimE(Z, ∣∣eβH − 1∣∣ /K). For any K ≥ 1, β ∈ R and γ̄ > 0, we have ∑ k∈[K] sup z,z′∈Zk(γ) |z(xk)− z′(xk)| ≤ ∣∣eβH − 1∣∣+ ∣∣eβH − 1∣∣ ·min{d,K}+ 4√γ̄2dK. Proof. This result is an adaptation of Russo & Van Roy (2014, Lemma 5) with C = ∣∣eβH − 1∣∣ therein.

Review summaries:
The paper studies risk-sensitive reinforcement learning with the entropic risk measure and function approximation. A meta algorithm based on value iteration is first proposed, then the paper proposes two concrete instantiations, one for linear function approximation and one for general function approximation. Regret bound for both algorithms depend sub-linearly in the number of episodes, and the linear one depends polynomially on the ambient dimension, whereas the general one depends polynomially on the Eluder dimension.

This paper proposes a risk-sensitive algorithm with function approximation in reinforcement learning. To handle the uncertainty, the proposed algorithms consider an entropic risk value function controlled by a risk parameter, which provides a unified framework for both risk-sensitive and risk-averse settings. The main contribution of this paper is to provide theoretical guarantees for the proposed algorithms.