Entropic Risk-Sensitive Reinforcement Learning: A Meta Regret Framework with Function Approximation
Authors: Yingjie Fei
Zhuoran Yang
Zhaoran Wang
Venue:  (2021)

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. 


Under review as a conference paper at ICLR 2021
ENTROPIC RISK-SENSITIVE LEARNING:
REINFORCEMENT A META REGRET FRAMEWORK WITH
FUNCTION APPROXIMATION
Anonymous authors Paper under double-blind review
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 meta algorithm based value iteration. We then derive two algorithms for linear and general function approximation, namely RSVI.L and RSVI.G, respectively, 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 meta regret bound. We further verify the condition for RSVI.L and RSVI. G under respective function approximation settings obtain concrete regret bounds that scale sublinearly in the number of episodes.
INTRODUCTION
Risk is one of the most important considerations in decision making, should it be in reinforcement learning (RL). As a prominent paradigm in RL that performs learning while accounting for risk, risk- sensitive RI. 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 (Buchler et al., 2009; Thrun, 2010), behavior modeling (Niv et al., 2012; Shen et al., 2014), real- time strategy games (Berner et al., 2019; Vinyals al., 2019) and robotic surgery (Fagogenis 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 RI algorithms in applications of high dimension. We focus on risk-sensitive RI. with the entropic risk measure, a classical framework established by the seminal work of Howard & Matheson (1972). Informally, for a fixed risk parameter / * 0, our goal is to maximize the objective
V8 = log RR
(1)
The definition of Va will be made formal later in (2). The objective (1) admits Taylor expansion V3 E[R] + _ Var R)) + O(32). Comparing (1) with the risk-neutral objective V E[R] studied in the standard RI setting, we see that 3 > 0 induces a risk-seeking objective and 3 < 0 induces risk-averse one. Therefore,
formulation with the entropic risk measure in (1) accounts for both risk-secking 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 V3 tends to the resk-neutral as 3 + 0.
Existing works on function approximation for RL have mostly focused on the risk-neutral setting and heavily exploits the linearity of nest-llutral 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). also well known that even in the nest-rl setting, improperly implemented function approximation could result in errors that scale exponentially in the size of the state space.

---

Under review as a conference paper at ICLR 2021
Combined with nonlinearity of the risk-sensitive objective (1), it compounds the difficulties of implementing function approximation in resk-sensitive RL with provable guarantees.
This work provides principled solution to function approximation in risk-sensitive RL by overeoming the above difficulties. Under the finite-horizon MDP setting, we propose a meta algorithm based value iteration, and from that we derive two concrete algorithms for linear and general function approximation, which we name RSVIL and RSVI.G, respectively. By modeling shifted exponential transformation of estimated value functions. RSVI.L and RSVI. 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. exploits a synergistic relationship between feature mapping and regularization in a risk-sensitive fashion. The resulting structure of RSVI. makes it more efficient in runtime and memory than RSVI.G under linear function approximation, while RSVI.G more general and allows for function approximation beyond the linear setting.
Furthermore, we develop meta regret analytic framework and identify risk- optimism condition that serves as the core component of the framework. Under the optimism condition, we prove 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 the role of function approximation in regret guarantees. We hope that our meta framework will motivate and benefit future studies of function approximation 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; 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 meta regret analytic framework and identify 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, 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 number u # O, we define sign(u) = 1 if > 0 and -1 if u < O. For two non-negative sequences {a:} and } we write as S by if there exists a universal constant C > 0 such that a, S Cb; for all i, and write a, x by a, S b; and by S aq. We use Ô(-) to denote O()) while hiding logarithmic factors. For any 6 > and set X, we let (X',, |I] be the E-net of the set X with respect to the norm -
||. We let A(X) be the set of probability distributions supported on X. For any vector u E RR and symmetric and positive definite matrix E Raxn, we let |/u]|r == Vu Tu. We denote by In the n x n identity matrix.
RELATED WORK
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- 2011; Coraluppi & Marcus, 1999; Di Masi Stettner, 1999; 2000; 2007; Fleming & McEneaney, 1995; Keermändez-Hermándee & Marcus, 1996; Jaskiewicz, 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 focuses asymptotic behaviors of the problem/algorithms, and sample/im results with unknown transitions have rarely been investigated.
2

---

Under review as a conference paper at ICLR 2021
The most relevant work to ours is perhaps Fei et al. (2020), who consider the same problem 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 lower bound. However, their algorithms and analysis are restricted to the tabular setting. Compared to Fei et al. (2020), our paper provides 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 ((K'1/))-rerre 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 risk- sensitive settings than in the standard risk-neutral one.
3 PROBLEM FORMULATION
3.1 EPISODIC MDP
Jhe m fraheem)) where K the number of episodes, H is the number of steps in each episode, S is the state space, AA is the action space, Ph. S x A + (SS) is the transition kernel at step h, and Tn S x A + [0, 1] is the reward also assume that {rx} are known and deterministic, as is done in existing works such as Yang & Wang (2019); Zhou et al. (2020).
An episodic MDP parameterized by a tuple H. (Pa
function step h. We assume that (Pr} are unknown. For simplieity
We interact with the episodic MDP as follows. In the beginning of each episode k: E [K]. the environment chooses an arbitrary initial state of E S. Then in each step h [H]. we take an action af E A, receives a reward rh (s), a and transitions to the next state sh_1 E S sampled from P. s sf,aa)) a.)). Once we reach s $1+1 the current episode terminates and we advance to the next episode unless l K.
3.2 VALUE FUNCTIONS, BELLMAN EQUATIONS AND REGRET
We assume that / is fixed prior to the learning process, and for notational simplicity we omit from quantities to be introduced subsequently. In risk-sensitive RL with the entropic risk measure, we aim find a policy ग {mh S + A} so as to maximize the value function given by
H
)]
}
(T) = 3
log
exp 3
Σ
Tw (w
$h=
8h $ )
(2)
h'=h
for all (h E [H] x S. Under some mild regularity conditions, there exists a greedy policy
π = {m which gives the optimal value V,"" (s) = sup, (s) for all (h E [H] x S (Bäuerle & Rieder, 2014). In addition to the value function, another key notion is the action-value function defined as
(s,aa))= 3
log E
exp
B hi=h
The (Rwssaa) aN) sh s,
(3)
for all (h, s, a)
[H] x S x A.
The action- value function QT, is closely associated with the value function ViT via the so-called Bellman equation:
()(s,a) = (a(s a) + log (Er-PA((Isa) [exp (B. V (
(4)
(s) = (1
V ($+ = 0.
3

---

Under review as a conference paper at ICLR 2021
which holds for all (h, s, a) E [H] S A. Note that the identity of Q7, in (4) is result of simple calculation based on (2) and (3). Similarly, the Bellman optimality equation is given by
(%(s, a) - ra(s, a) + log (BN-Pa((1a. [exp (B. V V
(5)
B
(s) max (s, a),
(s)=
acA
again for all (h, 8, a) E [M] x x A. In the above, we use the shorthand (
(:5 = O7 (---) for
all h [H] and (+) is similarly defined. The identity (-) m Q7 (-, a) implies that the optimal x is the greedy policy with respect to the optimal action-value function {Qr, he(M
During the learning process, the policy n* in each episode k may be different from the optimal n². We quantify this difference over all K episodes through the notion of regret, defined as
Regret(K) = Σ
Vi((+t - VT vT"((t) (dt) kE(K]
(6)
Since (s) 2 (s) for any and E S by definition, regret also characterizes the suboptimality of (x* k| relative to the optimal x².
3.3 FUNCTION APPROXIMATION
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.
We assume that the MDP is equipped with Rdd such that for any h E [H), there exists vector On E Bdd with |10 l2 S vd and the transition kernel given by
Assumption
sb SxAxS +
(s s, = (s, (,, TO
for any (s, E AxXXX. We also assume that
118 (s,,,,8) (cRV() 1)dd S Vd. Vd
for any (s, E S x A and V : S [0, T] where T 2 O.
This form of linear function approximation is also studied in the work of Ayoub et al. (2020); Cai al. (2019); Zhou al. (2020), whose setting is equivalent ours when + O. The setting of Assumption may be reduced to the tabular setting in which (b(s, a, s') is canonical basis vector in Ed with d S |A|, i.c., the (s,a, a,,ass) s')-th entry of v0ss, a, a.s) is equal to and the other entries are equal to zero. also subsumes various settings of function approximation including linear combinations of base models (Modi 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, make the following assumption.
Assumption We assume that have access to a function set' P such that the transition kernel Pr. E P for all h E [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, 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).
Throughout the paper, we use fanction class and function interchangeably.
4

---

Under review as a conference paper at ICLR 2021
4 ALGORITHMS
We first present the Meta algorithm for Risk-Sensitive Value Iteration (MetaRSVI) Algorithm 1, which is a high-level framework including key features of algorithms based value iteration (Bradtke & Barto, 1996; Osband et al., 2014; Jin et al., 2019). It mainly consists a value estimation step and policy execution step. In the value estimation step, the algorithm estimates the optimal {Q%) by its iterates { based on historical data. Since we focus on greedy policies, in Line the estimated value function (.) is simply taken as the maximum among (")'a)))''' The primary machinery of value estimation, known as Risk-Sensitive Temporal Difference 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 {2) }) to collect data for subsequent learning stages. remark that Algorithm is flexible and general enough to allow for any function approximation. In the remaining of this section, we derive two special instances of Algorithm I for linear and general function approximation, respectively, by providing concrete implementation of RSTD.
Algorithm MetaRSVI
Input: risk parameter 3, number of episodes K for episode l 1, ................................ K do
1:
2:
V (+) t
3:
for step h H, H 1...., do
value estimation
4:
Q < RSTD (i. h 3, (V re())
5:
(.(()) maxa'eA a2))
6:
end for
7:
Receive the initial state st from the environment for step h = 1, ..,..,. do
8:
D policy execution
9:
Take action o < argmax,'ea (sh, a')
Receive the reward rı (s%, ax) and the next state s s
11: end for
end for
We introduce Risk-Sensitive Value Iteration for Linear function approximation, or RSVI.L, in Algorithm under the setting of Assumption 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 with a concrete implementation for the linear function approximation. Line iterate w can be interpreted the solution of the following least- equatesquares problem:
w
< argmin WERd
Σ
- w TT a. - A||wo|
rE(R-1]
where the surrogate feature mappings { --(k))))))))) are constructed in Line 5 and X 2 0 is the regularization parameter to be set by users. The above regression problem essentially computes an estimate of On, the parameter of the transition kernel Pr. by taking advantage of the linear form B ss)) (e (44()) in the Bellman equation (4). Note that the regression targets set shifted exponential transformation estimated value functions, i.e., (oL,,)))))_))) 1}. Similar construction is applied to the surrogate features (--)) in Line 5. Mechanically, such design ensures 0, we would have of (..-) = 0 and therefore by definition Q% rn(::));
that when v this is similar behavior exhibited by risk-neutral algorithms for linear function approximation, e.g.,
h++1
Algorithm in Cai et al. (2019) whose surrogate features are given by replacing e ...vi..() 1 in Line 5 with V (-). To update (.((s)) Line 7, we use the quantity
(h.()))) [min(e (0) w +1+ (/(+)(())) )) ((--N) (of (1- i
if 0,
(8)
Informally, with BY taking the role of bonus, L. can be seen "optimistic" and risk-adaptive
estimate for the expected value of @ Vo V. under the (unknown) transition kernel Pt.. The term
5

---

Under review as a conference paper at ICLR 2021
Algorithm 2 RSVILL
Input: risk parameter number of episodes K, bonus multiplier Yt regularization parameter À
1: Run Algorithm I with RSTD() therein overloaded by the following subroutine:
2: procedure RSTD(k, h, 5.
TL. A)
3:
A + ErE(R-1) (5 0 0 (5) o,) +
4:
" + (A -AA)- [ (
(el -
(f..))) + Ss (,(')))'))))) (tt -1)ds'
5:
6: (..)
t T
7:
return (,) + (n())) + log(9h where (:.-) -) is defined in (8)
8:
end procedure
(o "), wxt) + serves as a correction the shifted quantity e (.V. in both (x and wh so as to align the structure of Line 7 to that of the Bellman equation (4). A proper definition of bonus 6% (with Yu therein formally given in Theorem 2 below) and the truncation at (H would put Th within [1, (BH- entrywise. This ensures that the estimate Q is on the same scale the optimal (% [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 set À 0 and update the entries in O whose corresponding state-action pairs have been visited in the history. In the linear setting, however, the entire Q is updated at once and it's imperative to prevent the singularity of the covariance matrix A This boils down to having a proper choice of the regularization parameter X. is too small, A% would be nearly singular; if À is too large, the spectrum of A would be dominated by À for prohibitively many episodes with the algorithm making little progress in learning. Intuitively, since ( & le 1l. an ideal À should depend on ,3 and be on the order (e - 1)2, so that the spectrums of the matrices (,, ),, () and AT are close. Indeed, this intuition provides guidance
choice of X (see Theorem 2). Our Algorithm 2 hence demonstrates a synergistic relationship between the surrogate features and regularization in a risk- sensitive fashion. This is in great contrast with existing algorithms for linear function approximation in the rest-ne setting, such 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 Disk-Sensitive Value Iteration for General function approximation, abbreviated as RSVI.G, Algorithm 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 3 < 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.
MAIN RESULTS
In this section, we present regret guarantees for our algorithms via a meta regret framework. We identify risk-sensitive optimism condition, which certifies 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 and respectively.
5.1 META REGRET BOUND
Recall the iterates { in Algorithm 1. For each tuple (k, h s,a) [K] x [H] x A, we define (),)))) = (s, a) + log(EE>>P.(1 2- Vhi2(1)))
can be seen that (Q)) are the
We also discuss computational aspects of our algorithms; Appendix

---

Under review as a conference paper at ICLR 2021
ideal counterparts of {Qr] } that could be constructed if the transition kernels {Pr 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) E [K] x [H] x S x A, we have Q% (8, a) E [0, H - h + 11, and
there exist some quantities m > 0.g g 2 1 and universal constant O such that
el8)H 9 m.-mm (8,a).
0 v (x (s, c. se.
13
Since { informally "'ptiiisttc" estimates of the ideal (Q.), the difference (5. (%, a) in Condition may be thought of as the level of optimism maintained by the algorithm for state-action pair (s, a) in step of episode k, with its upper bound depending on risk sensitivity through the factor -0 -1 Therefore, say that Condition is risk-sensitive optimism condition. [
In the upper bound of the condition, the actual values of and m (s, a) may depend on function approximation and implementation of the abstract function RSTD. Let us recall that {(* af) are the state-action pairs visited by Algorithm 1, and we are ready state the meta regret bound.
Theorem Let M = 9 Eke(K] Eneinn min (1, my (sh a where g and { are as given in Condition 1. On the event of Condition 1, for any å (0, 1]. with probability at least 1 - 8 the regret of Algorithm satisfies
Regret(K) 2 el
18| M e!llm
V HKH Hlg((11///)
The proof is given in Appendix D. Even though the actual form of M depends specific function approximation, the derivation of Theorem only requires the structure of Algorithm I, which is agnostic of function approximation. In the above bound, the first term can be interpreted as the total optimism maintained by Algorithm and is in fact a direct consequence of Condition 1. The second term can be seen as the total drift of iterates {VA} from the value functions {V,"" }. which is the result of a martingale analysis. The factor el shared by both terms due to a local linearization of the nonlinear objective (2) well as standard backward induction analysis of H --horizzo MDPs. Soon we will show that M ((K)/2) under both linear and general function approximation, so the first term in Theorem 1 would dominate the regret bound. Similar to M, the exponential factor elAl also comes into the bound from Condition 1. It has been shown distinctive feature risk-sensitive RL algorithms that represents tradeoff between risk sensitivity and sample complexity; see Fei et al. (2020) for a detailed discussion on this point.
[3]
5.2 REGRET BOUND FOR LINEAR FUNCTION APPROXIMATION
We now present regret bound for Algorithm induced by Theorem 1. Let
7t ce le 1lv d dlog(2dKH/O))
where o, is appropriate universal constant. We have the following result.
Theorem 2 Let " of (9) and X = (e - 1)2 be input to Algorithm 2, and M be as defined in Theorem 1. Under Assumption 1, for any 8 E (0, 1}, with probability at least 1- Condition holds for Algorithm so that M S (d2 K H2 log 22d HAAH//A H/8))//2, Therefore, Theorem I implies that the regret of Algorithum 2 satisfies
18/H -
Regret(K) S
e H² V VOKH2 (2dK
|8]
The proof given Appendix E. One may obtain regret bound for the tabular setting by taking
= [ [A| Theorem 2, and the resulting bound can be seen to nearly match that Fei et al. (2020, Theorem 1), except for the polynomial dependency on |S| and [A] The bound obtained
'B inspecting the proof of Fei et al. (2020, Theorem 1), see that they apply the bound (1 (exps)) H) 11)xx((18 H²) (1/18)) H²) 1)) for some universal constant C > 0.
7

---

Under review as a conference paper at ICLR 2021
from specializing Theorem 2 to the tabular setting is also nearly optimal for small |8] (with respect to (3), K and H) in view of the lower bound
c18111/2
E [Regret( [K)
K log K
(10)
|
given by Fei al. (2020, Theorem 3). In addition, as + O. the setting of risk-sensitive RL tends to that of standard risk-neutral RL. We have the following corollary as precise characterization of Theorem that regime.
Corollary Under the setting of Theorem and when B with probability least 8, the regret of Algorithu 2 satisfies
Regret K) 2
The proof is given in Appendix F. Corollary matches the standard result in the risk-neutral setting, e.g. Cai et al. (2019, Theorem 3.1), up to logarithmic factors.
5.3 REGRET BOUND FOR GENERAL FUNCTION APPROXIMATION
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. (s,a) E 8 A and
V: + [0, HJ. we define the function set
(e - 1)ds', (1I) Z = {zp : Pe P), where 2p(s, a, V) = sign(3) / P(s' s, (eaa)-((evviee
For any P, P' EP, we define
- P' |0o10 sUP(s,,)ESx.A P(: 8,0) P'(. (((118.0)) (..a)]1. We let dæ = dimg (Z, 1e S 11/K)
be the (eeH - 11 K) -lluder dimension of function set Z, and
c= == (H- (NNN (1xo,))/))))) + Vlog(4K3H))
(12)
In Algorithm 3, we set
YG 10]= 10 IVV.
(13)
We now state our result for Algorithm 3, which is another instantiation of Theorem
Theorem Let Gia of (13) be input to Algorithm and M be defined in Theorem 1. Under Assumption 2, for any ö E (0, 11, with probability at least 1 --6 8, Condition 1 holds for Algorithm 3 that M S. H min(de, K} KdC.HPC. Therefore, Theorem implies that the regret of Algorithm 3 satisfies
elA 18118 ( (iiindd K} + vdgkH?(
Regret( K) S
3
The proof is given in Appendix The term H min(dg, K) above also appears in the regret bound for the multi-arm bandit problem with general function approximation (Russo & Van Roy, 2014), which
special case of our finite-horizon episodic MDP setting. When is sufficiently large, we have H min (dg, K} S VdgKH's and therefore Thcorem yields Regret(K) = that the transition kernels in P. take the linear form as in Assumption 1, we have dg S dolog K, and 1
201n 2| Ö(v)rKHH)) In
[2
llso,))) I d K so that < S d dllo(KHH// H8)). Then for sufficiently large K, the bound Theorem 3 matches that Theorem 2 up to logarithmic factor. On the other hand, under the linear setting of Assumption 1, Algorithm
(P,
2 may be more efficient in runtime and memory than Algorithm 3, as discussed Appendix
RReaall that the definition of the eluder dimension is formally given in Appendix A.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin F. Yang. Model-based reinforcement learning with value-targeted regression. arXiv preprint arXiv:2006.0111 2020.
Nicole Bäuerle and Ulrich Rieder. More risk-sensitive Markov decision processes. Mathematics of Operations Research, ((1)):055-2200 2014.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Dębiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, al. Dota 2 with large scale deep reinforcement learning. arXiv preprint arXiv: 191200680, 2019.
Vivek S. Borkar. A sensitivity formula for risk- cost and the actor-critic algorithm. Systems & Control Letters, 44(5):339-346, 2001.
Vivek S. Borkar. Q-learning for risk-sensitive control. Mathematicc of Operations Research, 27(2): 294-311, 2002.
Vivek S. Borkar. Learning algorithms for risk-sensitive control. In Proceedings of the 19th
International Symposium on Mathematical Theory of Networks and Systems-MTNS, pp. 55-60, 2010.
Vivek S. Borkar and Sean Meyn. Risk-sensitive optimal control for Markov decision processes with monotone cost. Mathematics of Operations Research, 27(1):192-209, 2002.
Steven J. Bradtke and Andrew G. Barto. Linear least-squares algorithms for temporal difference learning, Machine Learning, 22(1-3):33-57, 1996.
Martin Buchler, Karl lagnemma, and Sanjiv Singh. The DARPA urban challenge: autonomous vehicles in city traffic, volume 56. springer, 2009.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimization. arXiv preprint
2019.
Rolando Cavazos-Cadens and Daniel Gernández-Heránddee Discounted approximations for risk- sensitive average criteria in Markov decision chains with finite state space. Mathematics of Operations Research, 36(1):133-146, 2011.
Stefano Coraluppi and Steven I. Marcus. Risk-sensitive, minimax, and mixed risk- neutral/minimax control of Markov decision processes. In Stochastic Analysis, Control, Optimization and Applications, pp. 21-40. Springer, 1999.
Giovanni B. Di Masi and Lukasz. Stettner. Risk-sensitive control discrete-time Markov processes with infinite horizon. SIAM Journal Control and Optimization, 38(1):66117)))) 1999.
Giovanni B. Di Masi and Lukasz Stettner. Infinite horizon risk sensitive control of discrete time Markov processes with small risk. Systems & Control Letters, 40(1):15-20, 2000.
Giovanni B. Di Masi and Lukasz Stettner. Infinite horizon risk sensitive control of discrete time Markov processes under minorization property. SIAM Journal on Control and Optimization, 46 (1):231-252, 2007.
Georgios Fagogenis, Margherita Mencattelli, Zurab Machaidze, Benoit Rosa, Karl Price, F Wu, V Weixler, Mossab Saeed, John E Mayer, and Pierre Dupont. Autonomous robotic intracardiac catheter navigation using haptic vision. Science robotics, 4(29), 2019.
Yingjie Fei, Zhuoran Yang, Yudong Chen, Zhaoran Wang, and Qiaomin Xie. Risk- sensitive reinforcement learning: Near-optimal risk-sample tradeoff in regret. arXiv preprint 11X2:22000.13827, 2020.
Wendell H Fleming and William M McEneaney. Risk-sensitive control on an infinite time horizon. SIAM Journal on Control and Optimization, (816):881-19151 1995.
Michael Fu et al. Risk-sensitive reinforcement learning: A constrained optimization viewpoint. arXiv preprint arXiv: arXiv 1810.09/00.0.. 2018

---

Under review as a conference paper at ICLR 2021
Daniel Hernández-Herniee Hernández and Steven I. Marcus. Risk sensitive control of Markov processes in countable state space. Systems & Control Letters, 29(3):147-155, 1996.
Ronald A. Howard and James E. Matheson. Risk-sensitive Markov decision processes. Management Science, 18(7):356- 369, 1972.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(Ap)):563-1660, 2010.
Anna Jaškiewicz. Average optimality for risk-sensitive control with general state space. The Annals of Applied Probability, 17(2):654-675, 2007.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. arXiv preprint urXiv:1907005380 2019.
Steven I. Marcus, Emmanual Gemmnndez-Gancherandd Daniel Hermandez-Heraandee Stefano Coraluppi, and Pedram Fard. Risk sensitive Markov decision processes. In Systems and Control in the Twenty-first Century, pp. 263-279, Springer, 1997.
Oliver Mihatsch and Ralph Neuneier. Risk-sensitive reinforcement learning. Machine Learning, 49 (2-3):267-290, 2002.
Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics, pp. 2010-2020, 2020.
Yael Niv, Jeffrey A. Edlund, Peter Dayan, and John P. O'Doherty. Neural prediction errors reveal risk-sensitive reinforcement--earmigg process in the human brain. Journal of Neuroscience, 32 (2):551-562, 2012.
Ian Osband, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via randomized value functions. arXiv preprint arXiv:1402.0633, 2014.
Takayuki Osogami. Robustness and risk-sensitivity in Markov decision processes. In Advances in Neural Information Processing Systems, pp. 233-241, 2012.
Stephen D. Patek. On terminating Markov decision processes with a risk-averse objective function.
Automatica, 37(9) 2001.
Daniel Russo and Benjamin Van Roy. Learning optimize via posterior sampling. Mathematics of Operations Research, 221-)312 2014.
Azad Shademan, Ryan S. Decker, Justin D. Opfermann, Simon Leonard, Axel Krieger, and Peter C. W. Kim. Supervised autonomous robotic soft tissue surgery. Science translational medicine, (337):337r664 337ra64, 2016.
Yun Shen, Wilhelm Stannat, and Klaus Obermayer. Risk-sensitive Markov control processes. SIAM Journal on Control and Optimization, 5 335:336523366, 2013.
Yun Shen, Michael Tobia, Tobias Sommer, and Klaus Obermayer. Risk-sensitive reinforcement learning. Neural Computation, 26(7): 198--1328, 2014.
Sebastian Thrun. Toward robotic cars. Communications of the ACM, 53(4))99- 106, 2010.
Oriol Vinyals, Igor Babuschkin, Wojciech M. Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782): 350-354, 2019.
Ruosong Wang. Ruslan Salakhutdinov, and Lin F. Yang. Provably efficient reinforcement learning with general value function approximation. arXiv preprint a0Xi::2005.10804, 2020.
Yining Wang, Ruosong Wang, Simon S. Du, and Akshay Krishnamurthy. reinforcement learning with generalized linear function approximation. arXiv preprint 1r12v 2019.
Optimism in
10

---

Under review as a conference paper at ICLR 2021
Peter Whittle. Risk-sensitive Optimal Control, volume 20. Wiley New York, 1990.
Lin F. Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. arXiv preprint arXiv: 1905. 10389, 2019.
Dongruo Zhou, Jiafan Hc, and Quanquan Gu. Provably efficient reinforcement learning for discounted mdps with feature mapping. arXiv preprint wrXv:2206.11315, 2020.
A ELUDER DIMENSION
To introduce the eluder dimension, we need to set forth the concept of e-independence.
Definition 1 For any 0 and function set G whose elements are in the domain X. say that I E X is E d-eeendentt on the set of elements Xn = {I1, Z2. Enl C X with respect to G if any pair of functions g.g' E 9 satisfying [ee()) g' (zx S E² also satisfies g(x) - (x) S E. We say that e-independent of Xn, with respect to if is not e-dependent Xn with respect to g.
Hence, e-independence characterizes a notion of dissimilarity of a point x to the elements in subset X,, 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 For any E > and function set 9 whose elements are the domain X, the E-eluder dimension dimg(g, is defined as the length d' the longest sequence of elements in X such that, for some 2 e, every element is e' -independent of its predecessors.
The eluder dimension extends the concept of dimension in linear spaces and generalizes to linear function spaces. It is also related to the notions Kolmogorov dimension and VC dimension. We refer readers Russo Van Roy (2014) for further details on the eluder dimension and its advantages compared to other complexity measures.
B MORE ON ALGORITHMS
We present details of Algorithm 3 that we have omitted from the main text. For each (k, h) [K] [H], transition kernels P, P E and estimated value functions (Vi411re(H-1) we define the squared error
P(s' P 5h ae
/ P'(s' 1h al)e &
TX. P') Σ
(14)
In Algorithm 3, Line 3 computes an estimate Pk of the transition kernel Ph. by solving a least- squares problem similar to (7). Line then constructs a confidence set around the estimate pk This step is reminiscent of UCRL (Jaksch al., 2010), where confidence sets used enforce the so-called Optimism the Face of Uncertainty (OFU) principle for efficient exploration. Line updates Q by solving an optimization problem over the confidence Pk with the definition
if 3 0. mmxxpert Is P(s' I Ver ds'.
dh. (..)()))==
(15)
minpeeg Is P(s' Je Vi ds's
if 3 < 0.
is worth remarking that both Lines 3 and implicitly operate with the shifted exponential transformation of estimated value functions: replacing e (++(() therein by --V -1 would not result in any difference for the algorithm.
Computational aspects. We briefly discuss computational aspects Algorithms and 3. It is not hard to that the time and space complexities for Algorithm 2 are polynomial in key model parameters d, K and H. For Algorithm is unclear how the complexities scale under Assumption 2, where the structure of P is unknown. Nevertheless, under Assumption in which the transition

---

Under review as a conference paper at ICLR 2021
Algorithm 3 RSVI.G
Input: risk parameter number of episodes K, confidence width YG. function set P
I: Run Algorithm I with RSTD() therein overloaded by the following subroutine:
2: procedure RSTD(k, h, 9. (Ttt)re(N) JG. P)
3: P argmin PEP Er=1 [e Ve -Js P(s' ee
(4)) ds'))
4: P :PEP:T Ph) S aa). where (: is defined in (14)
5: return (+(())) + rn(())) + log(gh where (h,)(.))) is defined in (15)
6: end procedure
kernels admit a linear form, Algorithm also attains polynomial time and space complexities with respect 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 requires solving linear programs which could be computationally cumbersome.
C PRELIMINARIES TO PROOFS
We fix tuple h, s, a) E [K]
[H] S A and a policy For Algorithm (which subsumes
both Algorithms 2 and 3), define
2 a) = =Bo'wPh a. 1k12(6))
(16)
and
Q3 = (s, a) = -v s,a) e (.V
(17)
In the above definitions. note that and @3 depend on (k, h, a); we suppress such dependency for notational simplicity. We have the following bounds on 92 and 93-
Lemma We have 22 Q3 [min (H)))), max e(H
Proof. The result for d2 and d3 can be seen if we recall their definitions and the fact that eVV() [min (1, (HHH))) max 1, (H -h) for any V S + [0, H hl.
For any g' > 0, define
1
Gi(d') = log(4')
B log 1og(
B
(18)
G2 = 3 log(42} log(4s}.
3
Since Q2. 93 > by definition, Gi(g') and G2 are well-defined. By the Bellman equation (4), for any we have
1 log (Bv-Pac maee (aje
([(s,a)=r(s... 3
We restate Condition in the following.
Condition 2 (Restatement of Condition 1) Let Gi(d)) be defined in (18). For all (k, h a) [K] x [ S x A, assume (), a) E [0, H. in Algorithm 1, then there exist some quantities g 2 1, mi = a) > 0, qi = th (s, a) 2 min(1, e (H--)) and universal constant C₁ > 0 such that G1 (1 Q (s, B log(gh. (s, and
c13(H
0 < Gi (s. a)) sa.
g. m
188
can be seen that G1 (9), a)) = (5, - (,, a), where क" is defined in Section 5, Under Condition 2, it holds that
1
(hh (s)
3 log(a))
log(es) G + G2.
(19)
12

---

Under review as a conference paper at ICLR 2021
by the construction of 0% in the algorithms, where we have let G1 G1 (91). Condition 2 has unspecified quantities ς1. {m and g. The condition, along with those quantities therein, will be verified in Lemmas 6 and 11 under Assumptions and 2, respectively.
For now let focus on G2, and we need the following simple result control it.
Fact 1 Consider z. y, b E R such that x 2 y-
(a) y 2 9o for some 9o > 0, then log(2) - log(y) - (2 y):
(b) Assume further that y 2 O. If b 0 and x S for some > 0, then exa - -ebo S
be (x y): if 0, then e ear S (-b) y).
Proof. The results follow from Lipschitz continuity of the functions x ++ log(z) and x + ebz
We next control G2, whose proof is agnostic of function approximation.
Lemma 2 For each (ki, h 8, a) E [K] H x S A, we have
VV (8) 2 (84)('') for all s' E S, then 0 $ G2 S 1 E s. 11 (8') (
Proof. Case 3 > O. The assumption V (s') 2 1 (5') for all s' E S implies that 2 93 (by the definitions of 92 and q3 in (16) and (17)) and therefore G2 by the definition (18). We also have
G2 < (22 93) 3
S Se (.Pl (s.)
(s'))
where the first step holds by Fact I(a) (with go = 1, x = 92. and y = q3) and the fact that Q2 2 ds 1 (implied by Lemma 1), and the second step holds by Fact 1(b) (with 6 = B, x h4 (8),
and y V (s)) and 2 (s) 2 (s) 2
Case 3 < O. The assumption V/ (s') 2 VT+ (s') for all s E implies that d2 S q and therefore
G2 2 due to its definition (18). We also have
1
G2 = (-3) (logfa3} log(gz))
< (-3)
(93 - 92)
S cl 13 E. ( 8.0) [V h+ (s') ViT (s')l
where the second step holds by Fact 1(a) (with go 3H
43, and y Q2) and the fact that
Qs 2 Qa > e 2H (suggested by Lemma 1), and the third step holds by Fact ((b) (with b = 3
1 (s), and y ( and V2K (s) V (s) 0.
With the help of Lemma (2), we can show the "optimism" of Qh in the following sense.
Lemma 3 Suppose (19) holds with G 2 O. We have (, a) 2 QT a) for all (k, h a) e [K] x [M]] S x A.
1i4 a)= = 0 for all (s, E S x A. We fix a tpple (k, a) E [K] x S x A and use strong induction on The base case for h = + 1
Proof. For the purpose of the proof, we set (8, (s
is satisfied since (Q) (+++1 Q 1+++) a) 0 for & E [K] by definition. Now we fix an h E [H] and
assume that 0 S (Qh+1 - (s, a). By the induction assumption we have
V (s) max Q
a'EAA h (s,a') 2 max (s, 2 (s).
(20)
a'EAA
Applying (20) to Lemma 2 yields G2 2 0. Since G₁ 2 by assumption, it follows that (Q), (5,) a) > 0 by (19). The induction is completed and so is the proof.
Lemma 3 implies immediate but important corollary.
13

---

Under review as a conference paper at ICLR 2021
Lemma 4 Suppose (19) holds with G1 0. We have (s) 2 (s) for all (k, h, E [K] x [H] x
Proof.
The result follows from Lemma 3 and Equation (20).
We now have all the keys to proving the meta regret bound.
D PROOF OF THEOREM
We work on the event of Condition 2 (which is a restatement of Condition 1), where and }m are defined. This means (19) also holds. Define 5% == V (s - Vi (sh), and ch+1 = E st (s') v 8/+1- Let {m,} } be as defined Condition 2. For any (k, E [ x [H], we have
o ( - Th (sh. a
< min(H, (2h - Q (5% }
(21)
e|8
m ( a } + el01H B - V (s')1
< min
H,
[8|
ela| -1
9
min|
[1, f )b 1814 -.
V (8))
[3]
(22)
el@l
=
g min m (s af1) + 100 (6 + c
(23)
18
In the above equation, the first step holds by the construction of Algorithm I and the definition of Vr," in (4); the second step due the fact that (: < H and (T
(---) 2 0: the third step holds by (19) combined with Condition 2 and Lemma 2: the fourth step holds since c1,9 2 1 and elaln
101 2
H; the last step follows from the definitions 8 and Sh++1-
Recalling from Algorithm and the Bellman equation (4) that ( ( = 0, as well as noting the fact that 6%m + Sh+ 2 implied by Lemma 4, we can continue by expanding the recursion in Equation (23) and get
(s)
8t Σ
Sh++1 +
elalH(hh1)g min m at))
(24)
18
KEI
NEW
Therefore, have
Regret(K) = Σ
-V Vi (
S Σ o7
KE(K]
kE[K]
S cl 11?
ΣΣ kE[K] hE(H]
chi +
18117?
Σ Σ
min minn1, (1,
af)).
9
|31
RE[K] AE[H]
(25)
where the second step holds by Lemma 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 independent of the new observation s in episode we have that { } is a martingale difference sequence satisfying |ck| < 2H for all (ke, h)) E [K] x [H] By the Azuma-Hoeffaae inequality, we have for any
t
IP
Σ
Sh 2t
< exp
2T H
KE[R]
NE(H]
14

---

Under review as a conference paper at ICLR 2021
Hence, with probability - 6/2, there holds
Σ
Σ
Sh+1 S
(26)
kE[K] bE(A]
Finally, plugging (26) into (25) yields
el
Regret(K) K) el H² V2H2T log(2/0)+
e
181111
Σ
Σ
min f
af))
9
kE[K] hE(H)
We then rescale å properly and finish the proof of Theorem 1.
To obtain regret bounds for Algorithms 2 and 3, remains to only specify quantities and Σke[K] EnE(H mf a in Condition 2. The next result prepares us for the quest.
Lemma Let 92 = df (s, a) as defined in (16). for each (k, h s, a) E [K] x [ x X A,
there exists some quantities 2 L, m = m a) > 0, = a 2 min (HH and universal constant C1 2 1 such that Gi (s, a)) = (s,
logi9h. a)), and 0 S S ci JeSH 1/9 m for B < 0, then
1--9 92 S Ci le - 11 m for 3 > O and 0 S
Condition 2 holds with the aforementioned cı 9. m and q1.
Proof. Case 3 0. By the definition of G1 (19). the assumption 0 S q1 2s implies that
G1 2 0. Moreover, Lemma and Fact ((a) (with 9o = 1, x = and Q2) together imply
1
G1 S B (qi 92).
Invoking the upper bound on ?1 1--- 92 for
the assumption completes the proof for the case.
Case 3 < 0. By the definition of G1 in 18, the assumption 0 < 92 implies that G1 2 0. Furthermore, by Lemma and Fact ((a) (with gu = x Q2 and y = q1), we further have
1
G
(- 3) (log {42} log(41))
(42 q1).
|
Invoking the upper bound on Ø2 91 and the fact that |e -1| = 1 - -0 for B < 0 completes the proof for the case.
E PROOF OF THEOREM 2
First of all, it can be seen that Line 7 in Algorithm 2 and the initial condition V (8, a) = 0 in
Algorithm ensure that Qf (s, a) E [o, H - h 1] for all (k, h, s, E [K] H x S x A. We let
SH 2)² and set as in (9) for Algorithm 2. We define
ΛF = 4n,1 (s,a)
k.t
w (s) (s,
+ (s,
if 0, if < 0:
(27)
w +1 - (s. a),
(minfe 1)) t) if 0,
91 ( a)
(28)
(max (6
((H--) -A) ,),tt) 1 <
Indeed, qi defined above is equivalent to of.r. defined in (8). It can also be verified that G (())
Q, a) & log( (2)). where G1(-) (-) is defined in (18) and 92 is defined in (16). We have the following
result which shows that Algorithm 2 satisfies Condition 2 (a restatement Condition 1) with high probability.
15

---

Under review as a conference paper at ICLR 2021
Lemma 6 Under Assumption 1, for any ò E (0, 11, with probability at least 1 - 6, Condition 2 holds for Algorithm with eı 1, ! Volgg( H/0). m a) V o 8, a) - (s,a) and
qu as defined in (28).
Proof.
Let us fix a tuple (ki h,) [K] [M] 8 x A. Then, have
(s,a)) w 1= () (A (AA)))
Σ
(h) (e - 11 +1 (29)
TElk-11
by Line 4 of Algorithm 2, and
Ex-Pa( s,ae &.V (+') Is ((ss,,,)) ( - -1dds' +1
(h(s,a) ())TO 0n+1
(h(s,a) a)(s,,)TTr
(oaaa)(())) ((A))- -1,00 +1
()) (((A)
Σ
(7 aj (0) Tm d. On
+1
TE|k-11
Σ rE[k-1]
(h a7)) -E 1 Ve 1]
+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 A positive definite by construction, the fourth step holds by Line 3 of Algorithm 2, and the last step holds since
a) On = -fs (ss,,, on (e - 1)ds' -gg-PsS I s.a) V.
for [K]. which is due to Assumption 1. Now consider the cases 3 > 0 and B < 0 separately.
Case 3 > O. Recall gf defined in (27) and d in (16). To control G1. we can compute
vi q2 as)
(%, a) w + Brrnra s.aee (o)
a)) ((A))-
Σ
oh o/) (eLVE E.aon I ge
(
rE(k-1
- A of a) (A
0
< |S1 1S21,
(31)
82
where the first step holds by the definitions of qf and F2, and the second step is implied by (29) and (30). We control each of S, and S2. For St, we have
EE og B. (T a.) (e (e 1 -]
Σ
VI 2(1)))))
(AE)
by the Cauchy-Schward inequality. On the event of Lemma 8, further have
| S 8H 1| / /log(22KHH/)) (10 a))l
for some universal constant
> Now for S2, we have
|8a S À | a) Al 1101 100lla8))
16

---

Under review as a conference paper at ICLR 2021
VA- 1x-1lof(s (A-1lof(e..)llaat)>> 110
S <vd (1, ())la))))))))
where the first step holds by the Cauchy-Schwarz inequality, the second step holds since A č A-I and the last step holds by Assumption that | ll2 S Vd. Plugging the bounds on S₁ and S into (31), and using the fact that À = (c 1)2 and the definition of Dy. we have
0% (T, T wh Eg x.a) ea)ee.Vhi Vill
S (s,
We choose C, c++ in the definition of (s, a) in Line 6 of Algorithm 2, and we have
0 S q S 20y e 31 dlog ||x a) 1KA
(32)
(x.0))
Since (32) implies of 92 and Lemma implies Φ2 S (HH-)) h), we can infer that qi 2 92 from the
definition of Fı = min ( (HH-)) h)), q8 } in (28). Then we have < q1 Q2 S q 92. By Lemma 1, we also have @1 2 02 1.
Case 3 < O. Similar to the case of 3 > 0, we have
Q2 96 (s) S | 1/ /dlog(2dKH/0) 110 ((())))))
If choose Cy c 1 in the definition of 1// (2, a) in Line 6 of Algorithm 2, the above equation
implies
0 S 92 ot s 20
(dlog(2dKHH0)
|10 a 11(ag)+
(33)
(G.0)
Therefore, using the same reasoning as in the case of B > 0, we have 0 42 S 92 by the definition of 91 in (28), we have 91 2 e
o.. Also,
The proof completed by invoking Lemma and recalling the identity a))(a)))))-- V (A*) (s,
Next, we give bound for the quantity ExE(K Eneim min(1, minfl,mis m (s a.)
Lemma Under Assumption 1, let (m a)} be as defined in Lemma 6 and we have
ΣΣ Σ min m a/1 S /2aK
KE[K] bE[M]
where log(2dK/6).
Proof. We have
Σ
min(1, m at:)
kE[K] HE
Σ VK
min(1, 1, (s (A))) -A a/)
HE[H]
KE[K]
H H2dKK..
where the first step holds by the Cauchy- inequality, and the last step holds by Lemma 10. 0
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.
17

---

Under review as a conference paper at ICLR 2021
E. AUXILIARY LEMMAS
We first present a concentration result.
Lemma 8 Let À (E 1) in Algorithm 2. There exists universal constant 0 such that for any E (0, 1] and hk, [K] x [H], with probability 1 - 6, we have
Σ (8h (.)))))))))) rE
(e (. -B Ba ( )
V (4266')
(at) 1 S ccl - -1| 1I (olog((d H/
Proof. The proof is adapted from that Cai et al. (2019, Lemma D.1) by using the fact that for any function V S + [0, H.. we have
E 3V(")) -lo')-BesPat s,ae 8 < - -11,
sup ())xxxx)
and that Assumption implies
1/8 (s,,,,8) (ov(6))1)do')) v -1 (s,a)ESxA
sup
The next few lemmas can help control the sum of the terms fo (sh at) 2 {
Lemma (Cai et al. (2019, Lemma D.3)) Let {0,}12 be sequence in Rd. Let Ao E Radd positive-definite matrix and A, = Ao + Σ Ej p50 Then any E Zoo we have [dc((A+t1)
Σ min (1, 0 A/ Φ,} 2 det(A1)
JEN
Lemma 10 Let @e 1) in Algorithm 2. For any h [H], we have
Σ
min 0f (5 a (A of a 2di,
kE[K]
where log(2dK/6).
Proof. By construction of Algorithm 2, we may define Al Ala so we have
A = Ag
Σ
07 af (o (5%%, T.
rE(k-1]
Since ( af)1l vdle for all (k, h) [K] [M] implied by Assumption have for any h E [ that
A +1
Σ
of T + ATa = ( - -1 + A)Ta-
[E[K]
Given A = 8
2 we have for any [H] that
dAt(A, AK+1)
dK 8H - - +
log
< d log
(A3(
A
< dlogldK + 1]
< di.
We now apply Lemma 9 to get
det(Ak K+1) det(AA)
Σ min of (st
ot) ((A)()))))))))))))) "of at:}} < 2log
kE []
- 2de,
as desired.
18

---

Under review as a conference paper at ICLR 2021
F PROOF OF COROLLARY 1
d N
The result follows from Theorem 2, as well as the fact that limg-u
and
18
s 1811 1.
G PROOF OF THEOREM 3
First of all, it can be seen that Line 5 in Algorithm 3 and the initial condition V (8, a) = 0 in Algorithm ensure that Q (8, a) E [0, H - h 1] for all (k, 8, a) E [K] x [H] x S x A. We fix
a tuple (k, h, s, [K] x H x S x A. Recall that 7a is as defined (13). For Algorithm 3, we let
maxpepk Ss P(s' s, a) V (6') ds', min Is P(s' 88, s,a)e (0
if > 0, if <,
a1 ( as)
(34)
which is equivalent to ( the result below, which verifies Condition 2 (a restatement of Condition 1) for Algorithm 3 under the general function approximation.
(s,a) a) defined in (15). Recall the definitions of Ep and 2 (11), We have
Lemma 11 Under Assumption 2, for any 8 (0,1] the following holds with probability at least 1-6. For all (k, h, 8, a) E [K] [ x S x A, Condition 2 holds for Algorithm 3 with c₁ = 1, = 1, paX 2r(8, a, Vi=1) minrep; 2r(8, a, vi+11) and q as defined in m (s, = |
(34).
Proof. It is not hard to see that by the definition of qi in (34), we have qi E [min e @HHH))) max ((H-))
Recall the definitions of da in (16) and (-)- in (18); holds that Gi = Q [og] On the event of Lemma 14, have Pa Pk.
Case B > O. By definitions of qı and Q2 and the fact that Pa E P we have qı 92. We can also derive
S P(s' Vi [ Ph(s') 8, 1i
91 -2
max PEP,
P(d' 18, s. v1)))) min PEP ( P(s' 8, a.ae
< max PEPE
max PEPÉ J
P(s') s V.inl)) -1)ds'
min PEP
/ P(s' s, (. - 1)ds'
= =leAh - 1 g m (8, a)
where the second step holds since Pn. Pli and the third step holds since Is P(s' 88, s,a)do' 1.
Case 3 < 0. By definitions of and d2 and the fact that Ph E Pk: we may deduce that Q1 42-
Also, we have
Q2 91 / Pa(s'
s, a. 2 min PEP: P(s' 1ss ee min PEP: ( P(s' | aj
/ P(s' a) as, (
max PEPE
min PEPA
P(8
(1))6' (-1) max PEP
P(s' B.
J
Js.
P(s' ss e @hiilll'))d
P(s' (od(ssa)(( - &.Viisld')
max PEPE J
min PEP
J
-
(s,
19

---

Under review as a conference paper at ICLR 2021
where the second step holds since Ph. Ph, and the fourth step holds since Is P(s' |s 1.
Finally, invoking Lemma completes the proof.
The following lemma controls [bE(K] Ene(m min ( af)
Lemma 12 Let d d2 (2 /K). Under Assumption 2, for any ó (0.1), let (s, a)} be as defined in Lemma 11 and Ç be as defined in (12), then with probability at least 1 - 6, we have
Σ Σ min m (sh a/)3 S 2H min(d, + 20H 20H/dKs dKç. AE[K]NE[H]
Proof. Since min (1, my (sh, a s ( al) for all (k, E [K] [H]. For each fixed h E [H) by Lemma 15, we have
min(1, (sh, at) s
10SH - | -1 min KJ + 5
kE(K]
[2108M -1 -mimfd 5
5
2 min(d, + 1eSH 1 V-2dK
2 min [d, K} 20 dK [Lo (Ni)x(P, |l (l.,,)) -H/) + vlo(44K2H/0
where the last step holds since 7 where is given in Lemma 14. Summing both sides of the above equations over E [H] results in the desired bound.
Recall the definition of M from Theorem 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, -allud functions for some number D > O. We define ((X,, Yx)) be series of random variables such that each X, in the domain of the elements of function set 2, and each Y, E R. Let F = {Fr Jr be set of filtrations such that for all т 2 1, the random variables (X1, .i..... X,-1, Y,, is F meassurable Furthermore, we assume there exists function E Z such that IE[Y, -- 2 (X,). For any & > we denote by N (Z, 11 the e-covering number of Z with respect the supremum norm |||| 22|1o0 sup, 2 (2) 22 (x)) We define
2 = argmin
(x(x,) - X,)
ZEZ rE(1]
and for 2 0, let
2,(1) = = E SEZ: Z: Σ - (xx))) S 5n
TE/(]
We record concentration result.
Lemma 13 Suppose that for any T 2 the random variable Y, 2² =xx)) is conditionally o-sub- Gaussian given filtration F,-1- Let
72 80² log (We 11x0)//)) + 4et (D+ (oglo((1((
Then for any and & E (0, 1}, with probability at least 8 we have =" E ((((6))))).
20

---

Under review as a conference paper at ICLR 2021
Proof. The proof can be adapted from that of Russo & Van Roy (2014, Proposition 6).
In the following, we use the shorthand ? = YG. where Go defined in (13) and used in Line 4 of Algorithm 3.
Lemma 14 For any 8 E (0, 1] and
7= 10 20 - 12 [og (Wix (lbo,)) H/5) + vlog(4K2H/5)
then for all (k, h)) E [K] [H] we have Ph. Phi with probability least 6.
Proof. We first note that for any h)) [K] [M]. Line 3 in Algorithm 3 can be equivalently written as
((e - - P(s') (T) (e - 1)ds')²,
Ph argmin
Σ
PEP
rE(R-1)
since Ss P(s'| 8, a ds's's 1. Recall the definition zp in (1I). For any (k, h) [K] x [.]],
we set 2 2, Y₁ e (+ 1, X = (sh, at V v++1) and =" 21,,- Then, we have that Y - =Xx,) is conditionally (lea" - 11) 1l)-suub-aaat Suu-Gaussian for T E [k - 1] given a properly defined filtration. By the definition of Pk we have (+ = {zp: P E Pk J. By definition of 7, we have
7 7h (5/ H, e -1 1K)
for all ls E [K]. where -).--)) as defined in Lemma 13. By Lemma 13 with D = a = |
and S 9H 1 KK, with probability at least 1 5/H and for all & E [K]. we have
E 1 8H /K) C Z6(r).
thus implying Pa. E Ph. Applying the union bound over E [H], we have that Pa. E Pk with
probability at least 8. Now we show that (2, || |1>o) S WN/leam-ijfa || llx,1) for any
E > 0. Let {V : S [0, H]}. For any P,P' and their corresponding 2p, 2p E Z, can compute
1/ P(s s (((()) -Ids'' - P'('' (s(''ss,)(ee () D)ds'
|| =pprls0 =
sup
(sSx
$ 11. sup
PP(s' (15'(8,0)= P'(6' |s,a)|
(s.0)ESxA
=|e00 11 ||P P' P'
as desired.
We have the following result on the eluder dimension.
Lemma 15 Let Z Z and d dimg (2, | - -K).K). For any K 1, B R and 7 0,
have
(=(0k) 2' (xx)) S l -1|+ 1 -1 min(d. K} + 4
sup (2,)))
KE[K]
This result an adaptation of Russo & Van Roy (2014, Lemma 5) with C -|eHH therein.
Proof.
21


Reviews:
[{"review_id": "qBU_lRRob1b", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary:\n\nThe 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.\n\n##########################################################################\n\nReasons for score: \n \nOverall, I vote for accepting. I think this paper considers an important topic: risk-sensitive reinforcement learning, and provides a first step in establishing theoretical foundation under that setting with function approximation. \n\n##########################################################################\n\nPros: \n\n1) The paper tackles an important issue: risk-sensitive reinforcement learning with function approximation, and shows regret bounds that are near optimal under some assumptions.   \n\n2) The value iteration based meta algorithm framework and the meta regret bound provides a nice abstraction beyond concrete implementation under different assumptions. It might benefit future studies on function approximation under risk-sensitive reinforcement learning. \n \n\n##########################################################################\n\nCons: \n \n1. The technical tools used in this paper seem to be based on a combination of ideas from Fei et al. (2020), Cai et al (2019), Russo and Van Roy (2014) and other papers. The analysis itself does not bring new insights.\n \n\n##########################################################################\n\nMinor comments: \n\nIt might be worthwhile to discuss other definition of “risks” beyond entropic risk measure under the risk-sensitive reinforcement learning settings, and mention any relevant theoretical results under those definitions.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "eZsEJMdyE1Y", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers a finite horizon episodic RL problem where the objective is risk-sensitive using the entropic risk measure. The paper proposes two algorithms based on the optimism in the face of uncertainty principle, one for linear function approximation and the other for general function approximation. Regret bounds are derived for both algorithms. \n\nThe strong points of this paper are that the algorithms proposed seem well grounded based on the optimism principle, and that a formal regret analysis is provided for general optimistic algorithms in the context of risk-sensitive object, which is then specialized to the two algorithms proposed. \n\nOne weak point of this paper is that the algorithms proposed do not seem very practical. What’s proposed for general function approximation is mostly a conceptual algorithm. It’s unclear how it could be applied in practice. Even with linear function approximation, it seems that the algorithm requires storing all past iterates as well as sweeping over all states and actions for each episode, which is extremely computationally costly. \n\nEven though there’s some nice theoretical contributions, I am not sure if this is the best venue for this paper, since it’s not really related to representation learning… (although the conference has been constantly evolving over the years). \n\nGiven the points above, I am leaning towards rejection.\n\nThe organization of the paper is pretty clear. One minor suggestion is that the authors might want to compress some of the background on value functions to make room for a concluding section. \n\nThe paper is easy to read in general, but I find the naming and terminology like “meta RSVI” and “meta regret analysis” a bit confusing. It seems to me that the proposed algorithms fall straight under the OFU principle, and it might be more straightforward to just say that instead of coming up with new names like MetaRSVI. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "IomtRgA96OG", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nPros \n\nThe idea of using entropic risk value functions in RL is a very interesting. \n\nThe paper is well-written and the proofs are present in details. \n\nCons\n\nMy major concern is the novelty in this paper. It is closely related to a recent paper, which considers the same entropic value function in RL, but focus on the tabular setting:\n\nFei, Y., Yang, Z., Chen, Y., Wang, Z. and Xie, Q., 2020. Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regret. arXiv preprint arXiv:2006.13827.\n\nThis paper is trying to extend the results in [Fei et al. 2020] to the function approximation setting. Then the key to decide if the paper’s contribution is enough is to see how hard such extension is. \n\nHowever, although [Fei et al. 2020] focus on the tabular setting, it seems that their proof techniques can be easily generalized to the linear function approximation setting (as they write the tabular representation using canonical basis, then the values could be written as the solution of a linear regression). I check the details of the proof and it indeed shares a lot of similarities with [Fei et al. 2020]. The major difference is how to choose a proper regularization (Lemma 10). \n\nMinor comments: \n\nTwo related papers that use entropic value functions in RL. \n\nO'Donoghue, B., 2018. Variational bayesian reinforcement learning with regret bounds. arXiv preprint arXiv:1807.09647.\n\nO'Donoghue, B., Osband, I. and Ionescu, C., 2020. Making sense of reinforcement learning and probabilistic inference. arXiv preprint arXiv:2001.00805.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "-XQs8jst0KD", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this work the authors studied the entropic risk RL problem and derived a regret bound of the entropic value iteration algorithm via the risk-sensitive optimism in face of uncertainty approach. Utilizing the theoretical framework of Osband 2014, they extend the results to entropic-risk RL with linear function approximations on the transition dynamics and value function and later with general function approximation in episodic MDPs.\n\nUnfortunately I am not very familiar with the recent theoretical exploration results with randomized value functions. On the high-level, I find the contribution of extending this to entropic-risk RL reasonable. One main question is why episodic MDPs are chosen for deriving the main theoretical results, and can these results be extended to more standard MDP frameworks such as discounting MDPs. Moreover, on top of the technical description, can the authors provide some intuitive explanations of condition 1 (which is a main RSOFU assumption that pivots most of the theoretical results) and some examples on when this condition is satisfied? \n\nWhile I understand this paper's main contribution is theoretical and appreciate the efforts for deriving that. Since the algorithm in analysis is fairly standard, it'd be great to see at least some simple, proof-of-concept numerical experiments to evaluate the tightness of the regret bound. Without that, it's rather difficult to understand the several theoretical results, compare with the references mentioned, and justify their usefulness. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: 
The paper considers the risk sensitive RL by exploiting entropic risk. The major contribution of this paper is providing the theoretical guarantees for the proposed risk-senstive value iteration with function approximation. 

The major concern of this paper is the similarity to the existing work in (Fei et al., 2020). I encourage the authors to reorganize the paper and emphasize the differences to highlight the major contribution. 
Decision: Reject