Provably Efficient Iterated CVaR Reinforcement Learning with Function Approximation and Human Feedback
Authors: Yu Chen
Yihan Du
Pihe Hu
Siwei Wang
Desheng Wu
Longbo Huang
Venue: ICLR 2024 poster (2024)
Keywords: Reinforcement Learning
Iterated CVaR
Learning Theory
Function Approximation
Human Feedback
Primary area: reinforcement learning

Abstract: Risk-sensitive reinforcement learning (RL) aims to optimize policies that balance the expected reward and risk. In this paper, we present a novel risk-sensitive RL framework that employs an Iterated Conditional Value-at-Risk (CVaR) objective under both linear and general function approximations, enriched by human feedback. These new formulations provide a principled way to guarantee safety in each decision making step throughout the control process. Moreover, integrating human feedback into risk-sensitive RL framework bridges the gap between algorithmic decision-making and human participation, allowing us to also guarantee safety for human-in-the-loop systems. We propose provably sample-efficient algorithms for this Iterated CVaR RL and provide rigorous theoretical analysis. Furthermore, we establish a matching lower bound to corroborate the optimality of our algorithms in a linear context.

Published as a conference paper at ICLR 2024
PROVABLY EFFICIENT ITERATED CVAR REINFORCE- MENT LEARNING WITH FUNCTION APPROXIMATION
AND HUMAN FEEDBACK
Yu Chen', Yihan Du", 1 Mss Tsinghua University, 3 Microsoft Research Asia,
Pihe Hu', Siwei Wang', Desheng Wu**, Longbo Huang ECE, University of Illinois Urbana-Champaign 'SEM, University of Chinese Academy of Sciences cheny:23emails tsinghua. edu. cn, yshandu@illinois edu, hph hph19@mails. ts twingnuuua.... edu. en, Siweiwanngmmcrosooefee com, dwu@ucas.ach accassacc.cm
srrgbohtangttsinngnge edu.
ABSTRACT
Risk- seskisensitive reinforcement learning (RL) aims to optimize policies that balance the expected reward and risk. In this paper, present novel risk-sensitive RL framework that employs an Iterated Conditional Value-at-Riss (CVaR) objective under both linear and general function approximations, enriched by human feed- back. These new formulations provide principled way to guarantee safety in each decision making step throughout the control process. Moreover, integrat- ing human feedback into risk-sensitive RL framework bridges the gap between algorithmic pecision-making and human participation, allowing us to also guaran- tee safety for human- in in-the-loop systems. We propose provably sample-efficient algorithms for this Iterated CVaR RI. and provide rigorous theoretical analysis. Furthermore, we establish matching lower bound to corroborate the optimality our algorithms in a linear context.
INTRODUCTION
Reinforcement learning (RL) (Russell 2010 Sutton & Barto 2018) is general sequential decision- making framework for creating intelligent agents that interact with and learn from an unknown environment. RL has made fround-breaknng achievements in many important application areas, e.g., games (Mnih al. 2015) Silver et al., 2017). finance (Hull, 2003) and autonomous driving (Sallab) et al. 2017). Despite the practical success, existing RL formulation focuses mostly maximizing the expected cumulative reward a Markov Decision Process (MDP) under unknown transition kernels. This risk- criterion, however, is not suitable for real-world tasks that require tight risk control, such as automatic carrier control (Isele et al. 2018; Wen et al. 2020). financial investment (Wang et al.) 2021 Filippi et al.. 2020) and clinical treatment planning (Coronato al. (020). To address this limitation, risk-sensitive RI. has emerged as promising research area, which aims to incorporate risk considerations into the RI. framework.
rich body of works have considered various risk measures into episodic MDPs with unknown transition kernels tackle risk-sensitive tasks. Among different risk measures, the Conditional Value-at-Riss (CVaR) measure has received an increasing attention in RL, e.g., Chow et al. (2015); Du (023) Rockafellar et al. (2000); [Stanko Macek (2019); Bastani
(2022) Wang al. (002a)) CVaR is popular coherent risk measure (Rockafellar et al.) 2000), which can be viewed as the expectation of the worst a-percent of random variable for given risk level a E (0. 1]. plays an important role to avoid catastrophic outcomes in financial risk controlling (Filippi et al.) 2020), safety-critical motion planning (Hakobyan et al., 2019), and robust decision making (Chow) al. 2015)
However, existing CVaR-based RL works (Bastani et al.) 2022 Wang et al. 2023a; Du et al. 2023 Xu et al., 2023) mainly focus on the tabular MDP, where the state and action spaces are finite, and the complexity bounds scale polynomially in the sizes of state and action spaces. As a result, the application of tabular MDPs can be limited, since in practical problems, the state and action spaces are often large or even infinite.
$ Corresponding authors

---

Published as a conference paper at ICLR 2024
To extend the risk-sensitive RL theory and handle large state space, in this paper, we study Iterated CVaR RL with both linear and general function approximations in episodic MDPs (ICVaR-RL with linear and general function approximations). One key distinction of our work from existing function approximation results (Jin et al. 2020; /hoou et al. 2021a Fei et al. 202T) is the Iterated CVaR objective. Iterated CVaR (Chu & Zhang 2014 Du et al. 2023)
important variant of CVaR, which focuses on optimizing the worst a-percent performance at each step, and allows the agent to tightly control the risk throughout the decision process. In this paper, we tackle the ICVaR-RL with function approximations by two novel sample-efficient algorithms, i.e., ICVaR-L (detailed in Section 4.1 and ICVaR-G G (detailed in Section 4.2)
We further investigate ICVaR- RL with human feedback and present provably efficient algorithm ICVaR-HF with general function approximation. Our exploration is motivated by the rapid develop- ment of Large Language Models (L..Ms) such as ChatGPT. These models, as demonstrated in vari- ous studies (Glaese et al. 2022, Ouyang et al. [022]] Lee et al.) 2023 Gulcehre et al., 2023), operate in diverse conversational landscapes where precisely defining reward signals is challenging. This challenges the conventional RL paradigm, underscoring the crucial role of infusing human feedback (Christiano et al. 2017: Stiennon et al.] 2020; Wu al. 2021: Ouyang et al., 2022). Furthermore, the risk control in intelligen systems such as ChatGPT is significant for preventing the generation of harmful offensive content (Zhuo et al., 2023 Qi al., 2023). This critical imperative under- scores the need of approaches that are inherently risk-sensitive, especially in the intersection of large language models and RLHF. Our work infuses risk sensitivity into RLHF paradigms and formalizes the first risk-sensitive RLHF structure for further theoretical understanding of risk-sensitive RLHF.
However, the Iterated CVaR objective imposes significant technical challenges in the theoretical analysis of the function approximation and human feedback setting. (i) Since the Iterated CVaR measure is a quantile expectation on the distorted distribution, it destroys the linearity of the risk- neutral Bellman equation and makes it hard to estimate the true value function. Therefore, existing rest-neutral RL algorithms for function approximation fail in ICVaR-RI. and new techniques are needed to handle this nonlinearity (See Section (.T) (ii) In our function approximation setting, one cannot calculate the CVaR operator and estimate the transition by tranditional sample-mean tech- nique efficiently, since the size of state space can be very large or even infinite. To address these dif- ficulties, we develop novel CVaR approximation and parameter estimation methods in Section [.] (ii) The standard regret analysis For risk-sensitive setting. For example, since the preference- based human feedback a comparison of the cumalative rewards of two trajectories, it is natural to apply this feedback to the risk-neutral RL (to maximize the cumulative rewards), while it can be non-trivial to apply this feedback to a risk- sensitive setting since the regret decomposition process for risk-neutral RLHF fails in analyzing the risk-sensitive goal. Moreover, previous online reward MLE algorithms focus on finite reward function set (Wang et al. 2023b), while we are dealing with an infinite reward function set.
RL with human feedback is not suitable for our
In this paper, we present provable efficient algorithms for ICVaR-RL with function approximation and human feedback, and develop novel technical tools to address the challenges in Section 4 and 5 Our contribution can be summarized as follows.
(i) We develop a provably efficient (both computationally and statistically) algorithm ICVaR- I. for ICVaR-RL with linear function approximation, which achieves the regret upper bound a(Va-(M+1))
K), where a is the risk level, d is the dimension of state-action fea- tures, is the length of each episode, and K is the number of episodes. Moreover, we con- struct hard-to-learn instance for ICVaR-RL. with linear function approximation, and establish an ( regret lower bound. This shows that algorithm ICVaR-L achieves a nearly minimax-optimat dependency on and K, and the factor va- Hf in our regret bound is unavoidable in general.
(ii) For ICVaR-RL with general function approximation, we propose algorithm ICVaR-G. We prove that ICVaR- - achieves a regret bound of (H+1) based on a new elliptical potential lemma. Here Dp is a dimensional parameter that depends on the eluder dimension and covering number of probability set (see Section 4.2 for the details).
(iii) We further extend ICV to encompass Reinforcement Learning with Human Feedback (RLHF), incorporating general function approximation for both transition probabilities and reward modeling. We develop the first provably sample-efficient algorithm ICVaR-HF for sisk-sensi
2

---

Published as a conference paper at ICLR 2024
RLHF with novel discretization of infinite reward function set and regret decomposition method that achieves regret bound of parameter for reward function set, and m is the positive lower bound for the gradient of link function.
+ vm-IDR) where D is dimensional
RELATED WORKS
Risk-sensitive RL with CVaR Measure There are two types of CVaR measures, i.e. the static and dynamic (iterated) CVaR measures. Boda et al. (2006); Chow et al. (2013); Ott 2010); Yu ett al. (2018); Stanko & Macek (2019) study the static CVRR measure, which considers the CVaR of cumulan latve reward in tabular MDPs with known transition kernels. [astani et al. (2022) : Wang et al.
(2023a) investigate the static CVaR RL with unknown transition kernels. On the other hand, Du ct al. (2023) propose Iterated CVaR RL (ICVaR-RL), an episodic risk-sensitive RL formulation with unknown transition kernels and the Iterated CVaR measure, and studies both regret minimization and best policy identification in tabular MDPs. In addition, Xu et al. (2023) investigate a general iterated risk measure (including Iterated CVaR) in tabular MDPs. In contrast, we study Iterated CVaR RL with linear and general function approximations.
RL with Function Approximation He et al. (2022): Ayoub et al. (2000); Zhou et al. (2021a) b): Zhao et al. (2023) 3023;:10 Agarwal et al. (2022)
For risk-ncutral RL. Yang & Wang (020); Jin et al. (2020);
study linear function approximation
two types, Le., linear MDPs and linear mixture MDPs He
iet al. (2022); Agarwal et al. (2022) and Zhou et al.
(2021)) present nearly minimax optimal al-
gorithms for Linear MDP and linear mixture MDP, respectively, |Ayou al. (2020); Wang et al.
(2020) study risk-neutral RL with general function approximation. which assumes that transition probabilities belong to a given function class. They establish sublinear regret bounds dependent on the eluder dimension of the given function class. Fei et al. (202T) consider the first risk-sensitive RL with function approximation under the entropic risk measure, and [aa et al.) (2023) study RI. with the iterated coherent risk measure with non-linear function approximation under simulator assumption. Compared to Fei et al. (202I) and Lam et al. (2023), we investigate the function ap- proximation for RL with Iterated CVaR measure without the simulator assumption.
RL with Human Feedback Christiano et al. (2017) firstly propose the deep reinforcement learn- ing models that are guided by human feedback. Then, there are many empirical works concentrating on the framework when the reward is parameterized as neural network (Ouyang et al. 2022 Stien- non et al. 2020; Wu et al. 202T, Ibarz et al. 2018 Lee et al., 2023 Gulcehre et al.) 2023). Recently, Zhu et al. (003): Zhan al.j(2223)) a) develop the theory of preference-
RLHF in the offline setting and present the Maximum Likelihood Estimation (MLE) for reward functions. Waag et al. (2023b) present the first online reward MIE algorithm in the risk-neutral RLHF for finite reward function set. Compared to their results, we formalize the first risk-sensitive RLHF problem, and present theoretical analysis for ICVaR-RO -RL with general function approximation for infinite transi- tion and reward function sets and comparison- human feedback.
PRELIMINARIES
3.1 EPISODIC MARKOV DECISION PROCESS (MDP)
We consider an episodic MDP parameterized by a tuple M = (S.A, H. where S and A represent the state space and action space respectively, K is the number of episodes, and H is the length of each episode. For step h. Pr, : S x A - ASS) is the transition kernel.
At the beginning of episode k initial state 8k,1 is chosen by the environment. At each step h [H], the agent observes the state &k,,, and chooses action 0g TH (s,,)) where T. S A is a mapping from the state space to action space. For step ht PA : S x "A - A(S) is the transition kernel which unknown to the agent, and ты S A [0, 1] is the reward function which is deterministic and known to the agent] Then, the MDP transitions to a next state sk,++1 that is drawn from the transition kernel PA(- Sk.h, h).h). This episode will terminate at step H + and the agent will advance to the next episode. This process is repeated K episodes. The objective of the agent is to determine an optimal policy n so as to maximize its performance (specified below).
This assumption is commonly considered in previous works Du et al. 2020
2023 Pei et al. 2021
Jin al.
Zhou al. (2021a): Modi al. (2020)
3

---

Published as a conference paper at ICLR 2024
3.2 ITERATED CVAR RL
First, we give the definition of the Conditional Value-at-Risk (CVaR) operator which is firstly intro- duced in Artzner (1997.. For a random variable X with probability measure I and given risk level (0, 1j:
CVaRG == sup zeR [(2-
(1)
which can be viewed the expectation of the a-worst-percent of the random variable X. In this paper, we apply Iterated CVaR as the risk-sensitive criterion (similar to Du et al. (2023)) (.23)).The MDPs with Iterated CVaR measure The Iterated CVaR MDP aims to maximize the objective J(T) which can be expressed as follows:
J(x) (1) + CVaR, (22(22, 02) + CVaR Paasagaaaaaa P2(()22)2)
(ra(ss.ag as)
(2)
+ (... - (ru(sn,
where (8h, 0h (8))) is the trajectory generated by policy (Th : - A) and initial state 81- Maximizing this objective means finding the optimal policy to maximize the cumulative rewards obtained when transitioning the worst a-portion states each step.
To evaluate the performance of RL. algorithms, we adopt the regret minimization task. Consider the value function V S E and Q-value function QT, S x A I under the Iterated CVaR measure as the cumulative reward obtained when transitioning to the worst a-portion states (i.e., with the lowest a- a-portion values) at step h, + ,.....
QT a) = (s( + CVaR (Vi+ (s) = (s))
(3)
($) Vs S
For simplicity, we use C to denote the CVaR operator:
[CF(())(ssa) = CVaRs -(-
(V (V(s') sup
aek 21--1166 [P(= v)+
(4)
where - - P(s') s, az (s'( Let ** be the optimal policy which gives the optimal value function V (s) max, (s) for any E S. Prior work Chu & Zhang (2014) shows that л* always exists. In the regret minimization task, the agent aims minimize the cumulative regret for all K episodes, which is defined as
K
Regret(K) (K) := Σ ( (SK.1) VT (sR.1)),
(5)
where ² the policy taken by the agent in episode ht and V/"" (sk.1) V (sk.1) represents the sub-optimality of Notice that when a 1, the CVaR operator becomes the expectation operator, and Iterated CVaR RI. degenerates to classic risk-neutral RI..
3.3 LINEAR AND GENERAL FUNCTION APPROXIMATION
Assumption 1 (Linear function approximation Ayoub et al. 2020 Fei et al. 2021); Zhou et al.
(021a)). In the given episodic MDP M, the transition kernel is linear mixture of a feature basis S S A Rd, i.e. for any step h [H]. there exists a vector On IRd with O vd such that
Pn(s' s. a) (8h. Φ(5', s.a))
(6)
holds for any (s', a) S S x A. Moreover, the agent has access the feature basis d.
In this paper, we assume that the given feature basis & satisfying ( a)ll2 & 1 where (s, =
Eves 0(8', 8, a) ds'(") for any bounded function f S - [0, 1] and (s, a) E S x A episodic MDP with this type of linear function approximation is also called linear mixture MDP.
In addition to the above linear mixture model, we also consider general function approximation scenario, which proposed by Ayoub al. (2020) and also considered in Fei al. (202T)
This assumption is also considered in /hou al. 2021a Ayoub al. 2020
Fei al.
2021
4

---

Published as a conference paper at ICLR 2024
Assumption 2 (General function approximation). In the given episodic MDP M. the transition kernels [P - P where P is a function class of transition kernels with the form : x - (SS). In addition, the agent has access to such function class P.
Denote the bounded function set [[S,[0, H]) with form f set P, we define a function class 2
H]. With the given candidate
2 (=p(s, VV
(,a) : PPP), P(5 P(dd
SEES
where 2p is a function with domain AA Bis, [0, H]). For simplicity, we denote [PV] (s, :=
Eres P(ss s. (s') for function - R.
We measure the efficiency of RL algorithms under Assumption using the eluder dimension of 2 and covering number of P (similar to previous works Wang et al. (2020); Ayoub al. (2020); Fei et al. (2021). The formal definitions of eluder dimension and covering number is detailed in
Appendix H.1
ICVAR-RL WITH FUNCTION APPROXIMATION
4.1 ICVAR-RL WITH LINEAR FUNCTION APPROXIMATION
In this section, we propose ICVaR-L (Algorithm D optimistic value-iteration algorithm designed for ICVaR-RL with linear function approximation. ICVaR-L is inspired by the algorithm ICVaR- (2023) for tabular MDPs, and incorporates two novel techniques: an
RM proposed in Du E-approximation of the CVaR operator and new ridge regression with CVaR-adapte features for estimating the transition parameter On.
Algorithm presents the pseudo-code of ICVaR-L. ICVaR-L. performs optimistic value iteration in
Lines 9 where the key component is to calculate the optimistic Q-value function Qk in Line 6
with an approximated CVaR operator and an exploration bonus term. Notice that directly calculating
the CVaR operator [C2, (V)](s, a) supme[o.mn] {i (Op, (a==v>+ a))] is computationally inefficient. To maintain computational efficiency, we introduce novel approximation of the CVaR operator:
[C (V))(s := sup xeN, { x 1=-aa a
( ((.Ve--)-
(8)
where E is an accuracy parameter, Nr is discrete e-net of [0. HJ. i.e., No == {ns: : E [[//I]]-
Co.N. takes supremum over the discrete finite set N₂ instead of continuous interval [0, H], which can be computed efficiently. Notably, this approximation guarantees that the error between the approximated CVaR operator and the true CVaR operator is most 2s (shown in Lemma in Appendix D.I.
We execute z to play episode k in Line 11 which is greedy with respect the optimistic Q-value function. After that, we calculate the transition parameter estimator 0.+1, Lines 12 14 by new ridge regression:
(.nn O 0R-1A 1,6 arg minA| 10 Σ (#i. ((1+4)((s(,+1))) (0 (O (5t, ain)) (8))))a)))) )²
deerd
Note that we consider (Z -P Di as the regression features, which are different from
( 1i used in previous neutrall linear mixture MDP works (Zhou et al. 2021a b). The specific value of J&.A is determined in Line 12 Intuitively, the agent will explore the direction of the maximum norm of (ia 1)+ (Sk,h, (k.h) for every x Nr, such that every possible direction eventually well explored.
The efficient approximation technique and novel ridge regression en- ables us effectively handle risk-sensitive RL problems with CVaR-type -tpe measures while main- taining computational efficiency. Moreover, the space complexity and computation complexity of ICVaR-L are O + [NC ()) and [[(H)NG[ respectively. Please refer to Ap- pendix
Computation Efficiency
E for more detailed discussions.
We state the regret guarantee for Algorithm I as follows.
5

---

Published as a conference paper at ICLR 2024
Algorithm 1CVALLL
Require: risk level a (0, 1]. approximation accuracy > regularization parameter À 0,
bonus multiplier 3.
1: Initialize ALA < AI, f1,1- < -, (1, - 0 for any & e [K] and h e [M].
2: for episode 11=1,-.. .... K do
3: for step h H do
4:
// O'tiiiistic value iteration
5:
Bx, a suPSEN, (e te. (
6:
Qua(+.-) = =r((,)) ICarN No
(Vk,+t))((s>)) + 25 + Ba.()))))
7:
(-,a(-) - min max a,,, H3 (0) arg m Q (n,((;a))
8:
9:
end for
for step h L,..,, do
11:
Observe the current state sk, and take the action ax, = (5k.))))))
Calculate 2h,h arg max (a ii (sk (kih) 1 37,1
13:
AR+IA < REJ + V(enna -P (8R, aR ) (on. Dmana)+ (8k,,, (k,b))
14:
0x+1h To. Σ (EL, - Pe (8 ( (3
// Solution to
ridge regression
15:
end for
16:
end for
Theorem 1. Suppose Assumption holds, and for given 5 (0, set À
H² dH V a and the bonus multiplier 3 H dog ( (H*KH*) + VX. Then, with probabil-
ity at least -626 the regret of ICVaR-L (Algorithm satisfies
K
KH
4 log, K + 8 (10)
Regret K) < Ad
a + +33
SdH log(K) + 4H3 log
H-I
Comparison to Tabular ICVaR-RL Theorem states that ICVaR-L enjoys a regret bound + K). Intuitivelyy the exponential term of a is due to the inherent hard- ness of the learning in risk MDPs, and the term d expresses the complexity of the environment of MDPs. comparison to the regret bound S" AHH33) K) for tabular ICVaR-RL in Du et al. (2023), our result has the same order of dependence a and K as the tabular setting, but does not depend on S. which, in our setting, can be extremely large or even infinite. The detailed proof of this theorem is given in Appendix
To bound the regret of Algorithm D we develop several novel analytical tools. (i) We present a novel lemma which shows that the error of approximating [CP, (V)] a) by [Ca.Ne V)](s, (s a) is at most 2s (Lemma I in Appendix D.I.. By this lemma, have computationally efficient method cal- culate an E-approximation of the CVaR operator, which contributes to the computational efficiency of Algorithm D
(ii) We establish novel concentration argument in Lemma in Appendix D.2 which exhibits that transition parameter 02 lies in an ellipsoid centered at the estimator 0x.n- Then, we can bound the deviation between the transition parameter 0,, and the estimator for the CVaR operator An This result is formally present in Lemma 3 Appendix D.2
Moreover, we construct a hard-to-learn MDP instance for ICVaR-RL with linear function approxi- mation, and establish a regret lower bound [[Regret(K]) > (Theorem 4 and proof are detailed in Appendix [F] due space limit. We can see that ICVaR-L achieves a nearly minimax optimal with respect factors and K, and the factor -a- IT in our regret upper bound is unavoidable in general.
The formal theorem
4.2 ICVAR-RL RL WITH GENERAL FUNCTION APPROXIMATION
In this section, we present our results for Iterated CVaR RL with general function approximation defined in Section 3.3 Specifically, propose algorithm ICVaR-G (Algorithm 3). In each episode,

---

The detailed proof of Published as a conference paper at ICLR 2024
ICVaR-G (i) estimates the confidence set of the transition kernels by constructing set centered at the empirical mean with radius 9, and (ii) choose the policy with the highest possible ICVaR value in this confidence set of the transition kernels. The pseudo-code and detailed description of ICVaR-G presented in Appendix duue to space limit), and establish the following performance guarantee.
Theorem 2. Suppose Assumption 2 holds and for some positive constant E (0, 1], we set the esti- mation radius 9 == (2 log( 24r (e(....lloo
+1+ + V (lo((5k200)) Then, with probability
at least 26, the regret of ICVaR-G (Afgorithm)
satisfies
4KH
4 4log2 K +
Regret () E V 1+ V |2H + +2d( + 8ddz(Z)
log(K) + H3 log
(11)
where dz( == dimg Z, 1/VK) is the eluder dimension of Z, and Nc(P, lloo,,, 1/K) is the
c/verivging number of function class P under the norm || ll..1 By setting the dimensional pa-
rameter Dp- dg(Z) log(Ncc(P.l] |l llx. 1/K)), we have Regret K) Ö(va D H
The dominating term of the regret bound in Theorem 2 is
Dp which enjoys
the same order of a. H and K as the result of ICVaR-L in Theorem [ Moreover, in the case where Assumption | holds (i.e., linear function approximation), we have dg(2) (dd) and log( No 1z,, 1/K)) = (dd). This means that we can recover the O(va-(M--)d_11 bound in Theorem | The main analytical novelty of Theorem 2 includes novel elliptical potential lemma for a more fine seeeggaiied analysis of regret summation. We begin with bounding the deviation term supree.,, [Cp V a) - [CP, Vk,n+1l(ssa) a) < In. a), where I a) is defined as
(s, = sup 2F' (s,a, a) - inf 2r (s.a. - VEn-1)t) (12) P'ePe,h
PrePe.n
Intuitively, gM,4(s, a) can be interpreted as the diameter of PEA.. Then, our new elliptical po-
tential lemma (Lemma 9 in Appendix H.3) provides a more refined result by demonstrating
Ex Σn R (Sk,h, ak.h)) (log(K)) in terms of K. This result is tighter than existing result Li 2n 2h. Ih. A (Sk. aR.A) O(vK) in previous works Russo & Van Roy 2014%|Ayour et al. (0220);
Fei et al. 2021). With the refined elliptical potential lemma, we can then perform a more fine-
grained analysis of regret summation similar the proof of Theorem I
Theorem 2 is deferred to Appendix H
5 ICVAR-RL WITH HUMAN FEEDBACK
We further extend our results to investigate risk-sensitive RL in the human feedback (RLHF) setting. In this setting, the ground truth reward functions are unknown and the agent cannot observe numer- ical reward signals, but only receives comparison feedback. Specifically, the agent provides two trajectories to a human expert, and the expert judges which trajectory is better. Below we introduce the formal definition of comparison feedback, following previous risk-neutral RLHF works (Wang ct al. 2023b; Zhan et al., (023a|b). First, we assume that there is an underlying reward function which guides the feedback of human.
Assumption 3 (Underlying reward (Christiano et al. 2017 There is a unknown underlying re- ward r* for some known infinite function set R := fr : T
10. H]}. Every reward A - 10, 1] H and satisfies that
r consists of И reward functions, i.e., = {Th S
for every trajectory
(81, "1, 8n, an) T, we have r(7) = 2h-1 Ih rn(Snaah) For a fixed trajectory To = (50.1, a0,1. H H) we define a regularized reward T (T) == SH 2h-17h ap) rn (s0 (o.n) based on benchmark To-
This underlying reward assumption is a common assumption for comparison feedback and widely used in Christiano et al. (2017); Zhu al. (003)): Zhan et al. (2023a]b); WWan al. (202b)) Following Wang et al. (2023b). we assume that the human's 's preference is drawn from Bernoulli distribution parameterized by a general link function a.
Assumption (Comparison oracle Wang et al. (2023)). A comparison oracle takes in two trajec- tories T1, T2 and returns
Ber(o (m)) r* (rz))),
Foo any Pll := sUP Eves |P(5' s,,a) -P'(s' s.a]
7

---

Published as a conference paper at ICLR 2024
where (-) is known link function, e.g., sigmoid function. Here is the human preference (Ti, T2). The output o = indicates T1 > T2. and o indicates T2 > Ti. Moreover, we assume that the link function a satisfies the following properties:
Completeeees:: (0) and for any 1- H, H,, we have a(x) + o(-2)
Regularity: For any x E [-H, -H HJ. we have o' (2) 3 m for some constant m > O.
Remark The Fradley-Teery-Lane exactly the case when the link function (xx) is chosen as the sigmoid function ((1++co ((1+exx((=2) The completeness assumption is based on the common knowledge that the consistency of the comparison
(BTL) model Bradley & Terry (952). famous RLHF model, is
between trajectories should be upheld regardless of their given order. Thus, since [
72
(rr
r (T2)) 1. The regularity assumption common in the bandit literature (Filippi al.
PPr2 > 7
orr* (T2) (T())) we have ((r((T)
r (T2)
2010
Liet al. 2017) and necessary for the existence of optimal policy (Wang et al. 2023b).
Here we consider the general function approximation setting defined in Section 3.3 For given reward functions tro and possible transition kernel set P == (Pr)a-1 we define the optimistic
value function V/ recursively follows.
as = rn(s,a) rh (50, (0,A) + sup Co C2-P()))) (V++2 PeeP,
(s; = max Qh (ss as)) aEA
(13)
V.P (8;77) = O, V
Inspired by Wang al. (2020); Ayoub et al. (2020): Fei al. (2021),
develop risk-sensitive
algorithm iCV As shown in Algorithm 2 in Line | we choose a benchmark trajectory To by executing arbitrary policy. In every episode, we select estimated reward p* maximize the
optimistic value function V. (sk.1;TT.) in Line We calculate the optimistic value and Q-value functions Qu,A. VA, by value iteration, and determine the policy ^ in Lines 5 In Line we execute the policy x and generate the trajectory Tk, and in Line 10 we feed trajectories (Tk, To) to the comparison oracle. In Line 11 we adopt MLE to update the confidence reward function set RE+11 where we use the following log-likelihood function (which is also considered in Zhu et al. 2023 Zhan et al. (2023a b): Wang et al. (2023b)):
(r(
+1 (1- oi) o(-rro(Ti)) (14) Σ log (ō(o,, Tro (T.)) H(, Tm (T.) = (()))(T))) (T:))
In Lines 12 1.5
we apply the transition estimation. iPA.A to estimate the transition kernel PA in 13 by novel distance function Dist : P x Ezo. and select a confidence set P. in
Line
Line
14.
where Py, belongs to PA.,. with high probability (as detailed in Lemma 6 in Appendix H.2
The construction of distance function Dista, P P Rzo is inspired by previous neutall ( (2021). Recall the definition of function class 2 = {zp IP P) in Eq. Let Sx x B U (0, HJJ be the domain of zp. We use the functions in 2 to measure the difference between two probability kernels in P. Specifically, for all (s, a) E Sx A, let (s,
works Ayoub et al. (2020): eei al.
maximize the diameter of PA.n by function as a, Vx,
sup 21r (x- viatta+) inf 2F (s, (x (x- (x- Paan)))) (15) PrePe,
(K, a= : arg max
x][0.H] (FEP
Denote X1.A = (Sk,h, aR.h, ak.h, (II, (k.A) 1)) X. Then, we can define the distance functions Dista, IP') = (zp (Xa,n) zp (Xx.))) for F. P. Equipped with this distance function, we can estimate IP,, by PAAA = arg minFre Σx= & , where ōg (8k,441 8, a) and (s' a) 0 for any s' * 84,4+1- That is, PK,A is the one with the lowest gap to the sequence } which contains the information of history trajectories. In addition, PK. is the confidence set centered at PPr,A with radius 7. The theoretical guarantee for ICVaR-HF presented below.
8

---

Published as a conference paper at ICLR 2024
Algorithm 2 ICH
Execute an arbitrary policy to collect trajectory To (80,1, d0,1,"" 80 Ro.
2: for == = K do
3: Receive the initial state 1,,1
4: Choose the estimated reward pptt < arg max PER Vi (sk.11 Too). // Choose the estimated
reward pi
5: for h H.... do
6: Qua(-:)) - ::)) - P (80.b: (o,n) + sup ICS (V++i)((s))
7: V.(-) maX.Ed (u, a). x² arg max Qk,((:,0)
8:
end for
9:
Execute the policy n² / In every step h, receive state 8n,6 and execute action
OR.h = Ta. (*R.A). Then collect the trajectory т = (8H,1, 1R.1, 8k,2, dx,2, 8R, (R,H)).
Compare two trajectories Tk. To and collect observation oş from human feedback. Update the reward confidence set R&+1 - (r E R: Cx(r)) maxr'eR Lu(r') - 3R}.
11:
12:
for h 1,..,,,,.
H do
13:
Pk+1, arg minrep Σ Di (TP', 5x,n)) Estimate the transition kernel Ph
14:
Dist,, (P' PP,)) & 62) Construct the confidence set PA+1, = P Σx
15: end for
end for
Theorem 3. For some positive constant 8 E (0, 1], we set the estimation radius 3r = clog(K.
NB 1lxe 1/K) and 9 4112 (2f222log (2log) 22 (2M-No(PP.-llo...111
+ 1 v log(/)/50 (5k2/0) for
8
some constant Denote Then with probability at least 46, the regret of Algorithm 2 satiifies
Regret(K) & (K)) H-1 (VHDr + Vm-'DR)
(16)
where the dimension parameters Dp := dr log( Nc(P, (P, I111,,1, 1/K) detailed in Theorem DR (g(R) log( NR I-1la,, 1/K)). Here (R) dim x 1/vK) is the eluder dimension Rf and NR læ 1/K) ) is the 1/ I-K-baacketing number of R under norm || 11a00
2 and
The full proof presented in Appendix[] [ Notice that the regret bound for Algorithm Dis sublinear to K, making ICV the first provably efficient algorithm for risk-sensitive RLHE The first term of the regret is similar to the result in Theorem 2 for ICVaR-RL with general function approx- imation, which is the cost of learning the transition estimation. The second term is cost of learning the unknown reward functions, which requires our novel regret decomposition method to bridge the gap of the dislocation of the risk-sensitive value function and cumulative reward served for hu- man feedback comparison oracle. Moreover, we apply the discretization method to R. to get the log( No (R. | >l 1/K) K)) term (instead of the log((R.) term Wang et al. (2023b)), which remains finite even when R. is infinite reward function set.
CONCLUSION AND FUTURE WORKS
In this paper, we investigate the risk-sensitive RL with an ICVaR objective, i.c., ICVaR-RL, with linear and general function approximations and human feedback. We propose two provably sample efficient algorithms, ICVaR-L and ICVaR-G for function approximation ICVaR-RL, by developing novel techniques including efficient approximation of the CVaR operator, new ridge regression with CVaR-adaphe regression features, and refined elliptical potential lemma. We also develop the first provably efficient risk-sensitive RLHF algorithm ICVaR-HF with general function approx- imation, and develop novel theoretical techniques for regret decomposition of risk-sensitive RLHF and the reward MIEE for infinite reward set. This paper leaves several interesting directions for fu- ture works, e.g., further closing the gap between the upper and lower regret bound for ICVaR-RL. with function approximation on and H, and extending the risk-sensitive RLHF problem more risk measures and more human feedback settings.
'The formal definition of bracketing number is detailed in Definition 4 in Appendix I.1 which is a common
discretization for function class in ML. analysis (Geer 2000 Lau 2023

---

Published as a conference paper at ICLR 2024
7 ACKNOWLEDGEMENT
The work of Yu Chen, Pihe Hu and Longbo Huang was supported by the Technology and Innovation Major Project of the Ministry of Science and Technology of China under Grant 2020AAA0108400 and 2020AAA0108440 08403. The work of Desheng Wu was supported in part by the National Natural Science Foundation of China (NSFC) under Grant 71825007 and 72210107001.
REFERENCES
Yasin Abbasi-yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in Neural Information Processing Systems, 24, 2011.
Alekh Agarwal, Yujia Jin, and Tong Zhang. VOQL: Towards optimal regret model-free with nonlinear function approximation. arXiv preprini urXiv:2212.060/0 2022.
Philippe Artzner. Thinking coherently. Risk, 10:68-766 71, 1997.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference Machine Learning, pp- 463-474. PMLR, 2020.
Osbert Bastani, Jason Yecheng Ma, Estelle Shen, and Wanqiao Xu. Regret bounds for risk-sensitive reinforcement learning. Advances in Neural Information Processing Systems, 35:36259-36269, 2022.
Kang Boda, Jerzy Filar, et al. Time consistent dynamic risk measures. Mathematical Methods of Operations Research, 63(1):169-186, 2006.
Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324-445, 1952.
Yinlam Chow, Aviv Tamar, Shie Mannor, and Marco Pavone. Risk-sensitive and robust decision- making: a cvar optimization approach. Advances in neural information processing systems, 28, 2015.
Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances in neural information processing sys- tems, 30, 2017.
Shanyun Chu and Yi Zhang. Markov decision processes with iterated coherent risk measures. In- 2014.
ternational Journal of Control,
Antonio Coronato, Muddasar Nacem, Giuseppe De Pietro, and Giovanni Paragliola. Reinforcement learning for intelligent healthcare applications: A survey, Artificial Intelligence in Medicine, 109: 101964, 2020.
Pierre Devolder and Adrien Lebègue. Iterated Actuarial Journal, 201 2017(4):287-318, 2017.
measures: A false good idea? Scandinavian
Yihan Du, Siwei Wang, and Longbo Huang. Provably efficient risk-sensitive reinforcement learning: Iterated CVar ar and worst path. In The Eleventh International Conference on Learning Represen- tations, 2023. htRhttp:: / net hotpeaaeeeeeeeeettooooooooooooe
KHNW
Yingjie Fei, Zhuoran Yang, and Zhaoran Wang. Risk-sensitive reinforcement learning with function approximation: A debiasing approach. In International Conference Machine Learning, pp- 3198-3207. PMLR, 2021.
Carlo Filippi, Gianfranco Guastaroba, and Maria Grazia Speranza. Conditional value-at-risk beyond finance: survey. International Transactions in Operational Research, 2773):1777-1399, 2020.
Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. Advances in neural information processing systems, 23, 2010.
10

---

Published as a conference paper at ICLR 2024
Sara A Geer. Empirical Processes in M-estimation, volume 6. Cambridge university press, 2000.
Amelia Glaese, Nat McAleese, Maja Trebacz, John Aslanides, Vlad Firoiu, Timo Ewalds, Mari- beth Rauh, Laura Weidinger, Martin Chadwick, Phoebe Thacker, Lucy Campbell-Gilinghamm Jonathan Uesato, Po-Sen Huang. Ramona Comanescu, Fan Yang. Abigail See, Sumanth Dathathri, Rory Greig, Charlie Chen, Doug Fritz, Jaume Sanchez Elias, Richard Green, Soña Mokrá, Nicholas Fernando, Boxi Wu, Rachel Foley, Susannah Young, Iason Gabriel, William Isaac, John Mellor, Demis Hassabis, Koray Kavukcuoglu, Lisa Anne Hendricks, and Geoffrey Irving. Improving alignment of dialogue agents via targeted human judgements, September 2022. URL httpt:ttttiii..aa////pppp/patatt org/ abs 2209 14375
Caglar Gulcehre, Tom Le Paine, Srivatsan Srinivasan, Ksenia Konyushkova, Lotte Weerts, Abhishek Sharma, Aditya Siddhant, Alex Aher, Miaosen Wang, Chenjie Gu, Wolfgang Macherey, Arnaud Doucet, Orhan Firat, and Nando de Freitas. Reinforced Self Training (ReST) for Language Mod- eling, August 2023. URL htt.: org. wttp://////aaaaaaaoooo/.o /tab////3000 208 08998
Astghik Hakobyan, Gyeong Chan Kim, and Insoon Yang. Risk-aware motion planning and control using evar-constrained optimization. IEEE Robotics and Automation letters, 4(4):3924-39) 2019.
Mary R Hardy and Julia Wirch. The iterated cte: a dynamic risk measure. North American
Actuarial Journal, 8(4):62-75, 2004.
Jiafan He, Heyang Zhao, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforcement learning for linear markov decision processes. arXiv preprint arXiv:2212.06133 2022.
John C Hull. Options futures and other derivatives. Pearson Education India, 2003.
Borja Ibarz, Jan Leike, Tobias Pohlen, Geoffrey Irving, Shane Legg, and Dario Amodei. Reward learning from human preferences and demonstrations in atari. Advances in neural information processing systems, 31, 2018.
David Isele, Alireza Nakhaei, and Kikuo Fujimura. Safe reinforcement learning on autonomous vehicles. In 2018 JEEF/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 1-6. IEEE, 2018
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137-2143. PMLR, 2020.
Thanh Lam, Arun Verma, Bryan Kian Hsiang Low, and Patrick Jaillet. Risk-aware reinforcement learning with coherent risk measures and non-linear function approximation. In The Eleventh International Conference Learning Representations, 2023. iid Rw2OVybb
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Harrison Lee, Samrat Phatale, Hassan Mansoor, Kellie Lu, Thomas Mesnard, Colton Bishop, Victor Carbune, and Abhinav Rastogi. RLAIF: Scaling Reinforcement Learning from Human Feedback with Al Feedback, September 2023. TtLL:ttp:/// http:::://xxvv.ooooe
2309. 00267
Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contex- tual bandits. In International Conference on Machine Learning, pp. 2071-2080. PMLR, 2017.
Qinghua Liu, Alan Chung, Csaba Szepesvari, and Chi Jin. When Is Partially Observable Rein- forcement Learning Not Scary? In Proceedings of Thirty Fifth Conference on Learning Theory, pp. 5175-5220. PMLR, June 2022. URL httpt::///// ptctps://procest http::////cceedieeee mgg.ng.......... mll wwt.spprrsss..... v 1iu22f. html
Qinghua Liu, Praneeth Netrapalli, Csaba Szepesvari, and Chi Jin. Optimistic MLE: A Generic Model-Based Algorithm for Partially Observable Sequential Decision Making. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pp. 363-376. New York, NY, USA. June 2023. Association for Computing Machinery. ISBN 978- 978-1-4503-9911345 doi: 10.1145/3564244335556666
110. URLhttps. / //d1. acm. 222///22/00..11///52222
359.1661

---

Published as a conference paper at ICLR 2024
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforeement learning. nature, 518(7550):559-5533 2015.
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 Statisties, pp.
PMLR, 2020.
Takayuki Osogami. Iterated risk measures for risk-sensitive markov decision processes with discounted cost. In Proceedings of the Twenty-Seventh Conference on Uncertainty in Artifi- cial Intelligence. UAI'11, pp. 573-580, Arlington, Virginia, USA, 2011. AUAI Press. ISBN
9780974903972.
Jonathan Theodor Ott. A Markov Decision Model for Surveillance Application and Risk-Sensitive Markov Decision Processes. PhD thesis, 2010.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35: 2022.
Yi Qi, Xingyu Zhao, and Xiaowei Huang. safety analysis the era of large language models: case study of stpa using chatgpt. arXiv preprint arXiv:2304.0/246. 2023.
R Tyrrell Rockafellar, Stanislav Uryasev, et al. Optimization of conditional value-at-risk. Journal of risk, 2:21-42..20 2000.
Stuart Russell. Artificial intelligence a modern approach. Pearson Education, Inc., 2010.
Daniel Russo and Benjamin Van Roy. Eluder Dimension and the Sample Complexity of Optimistic Exploration. In Advances in Neural Information Processing Systems, volume 26. Curran As- sociates, Inc., 2013. URL
nips wttpsss.ccppaaaee capparr http://paeeeeeeeeeeeeeeeeeeeeeee catttracct.htmml]
hash/41bff200l 3aa.///000003330000eeaaa000533a0
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 39(4):1221-124)) 2014.
Ahmad EL Sallab, Mohammed Abdou, Etienne Perot, and Senthil Yogamani. Deep reinforcement learning framework for autonomous driving. arXiv preprint arXiv:/704.02533 2017.
David Silver, Julian Schrittwieser, Karen Simonyan, loannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354-359 2017.
Silvestr Stanko and Karel Macek. Risk-averse distributional reinforcement learning: A evar opti- mization approach. In IJCCI, pp. 412-423, 2019.
Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Rad- ford, Dario Amodei, and Paul F Christiano. Learning to summarize with human feedback. In Advances in Neural Information Processing Systems, volume 33, pp. 3008-3021. Curran Asso- hew.eeedddinn.eeeiiieseeee neurips cc cc/paaper/222/haaz. ciates, Inc., 2020. URL (bb.aa2222.ff444455555544 Abst
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Kaiwen Wang, Nathan Kallus, and Wen Sun. Near-mininax-oppiall risk-sensitive reinforcement learning with evar. arXiv preprint arXiv:2302.03201, 2023a.
Ruosong Wang, Russ Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33:6123-611 2020.
Yuanhao Wang, Qinghua Liu, and Chi Jin. Is RLHF More Difficult than Standard RL?, June 2023b.
URL httt:ttt httpg//ab/223000 14111
12

---

Published as a conference paper at ICLR 2024
Zhicheng Wang, Biwei Huang, Shikui Tu, Kun Zhang, and Lei Xu. Deeptrader: a deep reinforce- ment learning approach for risk-return balanced portfolio management with market conditions embedding. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp- 643-650, 2021.
Lu Wen, Jingliang Duan, Shengbo Eben Li, Shaobing Xu, and Huei Peng. Safe reinforcement learning for autonomous vehicles through parallel constrained policy optimization. In 2020 IEEE 23rd International Conference on Intelligent Transportation Systems (ITSC), pp. 1-7. IEEE, 2020.
Jeff Wu, Long Ouyang, Daniel M. Ziegler, Nisan Stiennon, Ryan Lowe, Jan Leike, and Paul Christiano. Recursively Summarizing Books with Human Feedback, September 2021. URL
httt:://arxiv wwwxiv.org/aaa...
org abs / 2109 10862
Wenhao Xu, Xuefeng Gao, and Xuedong He. Regret bounds for markov decision processes with recursive optimized certainty equivalents. arXiv preprint urXiv:2301.12660 2023.
Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernlss, and regret bound. In International Conference Machine Learning, pp. 10746-10756, PMLR, 2020.
Pengqian Yu, William Haskell, and Huan Xu. Approximate value iteration for risk-aware markov decision processes. IEEE Transactions Automatic Control, 63(9):3115-311 2018.
Wenhao Zhan, Masatoshi Uehara, Nathan Kallus, Jason D Lee, and Wen Sun. Provable offline reinforcement learning with human feedback. arXiv preprint arXiv:2305. 14816, 2023a.
Wenhao Zhan, Masatoshi Uehara, Wen Sun, and Jason D Lee, How to query human feedback efficiently in rl? arXiv preprint arXiv:2305.18500 2023b.
Zihan Zhang, Jiaqi Yang. Xiangyang Ji, and Simon S Du. Improved variance-aware confidence sets for linear bandits and linear mixture mdp. Advances in Neural Information Processing Systems, 34:4342-4355, 2021.
Heyang Zhao, Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu. Variance-dependent regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency. arXiv preprint 2xXi::3302.1037/ 2023.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learn- ing for linear mixture markov decision processes. In Conference on Learning Theory, pp. 4532- 4576. PMLR, 2021a.
Dongruo Zhou, Jiafan Hc, and Quanquan Gu. Provably efficient reinforcement learning for dis- counted mdps with feature mapping. International Conference on Machine Learning, pp. 22793-12802. PMLR, 2021b.
Banghua Zhu, Jiantao Jiao, and Michael I Jordan. Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. arXiv preprint arXiv:2301.11270, 2023.
Terry Yue Zhuo Yujin Huang, Chunyang Chen, and Zhenchang Xing. Exploring ai ethics of chatgpt: diagnostic analysis. arXiv preprint arXiv:2301. 12867, 2023.
13

---

Published as a conference paper at ICLR 2024
A NOTATIONS
In this appendix, we present the basic notations used in this paper.
For positive integer n, [n] f1,2, n). For non-zero real number RV(0), the sign operator sgn(r) == r/|r]- For a d-dimension vector x E R and positive definite matrix A e Raxd ||=|| :- V Az: be the norm of vectors in Ie under positive matrix A. The operator (x)* = max(x; 0}. For two positive sequences {A,]. [B,), A, ((B,) if there exists a positive constant such that An & cBn, for any n 1, and An, ()B,,) if there exists 0 satisfying & cB,- & A, for any n 1. Ö(-) further suppresses the polylogarithmic factors in O(-)
Measurable space and o-algebra. To discuss the performance of the algorithm any MDP instance, we should establish the formal definition the probability space considered in problem. Since the stochasticity in the MDP is due to the transition, we define the probabil- ity space as Ω (S x A)K and the probability measure as the gather of transition proba- bilities and the policy obtained from the algorithms. Thus, (2, FP),, where is the product o-algebra generated by the discrete o-algebras underlying S and A. To analyze the random variable step h in episode k, inductively define Fu, as follows. First let Fi,h := 0(11,1, 01,1,' 81.h- (1,h) for any E [H]. Then set Fu, := (F 8k,1; O,,1," Sk,h, (k,h) for any k [K] and h [H].
work the probability space
B THE OBJECTIVE OF ICVAR-RL
The fourmulation investigated in this paper iterated CVaR MDP, which is also studied by Hardy & Wirch x: Osogami T201T); Chu & Zhang (2014); Du et al. (2023). The Iterated CVaR MDP aims maximize the objective (T) which can be expressed as follows:
( 01) + CV (r2($2,
(2) CVaR Aa- (ra(S3: az)
(17)
+ Pall (#H($H
PP
where an = (s)())) for E [H] and 81 is the initial state. Maximizing this objective means finding the optimal policy to maximize the cumulative rewards obtained when transitioning to the worst a-portion states each step. With this objective, we consider the regret minimization setting to evaluate the efficiency of our RI. algorithms.
Application Intuitively, the ICVaR-RL concerns the worst a-portion situations at each step. This formulation most suitable for safety-critical applications where there is a fatal failure probability that leads to catastrophic states at each decision stage. Our goal is to find a policy that guarantees safety even when disaster might happen at each transition. For example, consider the financial dynamic investment (Devolder & Lebègue 2017), where one needs design a risk-sensitive dynamic investment strategy. There small probability, encouters catastrophic states. In order to guarantee safety each step, Devolder & Lebègue (2017) studies iterated CVaR measure under a Boncc--Scoles---e Merton market.
each time during execution, that the investor
14

---

Published as a conference paper at ICLR 2024
C NUMERICAL EXPERIMENTS FOR ALGORITHM 1
In this section, we evaluate the empirical performance of ICVaR-L (Algorithm T Since there no other prior comparable efficient algorithms for VCR with function approximation, we compare our algorithm with the ICVaR-VI algorithm Du et al. (2023) which is designed for ICVaR- RL in Tabular MDPs, and the LSVI algorithm Zhou et al. (202lb) for risk-neutral RL in linear mixture MDPs. These two baselines are the closest comparable algorithms to ICVaR-L in ICVaR- RL with linear function approximation. The empirical performance evaluated with respect the cumulative regret defined in Eq. 5
C.I EXPERIMENT ENVIRONMENT
In our experiments, we consider a risk MDP with states space S = {sp, 81, $2, Sdis) U S U S2 and action space A {a*) Asub- The agent will start at the initial state 8n- In this state, the agent will not receive reward. Then with action a², the agent will transfer to a conservative state Otherwise, the agent will transfer an aggressive state 52 with action asud E Asud. i.e. P[ 50, arub] = 1. With any action a E A, the agent will receive no reward state Sp, r(s1, a) 0.5 in state $1, and r(s2, a) in state 82. The conservative state 81 associated with S1. The agent at will transfer into s E S1 with equal probability by action a*. With sub-optimal action asuh E Asub, the agent will not move in state 81, i.e. P[st 81, asuo] = 1. In E S,, the agent will receive reward r(s,a) 0.6 and transfer back to with P[s) 5, s,aj for any a E A.
$1, i.. P[s1 8o, a
The aggressive state 82 is associate with Sp and disaster state Sdis- For any S2, we still have r(s, a) = for any a E A. However, the disaster state satisfies r($dis a) = for any a A. With probability 0.5, the state 52 and S2 will transfer to Saia. i.c. Plsais $2, al Plaaia s,a 0.5. Otherwise the agent will stay in {82] U S2.
In this MDP, the agent will receive a higher expected cumulative reward if it chooses asub at initial state to reach the aggressive state $2. However, is not a risk-sensitive choice. This is because with small a, the Iterated CVaR MDP prefer the conservative choice a* which gives stable return, where the aggressive choice may lead to a disaster state.
C.2 NUMERICAL RESULTS
We evaluate the cumulative ICVaR-type regret defined in Eq. 5 for algorithms ICVaR-L, ICVaR-VI (Du et al. 2023) and I.S ( et al. 2021b), where IC is our Algorithm for ICVaR-RI. with linear function approximation, ICVaR-VTi is the algorithm for ICVaR-RL tabular MDPs (Du
et al. 2023), and LSVI is the resk-neutral RL for MDP with linear function approximation (Zhou ct al. 2021b).
In our experiment, set A = H 6 and (0.15, 0.30J. We explore MDPs with different sizes of state space and dimensions, denoted by (S, d). We set (S, d) = (20, and (S, d) (40, 4) to represent small and large MDPs, respectively, with d as the feature dimension in Assumption For each case, we conduct 10 independent runs and report the average regret across runs with 95% confidence intervals. The results are presented in Figures and
15

---

Published as a conference paper at ICLR 2024
0.15. 81-120.
0-0.30, 1S. 60-220 2)
240
IOWSL
220
120
Cunuatie Koa tagee:
20
Cumuatis
60
60-
20
20-
120
230
300
600
500
100
240
300
400
500
The Nambar Epracdes
The Numbe Esboce
(a) S 20,4 d
0.15
(b) 20, d 2, cx 0.30
Figure 1: Cumulative regret for the case
20 and d
050.15. 01-400
4=00.30 d)-440.00
10W54
170
120
Currutatve (CAR RDW.R Rogeet
200
20
60
20
20
220
400
200
200
300
400
500
The Mambar Epraces
The Number Esboci
(a) S 40, d 4, a 0.15
(b) 40, 4, 0.30
Figure Cumulative regret for the case and d
As depicted in Figures and 2 ICVaR-L. consistently exhibits sublinear regret with respect to the number of episodes, validating our theoretical result in Theorem [ Notably, for each a (0.15, 0.30), the regret of ICVaR-L significantly lower than those of other algorithms.
Comparing ICVaR-L with the tabular algorithm ICVaR-VI, our algorithm demonstrates faster learn- ing of the optimal risk-sensitive policy, highlighting its efficiency in adopting linear function approx- imation. Furthermore, LSVI exhibits a nearly linear regret with the number of episodes, indicating its struggle to learn the optimal risk-sensitive policy.
These experimental evidences demonstrate the efficiency of ICVaR-L in risk risk-sensitive linear RL scenarios, providing empirical supports for its theoretical advancements.
D PROOF OF THEOREM 1t REGRET UPPER BOUND FOR ALGORITHM
In this section, we present the complete proof of Theorem
First, we give an overview of the proof. Appendix D.I we bound the approximation error of CVaR operator from taking the supremum in finite set Ne instead of interval [0, H] in Eq.
8 We propose Lemma 1 which bounds the error of approximating (V)](ss a) by [Cp (V)l(s, a). In Appendix D.2 we establish the concentration argument with respect to our estimated parameter 0
and the true parameter On for step h. Lemma shows that 10, -0,-0 A.,. S 3 with high probability,
16

---

Published as a conference paper at ICLR 2024
V(sy
a-quantile
(m 1)
VaRş (V)
me
So
Si
Figure 3: Illustrating example for Lemma]
and Lemma 3 upper bounds the deviation term based on the concentration of 0s .. In Appendix D.3
Lemma 4 implies that calculation of functions QU, and Vg is optimistic. Finally, apply regret decomposition method and bound the regret of Algorithm Appendix|Da.
D.1 ERROR OF CVAR APPROXIMATION
Below show that the errоr of approximating the CVaR operator by the technique of taking supre- mum on the discrete set No is small.
Lemma 1. Assume the transition kernel IP parameterized by transition parameter 0, i.e. P(s'
(0, p(s',, iiss,, 8, a)) for any (8', 18,a) S x 8 A. We denote
[CC(()](s, a) == [CS(V)](ssa), [Cg (V)] := C.. (V)](s,o).
(18)
For given constant O and fixed value function V : S - [0, we have
[0g (V)](s,
[C (V)] a)) x 2e.
(19)
Proof. First, we denote [Cg == x=- (P a). Letx : VaRş(V) [0, H).
Then, we have (V))(sss [Cg (V)](s,a) by propterties of CVaR operator (Rockafellar ct al. 2000).
If f E Nv. we have V x* (ms, (m 1)e) for some positive integer m E [[//e]].
[C)(v))(s, a). suffices consider x* Ng. Suppose
By the property of CVaR operator, we have
[C (V)](s,a) max {ICg. (V)] a), (CCg.m((V][s.
[C (m+ I)e (V)])(s))))
(20)
Then, we assume So =- (8' S: V(s)) & mε), S :- (8' E S: me < V(8)) < x+). Denote s* as
V(s*) = z* Noticing that x = VaR$(V), we have:
P(s' s <a S'ES,OS,
Σ
Σ
P(s s, a) > a
(21)
We give Figure where we sort the successor states s' S by V(s') in ascending order, and the red virtual line denotes the a-quantile line. The black virtual line denotes the value of ms, x², (m 1)s, and the sets of states Sg, S are marked on the figure.
By the Figure we can write the exact form of (C a) and [Cg a [s a) as
1
[Cg [Ca. [s,, a) me a
Σ P(s')s,a) -
V(ss))+
(22)
d'eSo
17

---

Published as a conference paper at ICLR 2024
[Co [(s,a) x²
Σ
P(s')s,a)( -v(s)}+
(23)
#'eSu
respectively.
Then, we have
[Cg [Cg.a*
[[8, a) - 1-g.m-](ss
<x* me 1
Σ
Pis' s, a. - ma)
Σ stES
P(s (,a))(**-(()))
a
s'ESo
(24)
< + a
Σ
P(s' (s,0)<** me)
d'ESqUS,
<2E;
where the first inequality holds by triangle inequality, and the second inequality holds by the defini- tion of Si, and the last one holds by the definition of a.
Thus
[Cg (Cg.No(V) (V)](s, - [C% a)
= [C8 (V)](s,a) max (108 (C, (V)]((s)))
(25)
[ -Cs [cg.m & 28,
where equality holds since [C a) 2 [Cg (V)]((s) by definition.
D.2 CONCETRATION ARGUMENT
We show that our estimated parameter 0R,6 is a proper estimation of the true parameter 0, for all prove that OR falls in ellipsoid centered at 0₂ with high
episodes k and steps h. In fact, probability. order to define bonus term, we define function Nx,n(-,)) that chooses the ideal based on given state-action pair (8,a) by
X Xg, a) arg max (a- (8, a)) zeN.
(26)
for x E Ne with Then, we denote v/k, (s, a) as the maximum norm of I1 +++ (8, (8,a)) given state-action pair (s, a) E A:
vh a) == e (e.) (s,
(27)
Lemma (Concentration on f). For Se E (0, 1), we have that with probability at least 1 8/H.
H + KH3
00, On <B= 1==H1ne H
dlog
+ +VA
(28)
8
holds for any l [K] and h [H].
Proof. First, we fixed an [H] Let A& (EE, (k.h) and m) = (0n, ( ax,1)) - (Fa, V (8k We have A is FR.n measurable, me is Fa measurable. And (1k lx a martingale difference sequence and --sub-Gaussian. We have
An - -
A
Vi,n (st,,, an,)) (Bhs (ha, as,a)) (Ii. - (aa+))((sn++))) + 20
k-1
A
-11
Asri + AA -0-
k.
(29)
18

---

Published as a conference paper at ICLR 2024
Then, write
00 All
Am
+ AllonIla
Σ
Am
vd,
(30)
where first incquality is due Eq. 29
and triangle inequality, and the second one comes from
AR, 2 AL.
By Lemma 17 (Theorem 2 in Abbasi-yadkori et al. (2011)) we have that with probability at least 1 8/H²,
00, - Ou,AllkaA < Hy ddddog H + KH4
VX
(31)
8
Thus, by uniform bound, we have the above inequality holds for any h e [H] with probability at least 1 8/H.
Combined with the concentration argument above, we can bound the deviation term of 0g and OR with respect to the CVaR operator.
Lemma 3. For (0, 1). any k [K] and any h e [H], we have that with probability at least
1 - H, the following holds:
| (Van))(s, - -Cgg (Vi,a)(ss, - (V
(32)
Proof. Apply the same definition of (V)]((s)) = x- - HPP(2 - - v)+ we can write [Cg. (V)](s, = sup (C (V)](s, a). We have
[CO.N (Vs,A+))((saa)) Ben
sup (V, veN.
sup Cog (V (VR,+ti)(ssaa) nEN.
(Ve.N(Ve.,+))(333. 1 Bn. (Ven+1)l(ssa)
sup n,
(33)
(On, V +e) (s, y a
( V (en)
sup yeN.
y
0p. Onliaan sup (&) 1 Pa (8, a a)
veN.
where the first inequality holds by the property of supremum, and the second inequality holds by triangle inequality. Recall the definition of Xx, (s, a) and v'k, in Eq. 26 and 27 By Lemma 2 we have that with probability at least 1 1- H/H,,
[CogNN (PR,4)))((saa) - (CC.V.(PP.attn (V a)) & - Alan a) 1))
(34)
D.3 OPTIMISM
We use upper confidence bound-base based value iteration as in Jin et al. (2020); Zhou et al. (2021a) to calculate the optimistic value and Q-value functions Vi.h. QR.k. and construct the policy म² in greedy manner. Then, we prove the optimism of Ve, below.
Lemma 4 (Optimism). For 8 (0, 1], E S, and any ls e [K]. [H], with probability at least 1 8- 6, we have
Vi((s)) Vx* (s).
(35)
19

---

Published as a conference paper at ICLR 2024
Proof. We prove this argument by induction in h. For h H+1, we have VI,H+1(s) V H+1 (s)
O for any k [K] and 8 S. For h [H]. assume that with probability at least (H h H,
Ve,b+i (s) > 1 (s) for any [K] and S. Consider the case of h. For any [K] and (8,a) 8 x A, we have that with probability at least 6/H.
QuA(s, ax,
3
= (CaNNi(PR, + 28 + sup 14 ((0 a aeN.
(8, - -CCg, (V++1)((s,
3 28
[Ca, -LCavN (C2, (VK,
a
+ (C (V3,))))(s..))) -C,,, (F (V,, +Ca, (p 1))((s [Ca, (s,,)
>CC8, >1C8, (Ven+)))))) [Ca, (V/+1)](s
(36)
where the inequality comes from Lemma 1 and Lemma which show that
IC (Ve,At))))) - [C%, - (Ve,+)))(ss > -2
(37)
and
3 -1lvzu(s, a),a))
(38)
Since (s,) (s") for any s' E S and ls [K] with probability at least 1- h
Then by union bound, we have Q a) >> Q7 a) holds for any k [K] and (s,a) S x A with probability at least (H + h)6/H. H. Take the supremum on the left and right side for A. we have (s) 3 (s) for any & E [K] and E S with high probability. This implies the case of By induction, we finish the proof.
D.4 REGRET SUMMATION
In this section, we provide the proof of the main theorem. Here we follow the definitions Du al. 2023
For fixed risk level a e (0, 1]. value function V S R. and a transition distribution P(- 8, a, e A(S), we denote the conditional probability of transitioning to s' from (s, a) conditioning on transitioning the a-portion tail states s' as QF (s' 8, 8,a). Q s,a) is distorted transition distribution of based on the lowest a-portion values of is'),..e.
CVaR
=
V (s' (s)))
(39)
S'ES
Moreover, let [Q a= = Eves Q V (s' s, sss) for real valued function f: - R.
Then, we consider the visitation prohability of the trajectories. Let (T*) K =k=1 be the polices produced by ICVaR-L in the Let Wk, a) denote the probability of visiting (s, a) step h of episode k; i.e.
the probability of visiting (s, a) under the transition probability of the MDP P. | 1..)) with policy
x. at step 1, hh- 1, starting with state sk,1 initially. Similarly,
Wiah CValt,a,
denote the conditional probability of visiting (s, a) step h of episode & conditioning on the
co,1 (- ..)) and policy Tे step 1,2,..., 1.
distorted transition probability Op,
Equipped with these notations, now we present our proof of the main theorem for ICVaR- -LR with linear function approximation.
20

---

Published as a conference paper at ICLR 2024
Proof of Theorem 7 First perform the regret decomposition. The following holds with proba-
bility at least
(o,1(o - 1/= (SK.1)
[Ca.. (Vk,2)](8k,,, (k.1) + 25 (8k,1 [Că, (V2" (8
( (V1,2))(8kk,,, - (V
1
[C (Vx,2)](5H.1 ax.1) [C0, (V
(40)
12
[Cg (V2.))(5R,1, 1Cg, (V22 (V
][(8,, ax,1) +2s + (8.,1
<2(2E (x,1 (x,1)) + [0 (Vx.2 - V/r (sk,,1,, ax,1)
where the incquality holds by applying Lemma recursively apply the same method of Eq. to k.h V for 2.3. .,, have that with probability at least 1 - 5,
and 20 to bound 41, 12, and 13 respectively. By
(e, V/= (SK,1)
<2(25 + Bx.(skk1
Σ oF
(s.)sn,. (V V/" (s2))
$2ES
H
2
Σ
CVall, w
(s,a)(2E (s,,(s,a))
(41)
4=1 (s,a)ESxA
4He
2 H +
CVall,a (s,a)bx,((s,))
< 1-
Wkh
h=1 (s,a)eSxA
where we denote (s, a) = (8, = aB a)/B. then (s, a) & H. The first inequality is exactly Eq. [40] the second inequality holds by recursively apply the same method of 40 to VR - V. for
CVaR,o, (s, a) & 3. ... H, and the last inequality holds by Wk.h (TT by Lemma 21 Then, we have that with probability least 1 1-8. 5,
K
Regret(K) =
Σ
Vi*
(Sk.1)
VIT" (s1)
k-1
4HKg
23
K
H
CVaR.o Wkb
(s,4)bx,
(42)
H-1
k- mllll
(
We can bound term / by similar approach in Du al. (023). By Cauchy inequality, we have
K
H
K
H
1
Wghh
CVaR,a
(s,a)
WKA
CValt
(8,a)
Aml
hm
(a.
(s.4)ESXA
K
H
Σ
Σ
VV
(s, (s,
WKA
k=
(x.0)eSxA
(43)
21

---

Published as a conference paper at ICLR 2024
CVR,,, Vot
where the equality holds due to [ss,a) have
Wki
(s,a)
by definition. By Lemma 21
H
Σ
CVa
(s.0)0R,(s,a)
wkah
(8,a)ESxA
Σ (8,a)E8xA
(44)
H-1
K
H Σ
a H-
(nh
b (sh, an)
where d=", denotes the distribution of (s, a) pair playing the MDP with initial state sk and policy T.. Let Gk = FR.H, where FR.H is defined in Appendix A We have x is Gk-1 measurable. Set Th hh-1 67, (SK, an,A), we have [2p]2 113, and Tk is Ga measurable. According to 19 we have the following holds with probability 5.
Lemma
K
" Σ
K
H
4 1ogg2
K + 8
Σ
E ) Ah.3
(sh, an)
(sk. + 4H log
(45)
Notice that we can apply the elliptical potential lemma (Lemma 18 to the first term on the right hand side. Thus we can bound term / in Eq. 42 with high probability. Combine the arguments above, we have that with probability at least 1
20,
Regret (K) &
4HKe H-1
+
23 a
Σ
K H
CVaR.a Wheh
(s, (5,,
k=
(s.))ESxA
4HKe
2
K Σ
E (shnaa)aat
Σ h-1
U2 (sh,
VKH
H-1
4HKe
23
K
4log, K + 8
R.h (8k,b. 0k,h) + 3 log
v
KH
Va*+11
8
k=1h=1
4dHVK
2
4 loog K +
8dH log (K) 4H4 log
VKH
Va
Va
(46)
where the first inequality is due Eq. 42 and Eq. 43 the second inequality is due Eq. 44 the
third inequality holds by Eq. 45 and the last inequality holds by d.H / /a and elliptical
potential lemma (Lemma 18
E SPACE AND COMPUTATION COMPLEXITIES OF ALGORITTMM I
In this section, we discuss the space and computation complexities of Algorithm We consider the setting of ICVaR-RL with linear function approximation, where the size of S can be extremely large and even infinite. We will show that the space and computation complexities of Algorithm are only polynomial in d, H,, K and [A]. Noticing that dill/aa H-3/K is given by Theorem I have |Nal |H/s] & v KK/(2=-3(²) + is also polynomial in d, H, K. We will include the size of N₂ into the complexities of Algorithm
E SPACE COMPLEXITY
Though in episode E [K]. we calculate the optimistic Q-value function Q1 (s, a) for every (s, a)-pair in Line of Algorithm only need to calculate the Q-value and value functions
22

---

Published as a conference paper at ICLR 2024
for the observed states {SK,A)K-1 to produce the exploration policies { in episode k, and calculate the estimator 1, for any h E [H] in episode Thus we need to store the covariance matrix Ag.h. regression features (oa--u (Sk,h, a) for any z E NN, A and value (I Ve,b+1) (sk,b+1). The total space complexity is O( H (NaIAA)HK).
E.2 COMPUTATION COMPLEXITY
By the above argument, we only need to calculate the optimistic value and Q-value functions for the observed states { in episode k. We show that the total complexity is by analyzing the specific steps of Algorithm 1 in two parts.
E.2.1 CALCULATION OF THE OPTIMISTIC VALUE AND Q-VALE FUNCTIONS
We discuss the complexities calculating optimistic value iteration steps (Lines in this section.
First, we need calculate Q a) for every action a A produce the exploration pol- icy (sx,t) at step h in episode k. In Line 6 calculating the approximated CVaR operator [Cg.t Ve,n+al(3sa)) = suPxeN, {x - 2 (0, h: 1 (s- (8, a)} costs Odd[Wg)) operations. Cal- culating (a Pa.-I)+ (s.a) costs O(KH) operations since the number of non-zero elements of (R,A+1() (:) is at most K H. Computing the bonus term BR,N(8, a) needs O(d operations. Thus, calculating (sk,A. a) for any E [H] needs O(d]WWEllA) K) operations.
Since we have D a), we can calculate (5,.() by O(IA)) operations in Line and (5R.A.) by A() operations Line 8 In all, computing the optimistic functions will cost WEllWAl K2) operations.
E.2.2 CALCULATION OF THE PARAMETER ESTIMATORS
At step h of episode k; choose the specific value Fk,4 in Line 12 which needs ((P) operations. Then, Line 13 takes ((f)) operations to calculate the covariance matrix A In (si,h, (r,)) + and
Line 14 we can store the prefix sum > calculate 02+ with (dP) operations. Thus the total complexity for calculating the parameter estimators is ((K).
F REGRET LOWER BOUND FOR ICVAR-RL WITH LINEAR FUNCTION APPROXIMATION
In this section, we present the brief introduction to the idea of the lower bound instance and the complete proof of Theorem 4 The formal theorem for regret lower bound in ICVaR-RL with linear function approximation presented below.
Theorem 4, Let H > 2, d 3 2, and an interger n E [H - 1]. Then, for any algorithmm, there exists such that the expected regret lower bounded
an instance of Iterated CVaR RL under Assumption as follows:
!
K a
E[Regrot(K)] > Ω d(H n)
(47)
First we briefly explain the the key idea of constructing the hard instance. Consider the action space A {-1,1)d-1 and a parameter set U [-A,A)d-) where A is small constant. The instance contains n + states with n regular states s ... Sn, and three absorbing states #1 Ø2, Z3- Moreover, uniformly choose vector from 2. Set 0, (1, μr ) for any h [H]. Then, can generate the transition probabilities and reward function shown in Figure by properly define the feature mapping.
Intuitively, the structure of the instance in Firgure is combined with a chain of regular states 81 82 8n and hard-to-learn bandit state 8n (122 (inspired by the construction
23

---

Published as a conference paper at ICLR 2024
Reward 0.8
1 a (d 1) + (ju, ap)
a
81
Sn-
Take Action an
1
1 a
(d 1)4
Reward 0.2
Reward
Figure 4: A hard-to-learn instance for Theorem
2023) With probability of a, the agent can move from to 8;41 for i e [n- 1J. Since we consider the worst-a-portion case under the Iterated CVaR criterion, the CVaR-type value function of only depends on the state 8 for i [n 1J. At state 8n, there is linear-type hard-to-leant bandit (inspired by the construction for the lower bound instance of linear bandits (Lattimore & Szepesvári 2020)). By construction, the absorbing state æ2 is better than 23- Hence, the best policy at s, 1s a sg == (sgn(H)), ,sg((ua1)) needs to learn the positive and negative signs of every element of μ by reaching 8n and pull the bandit.
for tabular MDP in Du et al.
As a result, the agent
Proof of Theorem We define the hard-to-learn instance (shown in Figure 4). which is inspired by the lower-bound instances constructed in Du et al. (2023); Zhou et al. (2021a): Lattimore & Szepesvári (2020). For given integers H, K, n E [ I| and risk level a E (0. 1]. consider the action space as A = (-11 1) and a parameter set L4 = (-A, A]d-1 where A is a constant to be determined. The instance contains r + 3 states with n regular states 81, 8n and three absorbing states 21, 22, F3g. Moreover, we uniformly choose y from U.
Then, we introduce the reward function of this instance. For any step [H]. the reward function (n a) ( for any regular state s; with i E [m]] and action A. The reward functions of absorbing states are (x( = rx(2, a) = 0.8, and (n(33, a) = 0.2 for any step h e [H] and action A.
For the transition kernels, set 02 = (1, 14 for any h [H]. For any i E [n 1] and action a E A. let o(8 S,, a) (a, ... probabilities at regular state 8, are (s a) = a and (z 8,, a) = -- a since we will only reach 8; at step h i. For any action On A, let (xx2, Sn, (n)
and 0(11, s, = (1 a, 0,
_0) Then the transition
=1 (1-a+ a (d- 1)4, ( aT)TT 6(x3, 8n, an) (a- (d- a.) ) Then, we have (P,(22 88: an)
and
= 1 ()-1) (j,, an)
and (I Sn, ax)
(d I)A (H,an) an) for any h [H]. For the absorbing states x; with
[1, 2, 3). let o(I; a) = (1, 0. ... 0) and Φ(s, I, a) ffr s z4. Thus PA Iz, a)
for (1,2,3) 3) and any E h [H].
In this instance, we have
-- (0.2(a 2(d 0.8(2(d 1)4))
V (s)
(48)
a
(T( n (0.2(a- (d 1)4 (H, + 0.8((d 1)4 NT ((,,
(49)
Thus we have
1.( A)A d-1
V. (s1) (s1)
I(H, (s)))
(50)
24

---

Published as a conference paper at ICLR 2024
where [p, ())), (s)g((4) sgn(Tz((n)))). Then if Algorithm produces policy (s Re[K]] in K episodes, we have
RKg) 1.2(H 1JA d-1
I(, (5))))
(51)
Since we uniformly choose μ from U. we have
[[Regret(K]]= 1.2(H n)
(
1--11
I( (1, I(.
Ep
(52)
2
Denote En be the conditional expectation on the fixed μ U. For fixed [d - 1]. we denote u(i) == (M1,'.. 14-1, M4s Mi+1, (d-1) which differs from at its i-th coordinate.
Assume N(, 12. 14 in Lattimore & Szepesvári (2020)) we have the following lemma.
- (1 (1, (sn), By Pinsker's inequality (Exercise 14.4 and
Lemma 5, For fixed
[d 11. we have
K
(p T. (H.
22 V (LF())))M()))
(53)
where Py denotes the joint distribution over all possible reward sequences of length K under the MDP paraneterized by μ.
Denote u((i) :- (MI, 1, 1.+11 (4d-1) which differs from μ at its i-th coordinate.
Let (s.)) ) be the probability to reach 8n in each episode. By construction, we have w( = a-1
Denote Ber(p) as the Bernoulli distribution with parameter P. Let Ber, Ber(a (d 1)
(u, (sn)))) By definition of KL divergence, we have (L(Ber(a))] Ber(b)) 2(a b)2/
2p- p(1) (s,))
8A2
E [KL( [er < Ep
(54)
(,, + (d 1)
2(d - 1)
Let A V an-2x where is small constant such that 2(d 1)A a/2. Then, we have
KL(PA|PPM)) = Σ ((ss))E, [LL (Ber [er,())) < -
(55)
Combined with above equations, we can bound the expectation of the regret as:
1.2(H - n) 1
E Regrett K)]
E. [N x,
2d-1
a
HEll
==1
1.2(H A)
d-1
E [N म. 1)] + En TT;)]
a
2d
HELL
1.2(H - A)A
(56)
K (H,,((,TTT))) EE(O) [ (4, π, T1
a
2d
REl
1.2(H A)A
d-1
Σ Σ
K- K-2
2d
a
neld
0.6(1 - A)A
(d - 222K-K2KKKV
where the inequality holds by Lemma 5 and Eq. 55 Since A . an-2g- we have
K a
E [[Regret 2 Ω d(H d(H n)
(57)
25

---

Published as a conference paper at ICLR 2024
G ALGORITHM FOR ICVAR-RL WITH GENERAL FUNCTION APPROXIMATION: ICVAR-G
Overall, in each episode, the algorithm first calculates PR.A to estimate the transition kernel Ps. by least square problem in Line 11 and selects a confidence set Pk.k in Line 12 such that P,, is likely to belong to .R., with high probability (as detailed Lemma in Appendix H.2). Subsequently,
the algorithm calculates the optimistic value functions in Line 6 based on the selected set Pk.
and chooses the exploration policy n& using greedy approach Line 7
Algorithm ICVaR-G
Require: estimation radius 7.
0 for any is E [K]. 2: for episode k = 1,... K do
1: Initialize VR,H+
3: for step h = H -... do
4: // OOplimistic value iteration
5:
Qua((:))) =.((,))) supree., PCP (CP((4)))))))) V-,a(-) min { max Qn,((,
6:
7: (+) - arg max (.)))aa)
8:
end for
9:
for horizon h = 1,... ,., H do
Observe state Kk, h. play with policy The 0k (sk,))
11: PK+LA - arg min > Dist,, (TP', 6x // Estimate the transition kernel Ph. PEP
12: PA+IA - P' E a (F, & 53) // Construct the confidence set
end for
14: end for
H PROOF OF THEOREM 2 REGRET UPPER BOUND FOR ALGORITHM
In this section, we present the full proof of Theorem for ICVaR-RL. with general function approx- imation under Assumption 2 concentration argument which shows 1 PaLs with high probability in Lemma With the con-
The proof consists of parts. In Appendix H.2 establish the
centration argument, we can prove the optimism of QR.a and Vg, in Lemma and further bound the deviation term for general setting in Lemma potential lemma in Lemma 9 and prove Theorem 2 by regret decomposition and regret summation.
Appendix HH.]] we present our novel elliptical
H.1 DEFINITION OF ELUDER DIMENSION AND COVERING NUMBER
To introduce the eluder dimension, we first define the concept of e-independence.
Definition 1 (e-dependence Russo & Van Roy (013)). For ε > O and function class Z whose elements are with domain X, an element X e-dependent the X, {I fr1, 22, {nn C
X with respect to Z, if any pair of functions 2, z' E Z with v VE",, (z(x.) =xxx))² & s satisfies xxx) =2(x) & Otherwise, is e-independent on X, if it does not satisfy the condition.
Definition 2 (Eluder dimension Russo & Van Roy (2013). For any E O, and function class Z whose elements are in domain X, the Eluder dimenston dimp (Z,e) E) is defined as the length of the longest possible sequence of elements in X such that for some z E, every element e'- independent of its predecessors.
Next give the formal definition of the covering number. It is widely used definition (Ayoub) et al. 2020 Jin et al.) 2020 Fei et al. (021)..
Definition (Covering Number). For the function set F with norm || and given positive constatn e > 0. we can define the E-net of F as F. such that for any F. we have f E F. satisfying [ l'l & e. The e-covering number No(F.1 (1,8)) is the minimun size of the E-net of F.
26

---

Published as a conference paper at ICLR 2024
H.2 CONCENTRATION ARGUMENT
In this section, we apply the techniques firstly proposed by Russo & Van Roy (013) and also used in Ayoub al. (020): Fei al. (021) establish the concentration argument, which shows that PA is belong to our confidence set Pk.h with high probability.
Lemma 6. We have that for 8 (0, 11. with probability at least 1 - 6, Pr Pk.k holds for any kE [K] and he e [H].
Proof. Firstly we fix h [H]. By definition of Distr,a(;)) and the delta distribution òū we have
k-1
PR. = arg min Pepp
(IIAA -
- [I ((shh, (58)
and Pk.A {P' P. Ei=1 Dist (I,', PRIN)) & 522.. Let Xn. = (SK.h, ahah (FR,A V+
and Yx,h (Ii,h + Then, we have that Xg., FE, measurable and Yk, is
FR.++1 measurable. Note that (Yi,, - 2P, (Xx),, h is H-sub-gaut H-sub-gaussian conditioning on {FR, bk and
E E| 2P, (Xx,a) FE.A]=
Moreover, by definition of PA, and function class Z, we have
arg min Z
(Yi, - zp (Xi,a)))
(59)
Let (7, {{ bي 3: - (Xen) 2x. (Xin)) { By Lemma 22 for any
O, with probability at least 1 5/ H, for all k [K], we have 2P, Zz,,( Here
N 3el 8 H 8H² log(2H N 2, 1000 K H' K
H
18) + 4 k (H² + H² log(4k(k + 1)/8)).
(60)
where BR is defined by Eq. 121 in Lemma 22 and Nc
the covering num-
ber of Z with norm |- ll and covering radius H/K. Since pP, E (7,)(TH), we have Ph.
P'EP: EK11 (X,) =P,,, (x.)
& 7
Moreover, have
222 20r1100
sup Xx
Σ P(s' v()) Σ F'ss' (s)))((s)
SEES
SES
H
sup V).S
Σ PPs' s,a) - Σ I'(s' s.a)
(61)
8'ES
e'ES
sup <H
Σ
[Ps' 8,
P'(s' s,a)
s'eS
=HIP IP 1z
where the first inequality holds by V(s') E [0, H] for any s' S, the second inequality holds by the triangle inequality. and the third equality is due to the definition of nor 100.1- Thus we have Nc(2, læc, H/K) & NP., Ils., 1/K). Since
2H NN || 11..111 1/K)
G 2
2og
+ 1 vlog(5K3/6) > %k
(62)
we have IP, E PA.n h. for any E [K] with probability least 1- 88/H.
Finally, by union bound, we have P, E PR.n holds for any (k, h) E [K] x [H] with probability at least 1 5.
27

---

Published as a conference paper at ICLR 2024
With the concentration property in Lemma 6 can easily show the construction of Ve, and Qk optimistic in Algorithm
Lemma (Optimism). If the event in Lemmaphappens we have
(x,n(s) > (s), V
(63)
Proof. Since the event in Lemma 6 happens, we have Ph Pk.n holds for any A and h. Thus by the definition of Qua Algorithm
(x, = (, a) + sup [CPPR > (8, + [Cp, Vx
(64)
PEPLA
By similar argument of induction in Lemma we can easily get the result.
The following lemma upper bounds the deviation term by a)/a.
Lemma 8. If the event in Lemma 6
happens.
1 a
sup PeP
[CP (e - [C3, Vr.til(ss a) gg.n(s,a)
(65)
Proof. The left side holds trivially by the result of Lemma
We only need prove the right side.
sup [Cg Ve,A+1](s a) [Cp, (
P'EPE.
{a [Pn ((sat))((ssa))
inf [P Ve, P'P
sup xe[0,H]
I
sup xE[o,H]
sup
inf P'ePk.h
[P'( - +(A+t)+
[T 1 +1(s,a) +
==[0,H]
sup [P(2 ((,,,))+((s,00 inf [P(x - Vintt)) PEP
sup a ze [).H]
PEPPIA
(P(,)),(88) PRLtt) inf (P(()))((88))) (1,++1)
sup
a PEPLA
P'PPa.
a gk,,(s,o),
(66) where the first inequality holds by the property of supremum, and the second inequality holds by holds by Pa E Pk.s under the event happens in Lemma 6 and the rest equalities are due to the definition of (s,A(s, a) in Eq. and ga.h a) in Eq. 12
H.3 REGRET SUMMATION
In this section, we firstly propose refined elliptical potential lemma for ICVaR-RL. with general function approximation. Then, we apply the similar methods in the proof of linear setting to get the regret upper bound.
Noticing that Russo Van Roy (2014) presents a similar elliptical potential lemma (Lemma in Russo & Van Roy (2144) used in Ayoub al.) (2020); Fei et al. (2021) which shows that
.I1 2 Ik (Sk, a O / K) with respect to the term of K. Inspired by this version of elliptical potential lemma, our Lemma 9 is a refined version which gives sharper result.
Lemma (Elliptical potential lemma for general function approximation). We provide the elliptical potential lemma for general function approximation. We have
(sn, (..)) < H diimm(,,1///)) + 46 (2,
(67)
28

---

Published as a conference paper at ICLR 2024
Proof. Our proof is inspired by the proof framework of Lemma 5 in Russo & Van Roy 2014). First we recall the definition of Xk, X in the proof of Lemma l.. X == (SR,A, ag ( as.A) V)) For simplicity, let Gk,A
ga (k.bb) SuPPEPLA zp (K -inf---nfPee..... ze. (XE,)) Then for fixed h E [H]] we know ge.A I (Su,n, (g,b) & H since 0 & (Xx,,) & H for any probability kernel P E P. Then, we can reorder the sequence (GI,b)" . .k.)) - (G "..i,. Gix.)) such that Gz.hh b Gjaih 20 ......aaa... Gix.k. Then, we have
m
K
G RRA
Σ je k=1
Σ
Pi 1[G K K- +
Σ k=m+1
G. 1GG < K-1/2) (68)
1=1
for some m E [K]. Since the second term is less than 1 trivially, we only consider the first term. Then, fix 1 [mm] and let Gjenh and have
(69)
By Lemma 23
we have
K Σ
1(Gr, 8) & dimn(2,s) (1g
4 82
+1)
(70)
For simplicity, denote dz( == dimg (2, 1/2).
Since E [m]. we have Gjab
K-1/2, which implies dim (2, 8) dz(2). By Eq. 70 have Gj.hh &
V(15dg(Z)//( dz(Z)). Notice that this property holds for every fixed t [m]] Combined with Gk.h & H, we have
K
m Σ Gh
Σ
G
1 2 K-1/2)
K
42)
(71)
<1 + dg()) +
Σ
dx(2)
<1 d1+d)(Z)H1
K) + 1),
where the first incquality is due to Eq. 68 the second inequality holds by Gz.hh < ((45dr(2))/( dr((2) for any L E [m]] and GR.A & H, and the last inequality is due to the property of harmonic series. Sum over Eq. 71 for h [H]. we get the result.
Combined by this refied elliptical potential lemma, we can prove the main theorem of ICVaR-RL with general function approximation.
Proof of Theorem 2 This proof is similar to the proof of Theorem I with tiny adaption. Firstly, by standard regret decomposition method, we have that with probability at least 1 6, the event in Lemma 6 happens and
(5,1() VT (SK,1)
sup [Cp (Pk.2)))5)) [CP, (V2 [[RR,,
PEPe,
sup (Vk.)))(s6 [CP, (Vx,2)](sH,,, ax.1) MePa.
+ |Cg, (V (Vr,2) a1.1 [Cp, (V3"")((s,
De, (8k. ox.1)
10t
v.. (Vr.2 V (8 ax,1)
where the inequality holds by Lemma and Lemma 20 Here go is defined above in Fq Next we use the techniques of the proof in Section D.4 to bound the regret. Specifically, we have
(a.(5 VIT" (Sk.1)
1
CVaR,a, WgA
(s.a)gk.(ssaa)
(72)
h= (x.a)eSxA
29

---

Published as a conference paper at ICLR 2024
This implies that the regret of the algorithm satisfies
K
K V/ (sk,1) $
Regret K) =
(f((5),)
Σ
(5,11 - 1/ (sk,1)
(73)
K
aValla, (s,a)gan(ssa)
khh
(s.0)ESXA
aVaR.a, with probability at least 26. Here Whhh ity, we have
defined in Appendix D.4 By Cauchy inequal-
Regret K)
K
K (8, (8,4)gh,(ssa))
Wkhh
CVaRt,,
Wk.h
CVall,
(s,a)
1= h=1
(s.a)eSxA
11=1 (5.a)e5xA
K H
Σ
Σ
Σ
OVaR,o Whh
(3,0)).,,(3,4))3
(s.0)eSxA
(74)
where the equality holds due to _(s,a) have
W Wk
VVa
(s,a) 1 by definition. By Lemma 21 we
(K)
VKH
K
H
Wk.h
aVaR,a
(s,
(s,a)e5xA
V
KH
K
Σ
H
Σ
Wk.h (),
(75)
a H-11
(8,0)ESxA
KH
K
E
Σ Rhn an)
a H-1
(sh
where d= 56,1
denotes the distribution of (s, a) pair playing the MDP with initial state s and policy
R Since E (sk,,, ak,))
v H3, by Lemma 19 we have
H 1sh.as (adtt Σ
4 1ogg K 8 Fhin (sk,h (x.))
9h (sh, and
8
2
4H log
5
(76)
Apply Lemma to Dk_ D P. (s an,R), we can bound the regret with probability at least
1
KH
K H
4 log, K + 8
Regert(K) <
Th.n P (Sk,N, ok.).
4H3 log
1-1
4KH H-- V
1ogg K 2H + 2dg(2)H's 89d + +) H log
8
(77)
where dz(Z) dr 1/(221/VK), the first inequality holds by Eq. 75 76 and the second inequality
holds by Lemma
I PROOF OF THEOREM 3 REGRET UPPER BOUND FOR ALGORITHM
In this section, we present the proof of Theorem 3 First we give some notations used in this section.
We denote V (s))r) presents the value function for MDP with transition kernels (PPr) A and
h-1
30

---

Published as a conference paper at ICLR 2024
reward function Thus define x²* maxx VT (S11:=)) the regret be write as
Regret(K)
Σ V (sk,1i
VTTh (sk,1ir*))
(78)
Overall, we bound the reward estimation error in Appendix [.] and apply the regret decomposition method to bound the regret summation in Appendix
I.1 REWARD ESTIMATION ERROR
Definition 4 (Bracketing number, Geer 2000); Liu al. (023 ) Given a function set F. let I and r be two functions belonging to F. Suppose that & v. The interval [L. r] denotes the set of all functions f satisfying & Σ pointwisely. [t, is referred
e-bracket set the norm I|r py-1, -1] & according to a given norm || Then the minimum number of the 8-bracket sets needed cover F is defined the bracketing number NB(F, Il El, where || represents the chosen norm. And denote F (r r is member of the minimum e-brackets covering } as the E-bracketing covering of F.
In this section, we denote Rt/K as the KK-bbackkeing of R. with norm |- 1o and the bracketing number is (B(R, ll. 1/K). Then for every r R, there exists F such that F(r) r(r) and F(r) > r(T) for every 7 T.
Then we present the reward concentration in the following lemma.
Lemma 10. For 5 e (0, 1) and some constant
O, with probability at least have
T(o,, -(s) r(Tu)) clog(K -N((,, (ll, 1/K)/0).
log
(79)
Ölo, r*;)) r* (To))
kE
Proof. The proof of this lemma is inspired by Lemma D.1 in Wang al. (2023b) Notice that Wang ct al. 2023b) only deal with the setting when is a finite set, and in our problem the reward function might be infinite. We expand the proof infinite situations inspired by Liu al. (2023 2022) which present the MLE analysis to transition probabilities and including the discretization techniques such as e-bracketing number in partially observed MDPs (POMDPs).
First we denote " the distribution of trajectory when the agent starts with the initial state sk,1 and executes the policy The And we use T to represent the set of all possible trajectories. For every R1/K. we have
G(o, F(T.) - F(TO))
E (d i=1, &
exp
log
F(oir r (Ti) r3 (T))
k-1
F(or F(T,) F(Tu))
= =E (T.
exp
log
F(o;, r (2)))))()))0))))))))))))())) (T)))))
o(or, (Tx)) - F(TO))
(80)
F(or, x (Tx) - r (T))))
k-1
F(T,) F(Tu))
exp
log
F(o; r (+(()))))))))))))))) r (T))
o(0, F(T) - 7 F(TO))
Σ
P mu [
7(o, r
p. (T))
TeT
31

---

Published as a conference paper at ICLR 2024
where P denotes the probability of generating trajectory by executing the policy If we fix some T T, we have
o(o, T(T) T(TO)) 8(o,r"(T) - r" (To)) |7] 1
Eg
=o(r"(1 r" (To)) 8(1, F(Tu))
(1 (1-oor"(rr) -r) (7)))) ((0,
F(TO))
((),, r (TO))
7 5(0.
r (TO))
((r (T("(()- (To)) + ((r*(r) (+o0)) ( a(r(ro) r(())
d(r(r) r((o))
=o(r*(1) (r) r (To))
r*
((o r* (T))
-o(r(r) -
- =1
(81)
where the first equality comes from the orcale of human feedback defined in Assumption the second equality comes from the definition of ō in Eq. 14 and the third and forth equalities are due the completeness of link function Assumption
Thus have
- ((o., F(70)) ((re)))) r((,,,*(TT)) - y** (TO))
)
B (
exp
Σ log
1.
(82)
Thus, by Markov's inequality, have
5(or, ((m)) r(m)
r(TO))
log
Ho H(o (T:) - r" (TTo)) > log(1/8) & ò.
(83)
Taking union bound for all r R1/K and k [K]. for some constant >> 0, we have
A
Ho, ((,) r(To))
max Σ log
Ho,, r (Ti) r (To)) > clog(NV(RR.1) |l,, 1/K) < 6. (84)
PERI,K [K[
Since have for every R. there exists RI/K, r(r) & F(T) and r(r) r(r) 1/K for every 1/K, we have
((r) f(,,, r* (To))
5(o, r - r(To))
Vi [K]
(85)
olo r* [T)) r (T()
Then we have
h Σ
((o.,)(T)) rTTo)) Ö(o,, r* (Tol)
k
5(o; r(T;) - r((T))) ((o - r+()))))
max PERTAK
log
max HER
log
(86)
which implies
Ö(o,, r(T))())))))))) r(TO))
max KE
Σ log
H(o, r (T:) - r (To))
clog(NB((R.)) 1l. 1/K) E
(87)
This inequality instantly gives the result.
p Lemma 11. For 3R clog(KN, (R, II x E Rr for every l E [K] holds with probability at least 1 - 8.
1 1/K)/5) and positive constant 5 (0, 1], we have
Proof. Recall the definition R. and log likelihood function Lx(r). By lemma 10 conditional on event ERt, have the following holds for every le [K]
max
log
F(or r* (Tt) - ~r* -T"))))))
G(or, r(T)) r((T)))
-
max LL(T) LL(r*) 8n
(88)
PER
PER
Then have 8 R..
32

---

Published as a conference paper at ICLR 2024
Lemma 12. For constant 8'E (0, 1]. we have the following inequality holds with probablity at least 1 - 6 for every E [K]
Σ (T)) - r", (T.) < (4 123m)/m 1,
(89)
where m is the positive lower bound of the gradient of link function a.
Proof. The proof of this lemma is inspired by the proof of Proposition 14 in Liu al. (2022) which develops the analytic tools for transition probabilities' MLE in POMDPs. In our works, we develop the techniques for reward MLE.
By Lemma 15 in Liu et al. 2022) and the inquality log 3 - we have with probability at least 1- 5, the following inequality holds for every F RI/K.
o(o (T)) o (T+))
R-1
a(o, F (T)) a r (Ti))
1 - E.
log
logg(NB(R.) 1llo, 1/K)/6).
i-1
(90)
By algebra, we have
(T.. ((,r))((.))
Σ
E,
(o(T ((r (Tt)) 2
(91)
Recall regularity assumption of link function o, we have (xx) > m >
Thus we have
(T.(TT) -r (Tr) Em Σ (o( -r(
(92)
<m (4 + 43R 8 llog (ogg 1/K)/8)
<(4 + 12.3R)/m.
Moreover, for every gk, there exists a R1/K such that F(T) r(r) 1/K for every T L/K. Thus we have
ph (T)
r: (T)) & (4+ 128n)/m +
(93)
This implies the conclusion.
Inspired by the study of the relation between eluder dimension and sample complexity in Russo & Van Roy (2013). we derive the following lemma which is similar Proposition Russo & Van Roy (2033).
Lemma 13. For all ls [K] and > we have
(4 123R)/ m +
> 1 ( (T:) - + (Tt) e) <
+ dim (R, c).
(94)
2
Proof. This proof inspired by the proof of Proposition in Russo & Van Roy (2013). We denote wi == Fi, (T) r = (T). If w. for some fix t E [k]] then we have fl (Tz) T (Tr c-dependent on subsequence (Ti Tt,) of (TI, TT-1), then have
> e. If Te is
Σ (T.)
2
(95)
Therefore, if is c-dependent L disjoint subsequences of (71, TT-1), we have
Le
Σ (ot (T.) r (T:))2 & (4+ 123r)/ 1.
(96)
Then we know that L (4+128g)m+1 Denote d = dim R2 e). We want to prove the following claim:
33

---

Published as a conference paper at ICLR 2024
Claim For any E [K], there is some Ty in sequence (Ti.-.. 7t) that is e-dependent least t/d- disjoint subsequences of (TI, 11 T/-1).
For an integer L with Ld A2, .g. First let A; = (T.). = 1. L. If TL+1 e-dependent on A.. Ar. we have done. Otherwise select subsequence A, such that 7L+1 is c-independent with respect to A;- Then add T into A,. Repeat this process for Ty with j > L + until is c-dependent on each subsequence or
& t & Ld + d, we will construct L disjoint subsequences
Ty is e-dependent A,. .A. then we get the result. ] 1 Ld+1, 1, then Σ |4,] = - > Ld. Since every element in A, is c-independent of its predecessors by construction, have |A,] & for every E [I]] by the definition of eluder dimension. Thus |A,] = for i [4]. Thus Tr cannot be e-independent with respect to any A; by the definition of eluder dimension. Then we have Tr must be e-dependent on each subsequence, which proves our claim.
Then each Ta, is e-dependent on L, disjoint subsequences of (T1,' ,Ts,-1). By above argument, we know LJ < (33 Equip with the claim above, there exist a e [t] such that T; is c-dependent on at least 1/d 1 disjoint subsequences of (Ta,." -Tt--)) This shows that 1/d - < O(Bn/e²) Then we have
Take
subsequence consisting of elements Tú satisfying why
t 1w; > c) ( 123x)/ mmmmm+111 +1
(4+
+ 1)d,
(97)
2²
which implies the result.
Lemma 14. For 5 (0, the error of the reward estimation can be bounded follows with probability at least 8.
(rt (T*) roo (++))) < dr)))() + dx( 123m2)/mmmmmmmmmmm 1)(log(K)+
+1 (98)
Proof. This proof is very similar to the proof of Lemma
Let wh == مb (Tx) r (Tx) and
dg(R) = dimm R/) Then we need to bound _ w First we can reorder the sequence
(wi,".. wx) (Wi,, "" wix) such that Wi, 30 W11 3 3 wix. Then we have
Σ w Σ w 1(wrr K K-1/2) + k=1
w 1( < K 1/2)
(99)
k=
where L E [K] satisfying that ws, > K-1/2 K-1/2,
W
Fix some t [L] and denote w Wi,
1/2, we have
1 (wi, 3 1) 3 t.
(100)
By Lemma
13
we have
t & dim g (R, 3) ()(( + 12,3n / + 1)/0² + +1.
(101)
Since w >> K 1-2, we have dim R, T) < dimg 1/v dg(R). Moreover, with Eq. 101
we have
de) 123n)/m 1)/(t de(R))
(102)
Since t E [L] is chosen arbitrary, we have w,, & v ()) +123n) m 1)/(t (R) for every e [L]. By definition, Wi & H for every l E [K]. Therefore,
K
: 11
+1
de (4 +12+1)22)////) t- (-dx(R)
m/m /m 1)
(103)
<1 + dg 22)
de (R)+1
<1
(2) ((4+ 123m)/m + ()(log(K) + 1).
34

---

Published as a conference paper at ICLR 2024
J REGRET SUMMATION
Lemma 15. With probability at least 1 28 for given constant & E (0, 1]. we have (kn(Ska) 30
VT" (sk,1; ( every k [K] and h [H].
Proof. By the chosen of selected estimated reward p*, we have
VE,1 (SN,1)
max V. (8 r,
(104)
Since we have P/ E PR. with probability at least 1 - by Lemma and r+ E RR with probability least 1 by Lemma 11 have
v (P
(SE,1;
& max
1/ V/ (sk.1i)))T))) = (s,.
(105)
reR,
where the second equality is due to the definition of V
Eq.
13
Lemma 16. Given a positive constant 8 E (0, 1]. With probability at least 6, we have the following inequality holds for every ls [K].
V (kk.)) ViTh (sk.
CVaR,a, (sr (sh: an)
WkAh
(106)
h=1 (ESAA
((A(9)) an) - (S0.h, - (sh an) (so.h, (s........ + gh.h(shaa))
1
Proof. By similar regret decomposition method in the proof of Theorem in Appendix H.3
(E.1( V7 (sk,1;
= (P ax.1) - (s0.1, (0,1)) (rf (k.1) ( 0o,1))
(Pa2) (sk,1, CD C. (V2T (s';
+ sup PEPA,
(P((O).) - (80, (o.1)) - (r9(s.., (80,1, 10.1)
C7 (v.2) (sk,1, (x.1) CP. (Pk22) (sk.1,
(107)
+ sup
FEPAI
CD C. (Vx,2(5))) CD () (V.''('' (s
< <(f((s,,, (30, (0.1) (ri 0k,1) r .o.1)
,.13" (:rt))
9k.1 (sk,1, ak.1)
Pe (V22(52) V (s2: )))
where the inequality due to Lemma 20
Let 51 := sk,1, we can write
(1. 1i (sH.1iT < (Fh ax. Pt (30,1,
(sk,1, ax.1) ri (50.1, ag.1)
", (srit)
+ [k.,(Sk,11, (x.1) + Q Pi (Vx.((s)) 1/5" (s2:r*))
(108)
CValta, (sT (sh;
Σ
Wkah
h=1 (Ex.
(AA((sh) ah) - (Su ao.1)) (rh an) r (o..)) + ggalsnhaa)) on)
35

---

Published as a conference paper at ICLR 2024
Combine with above lemmas, are ready to prove Theorem
Proof of Theorem
By Lemma
15
we have with probability at least - 6,
Regret(K) (K)
Σ V (8z,1ir") - 1iTT (82,1i))))
Vs (SR,1iT*) - (TO) + r (To) V1 (sx,1in*)
(109)
Vi (sK.1:IT)) (sk,1
K Σ
[(,n(()21)) Vinn (sk.1;r+t)
where the second equality is due to (To( is fixed. Denote (s,, ax) = (sh, an)
Pi (So.h, do,4) (sh, an) - rx (80.ts au,h)). Consider the regret decomposition for every episode
k, by Lemma 16
we have
Regret(K)
K
H
CVaR, Vo (srig)
Σ
(sh, ap)
JESKA
1 gnhh(sn,
(Ph an) (50, ao,i)) (5% an) - r%. (50, ao,))) a
K
H
CVaR (::0 an (sh,
(110)
WkA
(4% (9h,0nJeSxA
K
H
CVaR, (trfu) (sh, Au an)
Σ
Wk,b
(SK.ah
Bounding the first term / almost same the proof of Theorem bounding J. Therefore, by Cauchy-Schward inequality, we have
which also gives insight into
CVaR, V (:0 (s, (s,
1
Σ
Wx.b
k= 1 -=
(s.a)aSxA
Σ
Σ
Σ
VVaR,a,ee (:500) (s,a)
Wkh
h=
(s,a)eSxA
(1II)
Σ
Σ
aVaR,a, (:r
(s.
Wkh
1=
(s,a)ESxA
JKH
K
nh (Sh, and
a
H-
E
(n
where d sk,
denotes the distribution of (s, a) pair playing the MDP with initial state sk, and policy
T Since v Em (sk.h, & H3H. by Lemma 19 we have with probability at least - 6,
H3,
K
H Σ
K H
4 4log2 K
Sh and &
gen (8k,n, (k.)) + 4H3 log
(an (mdtt
5
(112)
36

---

Published as a conference paper at ICLR 2024
Apply Lemma 9
we have with probability at least 28,
4 4log K a+ll 2H + (5d))) 1) Ha log
4KH
I E
8
(113)
=ō (7 (2) I ll,,,,,/KK))
Bounding the second term shares almost the same techniques as bounding probability at least 1 d,
Thus we have with
1 J
a (1n
- a
Wk.h
2.,
h- h- (e.0)e5xA
Σ
(1r7o) (s.a)
WKA
A= h= (e,0)ESxA
1
Va
WkAh
(s,
a
A=
(s0))SXA
(114)
KH
K
H A (sh: un)
a
a H
(en doth
КK
K
H
④ H
E
ash )adk
Σ
Au.n an)
VKH
K
ckk (T) r (T))²
H1
a
Notice that by Lemma
19 we have with probability at least - 8,
4 logz K 8 r (T)) 411² log
To (T)
[T)
F (T)
An wark
(115)
Since we have bounded the reward estimation error Lemma 13 we can bound J by
KH
4/12log log 4log, K + 8
4/2
+8 8dg)) + ((4+ 123x)/m 1)(lo(( K) + 1))
at++l
(o log( 1loo 1/k3)/K))mm
(116)
where the inequality holds with probability at least - 25
Finally, by Eq. 113 and Eq. 116 we can derive the regret bound for Algorithm 2 with probability at least 1 - 46.
Regret(K) & δ VKHlt--H-I, (HVdd(()) 1-lo,, 1/K) 11,,
(117)
+ (m-idg(R)) (oogNo((gBB) NB 10: 1/K))
K AUXILIARY LEMMAS
In this section, we present several auxiliary lemmas used in this paper.
37

---

Published as a conference paper at ICLR 2024
Lemma 17 (Hoeffding-type Self-normalinn Bound, Theorem 2 in Abbasi-yadken al. 2011 Let (Fii_o be a filtratio.. Let {n be a real-valued stochastic process such that nn is Ft- measurable and nt is conditionally R-sub-Gaussian for some R O. Let {Xa]== be a valued stochastic process such that Xt is measuraae. Assume that V is d x d positive definite matrix. For any t E O, define
V
Σ X S.= Σ neXs:
Then for any with probability least 1- 8, all 0, [et (det(V.))PPet((()22
|| & 2R log
Lemma 18 (Elliptical Potential Lemma, Lemma 11 in Abbasi-yadkori et al. (011)). For À > 0, sequence {Xo]2_ < R., and Vi = Al + E.= X.X,, assume Xella & L for all t. If X > max(1, we have that
det(Vn) & 2d log dd
d TL2
K & 2lg
(118)
A
Lemma 19 (Lemma Zhang et al. of random variables such that X we have
(021 I). Let {Fi)sao be a filtration. Let (X:)==1 be a sequence almost surely, that X; is F, measurable. For every 8 E (0, 1),
4 _
1
Σ
BLX? & Σ 8x? 4log
< (llog, n 2)6.
(119)
Lemma 20 (Lemma 11 in Du et al. 2023 ). For any (s,a) E S A, distribution p(: ss,)) E As. and functions V, V S [0, H such that (s') = V(5') for any s' S.
( (V(')) o (V(s') & & (: (.1 s, a) T( -V-
Lemma 21 (Lemma 9 in Du et al. ). For any functions Vi, VH E S - R, 0, h [M]
and (s, a) E 8 x A such that wk (8, a)
O.
CVaR.a.V A.A
(s,
(120)
Wh.n (s.
h-
CVV....V (s, a) denotes the conditional probability of visiting (8,a) at step h of episode where wk.h
k. conditioning on transitioning to the worst a--prrtonn successor states (i.e. with the lowest a-portion values Vw+1(5') each step h' 1,... .h -h-1. 1.
Lemma 22 (Theorem in Ayoub et al. (0220). Let (Xp. Yp)p=12.... be a sequence of random elements, Xp E X for some measurable set X and Y, E R. Let F be a set of real-valued mea- surable function with domain X. Let F = (F (F.)......... be a filtration such that for all p 3 1, (X1, Yi,Y,.... _xp-1, p- X,) is Fp-1 measurable and such that there exists some function f E F such that E[y, [P-11 (xp)) holds for all p 3 1. Let ft = arg min [p=1(f(X,) - Y2) Les No be the -covering number of F at scale a. For 3 > O, define F((B) = (ʃ F 8).
-
If the functions in F are bounded by the positive constant C > O. Assume that for each s > 1,
(Y, (x(X))) is conditionally a a-sub subb-aaussian given IF F Then for any a > O with probability
1 - 8, for all 2 1, fx F,(Ba(6, ai), where
8,(5. a)) = 80² log (2Na/ + 4ta(C + oo (ot(ggttttttoooo + 1)/5)).
(121)
Lemma 23 (Proposition 8 in Russo Van Roy (0144)) Consider the function class Z, P. and Pa.k. Z,P
defined in Section 5 For fixed h E [H]. let W/ (xx) suPtePr,n 2x( (x())) inf Per 2p Xx), then
44 ( + +1) dim (2, lx,
[(wx(As) > +)
(122)
for all k [K] and 0.
38


Reviews:
[{"review_id": "P2RZqub7ig", "reviewer": "Reviewer_wJB8", "summary": "This work focuses on risk-sensitive reinforcement learning for large state space. It propses three variants of Iterated Conditional Value-at-Risk (CVaR) algorithms for linear function approximation, general function approximation, and with human feedback respectively. Moreover, it provides theoretical analysis on the regret bound for each of the algorithms.", "questions": "See the weaknesses section.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "To the best of my knowledge, this paper is distinctive in its provision of the first theoretical analysis on regret bounds for ICVaR-RL algorithms in non-tabular settings. It sets a precedent which could lead to significant advancements in this field. Additionally, the introduction of human feedback into risk-sensitive RL opens a potentially fruitful avenue for future research.", "weaknesses": "1. The presentation can be further enhanced in terms of clarity and logic:\n\n   - In the first paragraph on page 2, the paper introduces two proposed algorithms but fails to sufficiently detail how these tools embody and implement the ICVaR concept. This lack of substance makes the uniqueness and contribution of your algorithms unclear.\n\n   - The main argument presented in the second paragraph on page 2 is confusing. It's unclear whether the intention is to highlight the importance of integrating human feedback, with LLM as a successful example of this, or to underline the significance of risk-sensitive RL, with ChatGPT as an example. Additionally, why is \" LLMs operate in diverse conversational landscapes, where defining reward signals unequivocally is challenging\" relevant here?\n\n   - The third paragraph on page 2 attempts to give an outline of the key challenges in theoretical analysis for ICVaR algorithms with function approximation and human feedback. However, critical concepts and symbols which outline these challenges are not adequately defined or explained, which hinders the comprehension of arguments. For instance, without further context or clarification, the term \"key elliptical potential lemma\" remains obscure to readers. Moreover, the majority of the \"challenges\" outlined are essentially highlighting that current proof techniques and results cannot be seamlessly applied to your problem setting. However, there's a lack of explanation rooted in the problem's inherent characteristics.\n\n2. Limited discussion on the intuition and implications of their theoretical bounds, making it difficult to understand the relevance and significance of these results.\n\n3. Absence of algorithm implementation or experimental results limits the understanding of the theoretical results' real world impact and applicability. Practical validation through experimentation is essential to underline the significance and verify the efficiency of the proposed algorithms, which has been neglected in this paper.", "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": "", "extra_scores": {}}, {"review_id": "XlSkvvMZdz", "reviewer": "Reviewer_CSXT", "summary": "This paper considers the risk-sensitive RL under an Iterated Conditional Value-at-Risk (CVaR) objective. Both linear and general function approximations are discussed in this work. Several algorithms are proposed to address such problems with the provable complexity analysis. A novel efficient approximation of the CVaR operator and a new ridge regression\nwith CVaR-adapted regression features are also provided. Besides, human feedback is integrated into this framework.", "questions": "no comment.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is easy to follow, and the technique novelty is clear. To address the risk-sensitive RL under an Iterated Conditional Value-at-Risk (CVaR) objective, the authors propose two sample\nefficient algorithms with sample complexity analysis, ICVaR-L and ICVaR-G, for two different function approximations correspondingly. Also, the upper regret bounds of algorithms are provided. Besides, the authors consider the risk-sensitive RL in the human feedback setting.", "weaknesses": "While I typically do not complain about the empirical results of this paper, I do expect that some implemented results on real-world practical problems could be contained in this paper.", "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": "", "extra_scores": {}}, {"review_id": "BvjRm3yWuR", "reviewer": "Reviewer_DGv8", "summary": "This paper studies the iterated CVaR objective RL under both linear and general function approximations. Additionally, the authors have incorporated human feedback into the framework. The paper offers theoretical guarantees for all the proposed algorithms in various settings.", "questions": "Some typos:\n\nOn page 2, in the first bullet, $\\sqrt{\\alpha^{-H}}$ → $\\sqrt{\\alpha^{-2}}$\n\nOn page 8, it should be $\\sigma(x)$ in regularity.\n\nWhat is $\\tilde{\\sigma}$ in equation (14)?\n\nCompared with the tabular setting, why the linear case has a bad dependence on H?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is well-written and well-organized. It effectively conveys the high-level intuition behind the algorithm. The paper provides a comprehensive discussion of the theoretical results for iterated CVaR RL in various settings, including linear function approximation, general function approximation, and the incorporation of human feedback. Notably, the paper introduces a novel approximation operator for the true CVaR operator in the linear approximation setting, which could be of independent interest.", "weaknesses": "The technical aspects of the algorithms appear somewhat limited and are relatively standard in the literature. Additionally, the algorithms are not efficient, and obtaining a solution for the approximate CVaR operator is not easy.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)