Provably Efficient CVaR RL in Low-rank MDPs
Authors: Yulai Zhao
Wenhao Zhan
Xiaoyan Hu
Ho-fung Leung
Farzan Farnia
Wen Sun
Jason D. Lee
Venue: ICLR 2024 poster (2024)
Keywords: reinforment learning theory
risk-sensitive reinforment learning
Conditional Value at Risk
Primary area: reinforcement learning
TL;DR: We present the first provably efficient CVaR RL algorithm in low-rank MDPs.

Abstract: We study risk-sensitive Reinforcement Learning (RL), where we aim to maximize
the Conditional Value at Risk (CVaR) with a fixed risk tolerance $\tau$. 
Prior theoretical work studying risk-sensitive RL focuses on the tabular Markov Decision Processes (MDPs) setting.  
To extend CVaR RL to settings where state space is large, function approximation must be deployed. 
We study CVaR RL in low-rank MDPs with nonlinear function approximation.  Low-rank MDPs assume the underlying transition kernel admits a low-rank decomposition, but unlike prior linear models, low-rank MDPs do not assume the feature or state-action representation is known. 
We propose a novel Upper Confidence Bound (UCB) bonus-driven algorithm to carefully balance the interplay between exploration, exploitation, and representation learning in CVaR RL. 
We prove that our algorithm achieves a sample complexity of $\tilde{O}\left(\frac{H^7 A^2 d^4}{\tau^2 \epsilon^2}\right)$ to yield an $\epsilon$-optimal CVaR, where $H$ is the length of each episode, $A$ is the capacity of action space, and $d$ is the dimension of representations.
Computational-wise, we design a novel discretized Least-Squares Value Iteration (LSVI) algorithm for the CVaR objective as the planning oracle and show that we can find the near-optimal policy in a polynomial running time with a Maximum Likelihood Estimation oracle. 
To our knowledge, this is the first provably efficient CVaR RL algorithm in low-rank MDPs.

Published as a conference paper at ICLR 2024
PROVABLY EFFICIENT CVAR RL IN LOW-RANK MDPs
Yulai Zhao
Wenhao Zhan
Princeton University yulaiz@princeton.eedd
Princeton University
wenhao. zhan@princeton edu
Xiaoyan Hu
Ho-fung Leung Independent Researcher ho-fung 1 leug@ look com
The Chinese University of Hong Kong xyhu21 @cse.
cuhk. cuhk. edu. hk
Farzan Farnia
Wen Sun
The Chinese University of Hong Kong farnia@cse cuhk. edu. hk
Cornell University ws ws455ecorne11.c edu
Jason D. Lee
Princeton University
jasonlee@prinnetonn.dd
ABSTRACT
We study risk-sensitive Reinforcement Learning (RL), where we aim to maximize the Conditional Value at Risk (CVaR) with fixed risk tolerance Prior theo- retical work studying risk-sensitive RL focuses on the tabular Markov Decision Processes (MDPs) setting. To extend CVaR RL to settings where state space is large, function approximation must be deployed. We study CVaRR RL in low-rank MDPs with nonlinear function approximation. Low-rank MDPs assume the derlying transition kernel admits a low-rank decomposition, but unlike prior linear models, low-rank MDPs do not assume the feature state-action representation is known. We propose novel Upper Confidence Bound (UCB) mous-ddiven al- gorithm carefully balance the interplay between exploration, exploitation, and representation learning in CVaR RL. We prove that our algorithm achieves a sam- ple complexity of Ô H A² -222
to yield an e-optimal CVaR, where H is the length of each episode, A is the capacity of action space, and d is the dimension of rep- resentations. Computational-wise we design novel discretized Least-Squares Value Iteration (LSVI) algorithm for the CVaR objective as the planning oracle and show that we can find the near-optimal policy in a polynomial running time with a Maximum Likelihood Estimation oracle. To our knowledge, this is the first provably efficient CVaR RL algorithm in low-rank MDPs.
INTRODUCTION
As a widely adopted framework to deal with challenging sequential decision-making problems, Re- inforcement learning (RL) (Sutton& & Barto 2018) has demonstrated many empirical successes, e.g., popular strategy games (Silver et al. 2016 2017 Vinyals et al.) (019).. However, the classical RL framework often prioritizes the maximization of the expected cumulative rewards solely, which ren- ders not suitable for many real-worl applications that face possible failure or safety concerns. In high-stake scenarios such as autonomous driving (Isele al. 2018) Wen al. 2020), finance (Davis & Lleo) 2008 Wang et al.) 2021] Filippi et al. (2020) and healthcare (Ernst et al. 2006; Coronato al. 2000),, optimizing only the expected cumulative rewards can produce policies that underesti- mate the risks associated with rare but catastrophic events. To mitigate this limitation, risk-sensitive
decision- decision-making has recently grown more popular (Hu & Leung 2023).
"qqual contribution. Listing order random.

---

Published as a conference paper at ICLR 2024
To this end, risk measures like Conditional been integrated into the RL-based systems as a performance criterion, yielding a more balanced approach that encourages policies to avoid high-risk outcomes. As a popular tool for managing risk, the CVaR metric is widely used in robust RI. (Hiraoka et al. 2019), distributional RI. (Achab et al.) 2022), and portfolio optimization (Krokhmal For random variable X with distribution P and confidence level (0, 1), the CVaR at confidence level 7 defined as
(CVaR) (Rockafellar al., 2000) have
al.] (002). CVaR quantifies the expected return
in the worst-case scenarios |
CVaR, (X) = sup [b - -x--EExxX-"""
bER
where x+ max(x; 0). In this paper, we consider the random variable X as the cumulative reward of a specific policy where randomness comes from the MDP transitions and the policy itself. We aim to maximize this objective to capture the average worst values of the returns distribution at a certain risk tolerance level r.
The most related works to this paper are Bastani et al. (2022) and Wang et al.) (223). Specifically, Bastani et al. (2022) proved the first regret bounds for risk-sensitive RI. with CVaR metric (CVaR RL), and Wang et al. (2023) improved the results to achieve the minimax optimal regret. However, their algorithms are restricted to the tabular setting, they are inefficient when the state space is large. To overcome such limitation, we introduce function approximation to the MDP structure and consider low-rank MDPs (Jiang et al. 2017) in this paper.
In low-rank MDPs, the key idea to exploit the higg--iimessoonl) structure in the model transitions of the MDP by representing them with lower-dimensional structure. This is often implemented by assuming the MDP transition kernels admit a low-rank factorization, i.e., there exist two unknown mappings (ss),, ((8, a), such that the probability of transiting to the next state s' under the current
state and action (s, a) is P(s'(s.a) a) = (0s')" σ(s,a). a). Low-rank MDPs generalize popular RL
models including tabular MDPs, linear MDPs (Jin al., 2020) and block MDPs (Du et al.] 2019
Efroni et al. 2021). and are widely applied in practice (Zhang et al. 2021 2022).
2020
2021
Sodhani et al.
Unlike linear MDPs, since the underlying v and 6 are unknown, we need to carefully balance rep- resentation learning, exploration, and worst-case failure stakes low-rank MDPs. The application of non-linear function approximation further complicates the problem, for controlling model errors state and action-wise becomes much harder (Wang et al. (023). Morcover, even within a given MDP, planning in CVaR RL is not a straightforward task as the CVaR metric exhibits non-linear structure (in stark contrast to standard rest-neutral RL), which results in extra computational over- head. All of these challenges call for more comprehensive algorithm design for the risk-sensitive RL in low-rank MDPs
In this paper, aim to fill gap in the existing body of knowledge by exploring the interplay between risk-averse RI. and low-rank MDPs. We summarize our contributions as follows.
Contributions. First, design an oracle-efficient representation learning algorithm called ELA (REprensentation Learning for CVAR), which optimizes the CVaR metric in low-rank MDPs. ELA leverages an MLE oracle to learn the model dynamics while simultaneously constructing Upper Confidence Bound (UCB)-type bonuses to encourage exploration of the unknown environment. We provide a comprehensive theoretical analysis of the algorithm, demonstrating that ELA would pro- vide an e-optimal CVaR with Ō(1/²²) samples. To the best of our knowledge, ELA is the first provably sample-efficient algorithm for CVaR RL in low-rank MDPs.
Second, improve the computational complexity of ELA planning, we introduce a computationally efficient planning oracle, which, when combined with ELA, leads to the ELLA (REprensentation Learning with L.VI for CVAR) algorithm. This algorithm leverages least-squares value iteration with discretized rewards to find near-optimal policies via optimistic simulations within the learned model. Importantly, the computational cost solely depends on the dimension of representations rather than the state space size. We show that ELLA requires a polynomial running time in addition to polynomial calls to the MLE oracle.
Standard CVaR definition considers average worst-case loss, thus a lower value is more desirable. How- ever, in this work, we aim to obtain a higher CVaR in the RL. context as we are maximizing rewards. In RL, planning refers determining the optimal policy and optimal value function within given MDP.
2

---

Published as a conference paper at ICLR 2024
2 RELATED WORK
Low-rank MDPs. Theoretical benefits of low-rank structure in MDPs have been broadly explored
in various works (Jiang et al. 2017 Sun al.] 2019 Du et al., 2021; Sekhari al. 2021 Huang
et al. 2023). In a contextual decision process (a generic RL model with nich observations and func- tion approximation) with a low Bellman rank, OLIVE (Jiang et al. 2017) yielded a near-optimal policy with polynomial samples. Additionally, [Sun et al. (2019) introduced provably efficient algo- rithms based on a structural parameter called the witness rank, demonstrating that the witness rank is never larger than the Bellman rank (Jiang et al. 2017). Despite their provable efficiency, these algorithms lack computational efficiency.
Leveraging Maximum Likelihood Estimation (MLE) as its computation oracle, Flambe (Agarwal ct al., 2020) proposed the first computationally efficient algorithm that was also provably efficient in low-rank MDPs. Following a similar setup, Rep-UCB (Uehara et al., 2022) improves the sample complexity dependencies of Flambe. The key to the improvements is a careful tradeoff between exploration and exploitation by combining the reward signal and exploration bonus.
CVaR RL. There is a long line of works studying (static) CVaR in RL., which refers to the CVaR of accumulative reward beyond certain risk threshold (Chow & Ghavamzadehi 2014 Chow al.)
2013 Tamar et al.) 2015 Bastani et al. 2022 Wang et al. 2023). For tabular MDPs, much work has
been done on value-based algorithms (Chow al. 2015 Stanko Macek 2019). However, these results often require the planner to know the model transitions of the MDPs, which is generally in- feasible. Recently, there has been a growing interest in the more general setting where the unknown model transitions are learned through online interactions YYu et al., [2018) Bastani et al.) [022] Wang al. 2023). However, their results are restricted to the tabular setting and cannot be combined with function approximation, where the state space is often enormous.
Prior works have also studied risk-sensitive RL in the context of other risk measures. Specifically, Du al. (2022) proposed Iterated CVaR RL, also known as dynamic CVaR, and Chen et al. (2023) demonstrates regret guarantees for Iterated CVaR RL with general function approximations. How- ever, iterated CVaR is intrinsically different from the static CVaR in our setting. Iterated CVaR quantifies the worst 7-percent performance at each step of decision decision-making. Such a definition al- lows the agent to control the risk throughout the decision process tightly, whereas our setting aims to maximize the CVaR of the total reward. Therefore, their algorithm designs and analysis techniques do not apply our tasks.
Our work also focuses on the static CVaR in RL. Specifically, we present the first sample-efficient algorithm for optimizing the static CVaR metric that carefully balances the interplay between risk- averse RL and low-rank MDP structure. Furthermore, we design a computationally efficient plan- ning oracle that makes our algorithm only require polynomial running time with an MLE oracle.
PRELIMINARIES
Notations. We will frequently use [H] to denote the set (1...., H). Denote ASS) as the distribu- tion over space S. Let (LA) be the uniform distribution over the action space. In this work, we use the standard (-), 2(.)) and ((-) notations to hide universal constant factors and use Ö()) to hide logarithmic factors. Please see Table I for a comprehensive list of notations used in this work.
3.1 LOW-RANK EPISODIC MDP
We consider an episodic MDP M with episode length E N, state space S, and a finite action space A. At each episode & E [K], trajectory T - ($1, 01, $2, a2, ... SH. aH) is generated by an agent, where (a) 81 E a fixed starting state (b) at step J, the agent chooses action according to a history-dependent policy a 7--[T--1, 8k) where 7h-1 == (81, (81,11," ".,..... .a=11 and (c) the model transits to the next state $h+1 ~ P (- (-|sk,
1) denotes the history Sh ap). The agent repeats these steps till the
end of the episode. For each time step, operators P S A + A(S) denote the (mon-stationary) transition dynamics, whereas Th 8 x A + ( 1)) is the (immediate) reward distribution the
Note that any Hllenghh episodic MDP with a stochastic initial state is equivalent to (H + 1)-length MDP with a dummy initial state s6-
3

---

Published as a conference paper at ICLR 2024
agent could receive from deploying certain action specific state. We use II to denote the class of all history-dependerr policies. Below, we proceed to the low-rank MDP definition.
Definition 3.1 (Low-rank episodic MDP). The transition kernel P = (P% S + A(S)
admits a low-rank decomposition with rank d if there exist two embedding functions d² = {0 S S A + ne(H and 10* == {0 S + TR )e(HH] such that
(s = (1%) (s,()))
(1)
where (s, a)1 S 1 for all (h, s,a) E [H] S x A. and for any function S + 10, 1] and h [H], it holds that Ises (s)))(s)) S vd. Low-rank episodic MDP admits such decomposition of P
We study the function approximation setting where the state spaces S can be enormous and even infinite. To generalize across states, assume access to two embedding classes Vi C ( + Rd) and कh C {S + Rd), which are used to identify the true embeddings (ob", o²)). Formally, we need the following realizability assumption, which is proven essential for obtaining performance guarantees independent of the state space size in low-rank MDPs (Agarwal et al. 2020).
Assumption 3.2. There exists a model class F ( L) such that U. E V. D Yh E [H].
We expect to obtain sample complexity that scales logarithmically with the (finite) cardinality of the model class F. Extensions to the infinite function classes with complexity measures are possible. See more discussions in (Agarwal et al. 2020).
3.2 RESK-SENSITIVE RL AND AUGMENTED MDP
We study risk-sensitive RL with the CVaR metric. Throughout the paper, let E (0. be fixed risk tolerance. First, we recall the classical definition: for a random variable X E [0, 1] is from distribution P, the ietiiiiioal-vllue-eeee at-risk (CVaR) corresponding to the risk tolerance is defined as
CVaR-(X)= = sup {e-r-1 1Ex-r((e- ((xxr((c-x)t] cE(O.1]
where (ar)+ max(æ; 0) for any TR. Interestingly, the supremum in the expression is achieved when e is set as the r-th percentile (unknown before planning), also known as value-at-risk (VaR), i... I, (= E IR P(X S x) 2 T).
In risk-sensitive RL, X represents the stochastic cumulative reward accumulated over H successive actions and state transitions: X =
This multi-step nature of risk-sensitiv RL brings the dynamic planning structure to the setting and makes difficult. We may make an intuitive insight of by considering it a initial budget, which affects the agent's action selection and needs to be carefully managed during the planning. Particularly, after receiving a random reward Th at each timestep h E [H] the learner deducts it from the current budget, i.e., Ch++1 Ch - F' where C₁ is the remaining budget and Ci = c. The main task of risk-sensitive RL is to interplay carefully between policy planning, exploration, and budget control. Inspired by this observation, we incorporate the available budget as an additional state variable that could impact the agent's is choice of action. Formal descriptions of the augmented MDP are introduced below.
Augmented MDP. We introduce the augmented MDP framework (Bäuerle & Oul 2011 to study CVaR RL, which augments the state space in classic episodic MDP to SAug S [0, H] that includes the budget variable as an additional state. The transition kernel of the state and the imme- diate reward distribution are the same as the original MDP M. Inspired by the observation above, we consider policies defined on the augmented state space IT Aug := {IT SAng A(A)).
In the augmented MDP, the agent rolls out an augmented policy и E A with initial budget e E [0, H) follows. At the beginning of an episode, the agent observes the augmented state (s1, C1), selects action a1 ~ <-1|s1, )1), receives reward ri ~ Ti (11, a1), and transits to 82 ~ PT (-(ss,, a1). Most importantly, the available budget is also updated: C2 Ci ri. The agent then chooses an action based on the (#2, 62) pair. The procedure repeats for H times until the end of the episode. For any π E Auug. the (augmented) Q-function is defined
(<1-
H
(s.c-(s,c.a) == =E,,p-
Σ 1=
re re oz)
s. = C, aA = a
4

---

Published as a conference paper at ICLR 2024
for any (h,s,c,a) [H] S [0, H] x A and the (augmented) value function is defined
Vi,p-(s: c) (-(s,) (s,,,(s,
(3)
for any (h) [M] x [0, H.. The Bellman equation is given by
(
E
V Vitzls',cc-)
this paper, we aim to find the optimal history-dependent policy maximize the CVaR objective, i.c.
Goal metric.
CVaR == max (V)T) TEl
c- min El(c Be(cel(([Ri) B((c- cE(O,
sup
where R(T)) is the random cumulative reward of policy π in M. Nevertheless, it is known that min ( [c R[ can be attained by augmented policy n' E II with initial
budget e (Wang et al. 2023). Thus we can indeed focus on searching within æ E ATug.
CVaR = max cE[0,H
- min VT,P, (51,
(a(R,(((*)) ,c"))
(4)
FETINN
where n² E AAgg is the optimal augmented policy and c* E [0, H) is the optimal initial budget, and we overload R( c) denote the stochastic cumulative reward when the agent rolls out the augmented policy ı with initial budget e in augmented MDP.
4 ALGORITHM
In this section, we present the ELA algorithm for risk- RI. in low-rank MDPs. The pseudo- code listed Algorithm [ The algorithm is iterative nature, where the k-th episode proceeds in three folds: (1) we collect new data by rolling in with the exploration policy x* starting from the initial budget - (2) Then, all transitions collected so far are used two aspects. First, we pass all transition tuples to the MLE oracle (Line 11). The MLE oracle returns embedding functions (W%, @h) for each h, which determine the model. Second, we compute the exploration bonus using the latest learned representation ø. (3) The algorithm performs VI on the learned model with the reward signal to obtain the exploration policy-budget pair (Λ² e*) use in the next itcration. After K iterations, we output the current model and all policy-budget pairs. Next, we illustrate more details about these steps.
4.1 DATA COLLECTION
During training, we collect two (disjoint) sets of transition tuples to compute the bonus terms and estimate the transition kernels. These two datasets are different in their (marginalized) distributions and facilitate the regret analysis in Section 4.3 Next, we clarify how data are collected and added to the two sets.
To collect new transition tuple for each dataset Dr, and Dr, (vh E [H- I),, at the k-th itera- tion, the algorithm roll outs policy - with initial budget ch11 to obtain two trajectories. The difference occurs at the (h 1 1)-th timestep. Particularly, to obtain (sn, ajs 8441) for Dr, the algo- rithm keeps on to exccute policy - for one more step and observes state 8h. Then, a uniform (,)s,,aa)) However, to obtain (ōk; ān, +/)+) for Dn, the algorithm takes two consecutive uniform actions at timesteps h - 1 and h. i.e., ah-1 U(A), 5n. P ãn ~ U(A), and receives state s/ Intuitively, dataset Dj, reveals the behavior of the exploration pplicy-budger pair (T*, up to the h-th timestep, which facilitates the design of bonus terms (cf. Lemma C.2 Meanwhile, dataset D, enhances the exploration and leads to improved estimates of transition kernels (cf. Lemma
action an U (AA) is taken to receive the next-state š4+1
At first sight, the data collection procedure requires 2(H - 1) trajectories per iteration (i.e., one trajectory for Dr and one trajectory for D,)) To save sample (trajectory) complexity, collect
5

---

Published as a conference paper at ICLR 2024
transition tuples for Dj, and D), at the h, (h-1) steps in go, respectively (Lines 8-10). Therefore, the algorithm only requires H trajectories per iteration. For both sets, new transition tuples are concatenated with the existing data to perform representation learning, i.c., learning factorization and representation by MLE (Line 11).
4.2 REPRESENTATION LEARNING AND BONUS-DRIVEN VALUE ITERATION
MLE oracle. In the function approximation setting, the agent must estimate the model structure as accurately as possible. Collected transition tuples are used to compute model transitions through the MIEE oracle. As general approach used to estimate the parameters of probability model, MLE
also gaining more focus in low-rank MDPs (Agarwal et al. 2020 Uehara et al. (022).
Value Iteration. Based on the learned model, the algorithm runs Value-Iteration (VI) with the exploration bonus term. In risk-sensitive RL, for any т E Aug and (h, 8, [H] 8 x [0, H). we define value function enhanced with exploration bonus by S
as
V c) Ex,P [
Σ h'
The (so (ks)),
bwrssw, anr) Sh =
(5)
where we deduct the exploration bonus term because the agent desires to minimize the value func- tion (4) in risk-sensitive RL. Such value function used perform VI and update policy on the learned model P, since the learner has no prior knowledge of the real model transitions. Therefore, obtaining an accurate estimation of the model determines the quality of the output policy.
In Algorithm T we assume the learner has access to exact VI (Line 15). However, we remark that this step is not computationally efficient due to the continuity of e and potentially large state space S. To overcome such a computational barrier arising from the nature of controlling risk while planning, in Section 5 we provide a computationally efficient planning oracle that performs LSVI with discretized reward function (with sufficiently high precision). We rigorously prove that we only need polynomial running time with the MLE oracle to output near-optimal CVaR.
4.3
MAIN RESULTS
In this subsection, we are ready to demonstrate our theoretical guarantees that characterize the regret and sample complexity bounds.
Theorem 4.1. Fix 8 E (0, 1). Set the parameters in Algorithm 7 as:
at = = +
(1F
|F(HK) )):
[F|HK x = o d 8
0
have two equivalent interpretations of the theoretical results. In terms of PAC bound, with probability at least -8. 8. the regret is bounded by
K Σ CVVRR CV (t)) = Vlgg ((F1/8)
1=1
Alternatively, we can interpret in terms of sample complexity; w.p. at least 1 1 ô, to present an e- optimal policy and budget pair s.t. CVaR" CVaR, (R(f,, 2)) The total number of trajectories required is upper bounded by
A log (1F1/8)
T222
Proof.
The proof can be found in Appendix
In Theorem 4. present the first regret/sample complexity bounds for CVaR RL with function approximation, in which exploring the unknown action/space spaces posits extra difficulty. We explicitly characterize the number of samples required to output e-optimal CVaR in terms of the length of the episode H, the action space size A, the representation dimension d, and confidence level The theorem has explicit dependence on state space S, proving nice guarantees even in

---

Published as a conference paper at ICLR 2024
Algorithm ELA
Require: Risk tolerance T E (0, 1J, number of iterations K, parameters {1o hEEKK] and {a ]eE[K)-
models F = { V }). failure probability 8 E (0, 1).
1: Set datasets D,, D, <- 0 for each h E H - 1].
2: Initialize the exploration policy TO < [mg (s. (s.c) U(A), for any (s,c) E ESX x 10, Me)((
3: Initialize the budget c² 6-
4: for iteration k L...., K do
5: Collect a tuple (81, Ø1, x22) by taking ã1 ~ U(A), ~ (1)
6: Update D1 t D1 U {(51, $2)
7: for h = 1,..,
do
8:
Collect two transition tuples (sh, an, 8a+1) and (sn+1, 11+ 8/42) by first rolling out TK-1 starting from ((1, into state 8h, taking aş U(A), and receiving $141 P7 (-1sn, an), then taking 0h+1 ~ ((A) and receiving 5/ Ph (-881+1, @x+1). 1).
9:
Update Dr +- DA U {(8,, an, 81+1)}-
10:
Update Dn+1 + Da+1 U (1 @1+1, 24422 HH- 2.
11:
Learn representations via MLE
Pr. :::=(Wn, @k) arg max (V.O)EF
Σ
log ((5)44)).0$$h an))
Update empirical covariance matrix En E(anjED, ( + la Set the exploration bonus:
(s, a) min a () h H
h=
end for Run Value-Iteration (VI) and obtain ct <- arg max {c- min,
min- V 1.2,(01,,0).
16: Set r² + arg ming V (5,,
17: end for
Ensure: Uniformly sample l from [K]. return (я, = (M* ct).
the infinite-state setting. As far as we are concerned, the only existing theoretical guarantees in the field of risk-averse CVaR RL were provided in the tabular setting (Bastani et al. 2022 Wang al., 2023), where representations are known. Moreover, these results explicitly depend on [S], thus can not apply the function approximation setting with enormous state space. Given the above, our work accomplishes a great leap by incorporating exploration in the comprehensive function approximation setting, which evidently better aligns with real-world applications than the tabular and/or linear MDP settings.
As for the sample complexity, the dependencies on and d match the same rates the analysis of risk-neutral RL in low-rank MDP (Uehara et al. 2022), showing our algorithm overcomes the extra hardness of balancing exploration and budget control even with large action space. Our sample complexity matches the dependency Hoeffding bonus (Wang et al. 2023) and UCB algorithm (Bastani et al. 2022). On the other hand, the sample complexity enjoys an Ω + lower hound(Wang et al. 2023 Theorem 3.1). Tightening the dependency on F is left as future work.
with the rates in the CVaR-UCBVI algorithm with the
Our theoretical guarantees have slightly worse dependency on H while Rep-UCB (Uehara al. 2022 scales as HS,, since we do not assume the trajectory reward normalized to 1. we adopt this reward normalization, our PAC bound can be improved to Ō(H*), and thus matching the rate. In addition, point out that it might be possible to reduce another H² dependency by utilizing Bernstein-tyre bonus in the algorithm instead of the Hoeffding -eyfi bonus, which is left for future work.
7

---

Published as a conference paper at ICLR 2024
5 PLANNING ORACLE: CVaR-LSVI
In Algorithm| we need to calculate c < arg (f,,H fc-r-1 ming 1 (+1, (Line 15), which is not naively computationally efficient since the objective c- -- min, V concave. this section, we introduce a feasible planning oracle for this step and provide the cor- responding theoretical guarantees. For simplicity, we assume the reward distribution is discrete and ra (s. a) only takes value in iv where v > 0 and 0 < i I [1/u]. For a continuous r, we can discretize it with sufficiently high precision that all the analysis still applies. The details deferred to Appendix
1. 1, c) is not
B
Since the supremum of the CVaR objective 2 is attained at 7-th quantile of the cumulative reward distribution, which is also discrete when the reward ra is discrete, we can only search cx within the grid in Line 15 of Algorithm
Tellaws 1, iv) }
arg max in - min V [/VS
Nevertheless, if we run standard value iteration to calculate min, VT. (T,,,($1,, our sample complexity will scale with the size of the state space [S], which can be infinite in low-rank MDPs. To circumvent such dependency on (S], we introduce a novel LSVI-UCB algorithm for the CVaR objective in this subsection, called CVaR-LSVI. In the following discussion, we fix i where 0 I We will drop the subscript P and b
S H /v] and aim calculating min V
when it is clear from the context. We use V to denote min
V A.P.B and (P,r) to denote the
MDP model whose transition is P and reward distribution is r.
First, recall that the discrete reward distribution (x a) only takes values of in where 0 S í S [1/v]. This means that it is always linear with respect a ([1/u] + 1)-dimension vector:
ra(iv]ss a) = (on. (8, a), 1h.-- (iv)),
where (s, rn (tvls,)) and (1o) = e, for all 0 S i [1/e] and s E S,a A,
[H]. Since Pa(s'|s, a) = (sn(s, (s))) this implics that for all s, E S, E A, e 5
i < [1/v], we have
Ph 1s, ald a) (s, a), (n((s,iv))
where on = (n a) @ (s, a) and (s', iv) = To (8, a) @ (io).
The linearity of transition and reward implies that we can utilize LSVI to compute Q7 (s. c, a). More specifically, we propose an iterative algorithm consisting of the following steps:
Step 1: Ridge Regression. In the t-th iteration, denote the trajectories collected before t-th iteration by {(5], a r - Let V (s, iv) iv for all E S and 0 I i < [H/u]. From h H to h 1, for each 0 i [H/u], we first compute:
w (1v) + (A Σ
(sh at) [vitz(0h+nno0-r1
where A,, = AI -ラ 1- 3 / a² (on TT))T.
Then for any j [1-1], a E A and 0 S [H/b], we can estimate the value function (i iv) as:
(h( (n, a) = Clip ( (bbnish a) + (on(5h. a))" (1o) - ( ()))))))))
(/ iv) min Qh (1/,, a).
Note that although we do not compute Q (s, iv, a) for all E S (which will incur computation cost scaling with (S),, they can be implicitly expressed via wi, (iv), i.e. for all E S,a A, i < [H/U]. we know
(8, in, a) = Clip, ( (-ba(s,))) a) + (0,( wf() - 21 (8, (lls)))))) (
(6)
8

---

Published as a conference paper at ICLR 2024
Step 2: Sample Collection. In the t-th iteration, simulate the greedy policy म' (w.r.t. the estimated function Q% (8, iv, a)) with the initial budget c₁ i in the MDP model (P,r) r)) and collect trajectory (5% of 1=1 Then, go back the first step.
Step 3: Policy Evaluation. After reteatinn the above two steps for iterations, simulate each
policy H' with initial budget Ci = ir (P,r) for T2 episodes. Suppose the collected trajectories
are {<//
15 t. " h=1
and we estimate the empirical value function of म as follows:
V (s
1
dn h (s
Σ h=1
by (s aa))).
T2
1=1
Then simply use max)e(T)) VIF' (s1, 21v) surrogate for (11,
The details of CVaR-LSVI are stated in Algorithm (cf. Appendix B). Note that in Line 16 of Algo- rithm 1 can also use the above CVaR-LSVI algorithm to compute オ². Combining Algorithm and 2 we can derive a computationally efficient algorithm, called ELLA, for CVaR objective in low-rank MDPs, which is shown in Algorithm B (cf. Appendix [B. Now,
ready present the computational complexity of ELLA. Particularly, the following theorem characterizes the computa- tional cost for finding e-optimal policy:
Theorem 5.1 (Informal). Let the parameters in Algorithm 7 and 2 take appropriate values, then we have with probability least 1 1-8 5 that CVaR, CVaR, (R(T, 2)) e where (f, is the returned policy and initial budget by Algorithm In total, the sample complexity is upper bounded
by δ
H² d2d log (F)
The MLE oracle called Ô
H² A2d log. [2l times and the rest of the
T"
H d log 121
computation cost Ô
Theorem 5.1 is special case of the continuous reward setting, whose formal statement is in Theo-
rem B.3 and the proof is deferred to Appendix D Theorem (5l]emmattindiiattt.. that Algorithm BJis able to find a near-optimal policy with polynomial sample complexity and polynomial computational com- plexity given an MLE oracle. Note that calling CVaR-LSVI in Line 17 and 20 Algorithm 3 will not increase the sample complexity because we are only simulating with a known model (P. and do need interact with the ground trouhd-truth environment.
6 CONCLUDING REMARKS
The paper proposes ELA, the first provably efficient algorithm for risk-sensitive reinforcement learn- ing with the CVaR objective in low-rank MDPs. ELA achieves sample complexity of Ô(1 ((1/2)) to find an e-optimal policy. To improve computational efficiency, we propose the ELLA algorithm, which leverages least-squares value iteration upon discretized reward as the planning oracle. Given the MLE oracle, we prove this algorithm only requires a polynomial computational complexity.
Regarding future work, we believe establishing lower bounds for CVaR RL in low-rank MDPs is an exciting and challenging direction due to the complexity the risk landscape and the non-line con-linearity in function approximation methods used. We point out that even for standard episodic RL, which is well-studied area, we have only recently seen some results on sample lower bounds in the context of low-rank MDPs (Cheng et al., 2023 Zhao et al.) (023). However, these results do not directly apply to the CVaR risk landscape. We suppose the sample complexity lower bound may take the form of Ω ( 7CT according to the lower bounds in low-rank MDPs (Cheng et al. 2023 Zhao et al. 2023) and tabular CVaR RL (Wang et al. 2023), which implies that our algorithm has a loose dependency
on H. and т. Such gap might be alleviated if we use the Hoeffding tetftpiin-typeeeee bonus instead of the Bernstein-type bonus in the bonus-driven exploration. We leave it as future work to tighten the dependencies.

---

Published as a conference paper at ICLR 2024
REFERENCES
Mastane Achab, Reda Alami, Yasser Abdelaziz Dahou Djilali, Kirill Fedyanin, Eric Moulines, and Maxim Panov. Distributional deep q-learning with evar regression. In Deep Reinforcement Learn- ing Workshop NeurlPS 2022, 2022.
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complex- ity and representation learning of low rank MDPs. Advances in neural information processing systems, 33:20095-20107, 2020.
Osbert Bastani, Jason Yecheng Ma, Estelle Shen, and Wanqiao Xu. Regret bounds for risk-sensitive reinforcement learning. Advances in Neural Information Processing Systems, 35266, 2022.
Nicole Bäuerle and Jonathan Ott. Markov decision processes with average-value-at-risk criteria. Mathematical Methods of Operations Research, 74:361-33 153311379,100 2011.
Yu Chen, Yihan Du, Pihe Hu, Siwei Wang, Desheng Wu, and Longbo Huang. Provably efficient iter- ated evar reinforcement learning with function approximation. arXiv preprint arXiv:2307.02842, 2023.
Yuan Cheng, Ruiquan Huang, Jing Yang, and Yingbin Liang. Improved sample complexity for reward-free reinforcement learning under low-rank mdps. arXiv preprint arXiv:2303.10859, 2023.
Yinlam Chow and Mohammad Ghavamzadeh. Algorithms for CVaR optimization in MDPs. Ad- vances neural information processing systems, 27, 2014.
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.
Antonio Coronato, Muddasar Naeem, Giuseppe De Pietro, and Giovanni Paragliola. Reinforcement learning for intelligent healthcare applications: A survey. Artificial Intelligence in Medicine, 109: 101964, 2020.
Mark Davis and Sébastien Lleo. Risk-sensitivg benchmarked asset management. Quantitative Fi- nance, 8(4):415 426, 2008
Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient RL with rich observations via latent state decoding. In International Conference on Machine Learning, pp. 1665-1674, PMLR, 2019.
Simon Du Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: structural framework for provable generalization in RL. Interna- PMLR, 2021.
tional Conference on Machine Learning, pp.
Yihan Du, Siwei Wang, and Longbo Huang. Provably efficient risk-sensitive reinforcement learning: Iterated evar and worst path. In The Eleventh International Conference on Learning Representa- tions, 2022.
Yonathan Efroni, Dipendra Misra, Akshay Krishnamurthy, Alekh Agarwal, and John Lang- ford. Provable rl with exogenous distractors via multistep inverse dynamics. arXiv preprint arXiv:21 2021.
Damien Ernst, Guy-Bart Stan, Jorge Goncalves, and Louis Wehenkel. Clinical data based optimal STI strategies for HIV: reinforcement learning approach. In Proceedings of the 45th IEEE Conference on Decision and Control, pp. 667-672. IEBE, 2006.
Carlo Filippi, Gianfranco Guastaroba, and Maria Grazia Speranza. Conditional value-at-risk beyond finance: survey. International Transactions in Operational Research, 27(3): 2020.
Takuya Hiraoka, Takahisa Imagawa, Tatsuya Mori, Takashi Onishi, and Yoshimasa Tsuruoka. Learning robust options by conditional value at risk optimization. Advances in Neural Infor- mation Processing Systems, 32, 2019.
10

---

Published as a conference paper at ICLR 2024
Xiaoyan Hu and Ho-Fung Leung. A tighter problem-dependens regret bound for risk-sensitivg inforcement learning. In Francisco Ruiz, Jennifer Dy, and Jan Willem van de Meent (eds.), Pro- ceedings of The 26th International Conference Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pp. 5411-541 1-5437. PMLR, 25-27 Apr 2023. URL htt.::::/pppoeeeeeeseeeeee
ml press https/s/vv00///h2220 html
Audrey Huang, Jinglin Chen, and Nan Jiang. Reinforcement learning in low-rank MDPs with den- sity features. arXiv preprint 2rXiv:230..022522 2023.
David Isele, Alireza Nakhaei, and Kikuo Fujimura. Safe reinforcement learning on autonomous vehicles. In 2018 IEEE/RSI International Conference Intelligent Robots and Systems (IROS), pp. 1-6. IEEE, 2018.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire. Con- textual decision processes with low bellman rank are PAC-learnable. In International Conference on Machine Learning, pp. 1704-1713, PMLR, 2017.
Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference Learning Theory, pp. 2137-2143. PMLR, 2020.
Pavlo Krokhmal, Jonas Palmquist, and Stanislav Uryasev. Portfolio optimization with conditional value-at-risk objective and constraints. Journal of risk, 4:43-68, 2002.
Tyrrell Rockafellar, Stanislav Uryasev, et al. Optimization of conditional value-at-risk. Journal of risk, 2:21 42, 2000.
Ayush Sekhari, Christoph Dann, Mehryar Mohri, Yishay Mansour, and Karthik Sridharan. Ag- nostic reinforcement learning with low-rank MDPs and rich observations. Advances in Neural Information Processing Systems,
2021.
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of Go with deep neural networks and tree search. nature, 529(7587)4484-48) 2016.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis 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-35)) 2017.
Shagun Sodhani, Amy Zhang, and Joelle Pineau. Multi-task reinforcement learning with context- based representations. In International Conference on Machine Learning, pp. 9767-9779. PMLR, 2021.
Shagun Sodhani, Franziska Meier, Joelle Pineau, and Amy Zhang. Block contextual MDPs for continual learning. In Learning for Dynamics and Control Conference, pp. 608-623. PMLR, 2022.
Silvestr Stanko and Karel Macek. Risk-averse distributional reinforcement learning: A CVaR opti- mization approach. In IJCCI, pp. 412-421, 423, 2019.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based RL in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference learning theory, pp.
PMLR, 2019.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Aviv Tamar. Yonatan Glassner, and Shie Mannor. Optimizing the CVaR via sampling. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
Masatoshi Uehara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline RL in low-rank MDPs. In International Conference on Learning Representations, 2022. URL https::/openrewieww net htt.

---

Published as a conference paper at ICLR 2024
Oriol Vinyals, Igor Babuschkin, Wojciech M Czamecki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning, Nature, 575(7782):350-35,, 2019.
Kaiwen Wang, Nathan Kallus, and Wen Sun. Near-minimax-optimall risk-sensitive reinforcement learning with CVaR. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.). Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 35864-35907. URL https:://proceet ngs ml press wwmg233..mmmmmmmmmmmmmm PMIR, 23-29 Jul 2023.
html
Zhicheng Wang, Biwei Huang, Shikui Tu, Kun Zhang, and Lei Xu. Deeptrader: 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.
Pengqian Yu, William B Haskell, and Huan Xu. Approximate value iteration for risk-aware markov decision processes. IEEE Transactions on Automatic Control, 63(9):3135-3142, 2018.
Amy Zhang, Clare Lyle, Shagun Sodhani, Angelos Filos, Marta Kwiatkowska, Joelle Pineau, Yarin Gal, and Doina Precup. Invariant causal prediction for block MDPs. In International Conference on Machine Learning, pp. 1 11214-11224. PMLR, 2020.
Amy Zhang, Rowan Thomas McAllister, Roberto Calandra, Yarin Gal, and Sergey Levine. Learn- ing invariant representations for reinforcement learning without reconstruction. In International Conference Learning Representations, 2021. httptttssss///ppeettss////
id= 2FCwDKRRBU
Canzhe Zhao, Ruofeng Yang, Baoxiang Wang. Xuezhou Zhang, and Shuai Li. Learning adversarial low-rank markov decision processes with unknown transition and full-information feedback. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
12

---

Published as a conference paper at ICLR 2024
A
NOTATIONS
Table 1: List Notations
Basics
= [A
cardinality of the action space
[ (1, H
A()
probability simplex
Zp,a
return distribution of rolling æ with initial budget in an MDP with P
V.p.. : 8 H (0.
defined in
(s), n,P
(s)a)
occupancy of and (s, a) at step h when rolling и with initial budget ej in an MDP with P
df (1 (s) = d (s), dl (
(s, = (
( (s,a)
occupancy of and (s, a) at step h when rolling with initial budget e₁ in the (true) environment
In-Algorithm
Initialization
F (V.
model class regularizer at iteration l: parameter at iteration k
A = O(
a VH*(A+ (o)o
Datasets (at the end of the k-th episode)
D = ((s) of +
8) h ~ U(A)
D = [(3) oh sf 1ivem
$ ~ d. d (XU( x Ph of ~ U(A)
Estimations (at the end of the k-th episode)
((T) 32 hNEHH) pk (P.
learned representations
empirical transition kernel empirical covariance matrix bonus term
S ((s.)EDD (1)) + A
2
In-Analysis
(+(s) = 1/2 Ek-1 as' (s)
occupancy of dataset D
ph(s,a) a) EiD do
k-
(
(s)) = =E (i-1(s')U(a')))
Ph P a')
occupancy of in dataset D
IotxU (A), =KB supt a~t
10 + XRT
Ept & KE a) (00)
I
Et k(E(,,))DDy 100
1 1+
unbiased estimate of Eng (U())
(s) = -1 1/ (-1s, P.(
estimation error L, norm
(T.7)) (-1s,a)
Wh,p
the distribution of the remaining budget at h for any (s, a) when rolling out (I, (r. in MDP with P
(TTA)) (-|1, (TTa)(11ss)) w/(r))) (-18,
wn
the distribution of the remaining budget at h for any (s, a) when rolling out (It, e1) in the true MDP
13

---

Published as a conference paper at ICLR 2024
B ELLA FOR CONTINUOUS REWARD
Now, we extend the analysis in Section S to continuous reward distribution.
B.I DISCRETIZED REWARD
Inspired by Wang et al. 2023), we discretize the reward Th and the budget cy at each step. this way, only need to plan over finite grid. More specifically, suppose the precision is > 0, then we round up the reward r to (r) == [r/u]vc l.. In the following discussion, we use M to denote the MDP which shares the same transition M while its reward is discretized from the original reward distribution r of M, i.e., == Urr). Since the supremum of the CVaR objective ( is attained 7-th quantile of the return distribution, which is also discretized in (P,F), F), we can only search ct within the grid for (P,7) Line 15 of Algorithm
min Vi.p:a(s,, (0)
+ U. arg max
iv T
0S/g[H/v]
rEll
where Aug is the augmented policy class of augmented M and VA. h,P,b b is the value function of (P,F) with bonus b:
V (x.),(s.C)) :EEr, [Co
H
Σ U (rw)) h'=h
by (sw: an)
Sh. 8, C. =
Similarly, the Q function of rP,r) with bonus b is defined as:
(, -EA, ( (a- Σ U (Tw)
H
by (sh (shr,ar)) 84 = 8, 8,Ch = C, an
To stay consistent with Line 15, we also derive the optimal augmented policy of (f, with bonus b in Line 16 of Algorithm i...
f- arg min HEllau Vi,ps(s,,
Note that in Line of Algorithm we need to roll out n² in M to collect samples. Since x² E A works only within the grid, discretize the reward we observe when executing n² in M. which is equivalent to playing the following augmented policy Te E TTAug in M:
h-1
h-1 Eu(r) ) wh E [H].
s
Σ re =
s, (,,c--
(8)
Planning within a discretized grid via 7 will inevitably incur eirors compared to the original ob- jective. Nevertheless, we can show that if the precision v is sufficiently small, the discretized MDP M will be excellent approximation to M and thus the induced error of planning via (7) will be negligible. Formally, let ((( e) denote the return of executing TI Aug with initial budget iv
(0 ? < [H/u]) in M, then we have the following properties from the literature (Wang et al,
2023
Proposition B.1. For any
1,0 policy म E ATag and 0 Sis [H/u], we have
(1) CVaR; < CVaR ==
max OST
CVaR, (R(T,iv)) iv)),
(2) < CVaR (v)) CVaR, (R(T, < Hv
14

---

Published as a conference paper at ICLR 2024
B.2 CVaR-LSVI
With discretization, we only need to search within the grid of c in each iteration. For each discrete value iv, apply the CVaR-LSVI algorithm planning oracle introduced in Section [ The only difference is that now we simulate with the discretized reward model F. The full algorithm is shown in Algorithm
In particular, in Line 12 we can express Q with wf,
2 (s, -lipp-H.H (ba(s, (
(s, T w/ (iv) 311 (s, (s Mllap)))))
(9)
Moreover, note that we can bound the norm of the newly-construeted feature vectors as follows:
Σ
Vnls' iv)ds S (1+ [1/o])vd.
[Sig(1/e]
This bound will be useful in our analysis.
Algorithm CVaR-LSVI
Require: MDP transition model and reward (P = (ō. (),,), r), bonus 8, initial budget i number of iterations T1, parameters À and number of policy evaluation episodes T2.
Compute 6, (s, a) 6x (s, a) & (s, a) for all E [H] E S.a E A where (s, a)
R [1//|++1 and (s,., a)); = (iull a) for all S i < [1/u].
2: for 1,... Ti do
3: Initialize V H+1 (s, iv) + for all s E E and S i [H/b].
4: for h = H ... do
Compute A1, AI + プド (n a (on, (o)
5:
6: Calculate w/, (tv) (A,)) Σ on (s), a/h V 1H/))
7:
do
8:
Compute for all A, si [1/u|:
i0, + Clip H.H| (s), a) + (on (on(sh. T (()))) - Bllōn a)lles)>> )).
V (s), iv) + minge (s,,
9:
10: end for
11: end for
Simulate the greedy policy #' (w.rt. (,, iv; a) defined in 9 with the initial budget ei i the MDP (P.r) and collect trajectory (s), ag. b
13: end for
14: for tort=le 1,.,,,, Ti do Simulate #' with initial budget 6₁ i in (P,T) for Ta episodes and collect trajectories
15:
T
{(h d. (
1=1 N=
j=1
16: Compute V (81,
Eو (iv-EE ( (1)))))))) -Et (n E aht)).
Is
17: end for
18: Return: value estimate min V (11) and policy arg ming (81,
Now let V A. denote min =El Aug
A Then we have the following theorem indicating that Algorithm can do planning in (P,7) accurately with appropriate Ti and T2:
Theorem B.2. Lei
A = 1,3 =0 _dd
(
15 13
H2 H2 log A
TI = δ
To =
62
15

---

Published as a conference paper at ICLR 2024
where log" HdT1 we have with probability at least 1 that
(1)
V (, - V (,
+ =
V (I53(,,,11)) V 1,8,8(01, S 7..
(2)
# V1 (s) and (. (1)) = ming V, ($1, i1) are the returned
=#'
where ar = arg ming
values of CVaR-ISVI.
The proof is deferred to Appendix D.I
B.3 COMPUTATIONAL COMPLEXITY
Equipping ELA with CVVR-LSVI, we can derive ELLA, which is shown in Algorithm 3 Based on the above discussions about discretization and CVaR-ISVI, the computational complexity of ELLA for finding an e-policy can be characterized as follows:
Theorem B.3. Let
[FHHK
FI 8
a =
V HH((IA) de) log
\² =0
dlog
F 11 Add log
H de
K Ō
T22
5
,0= 3H
X 1,8 =
v
HH (37222
H22 log
log I 7262 o
Tj Ō
T2 =T==
Then we have with probability least 1-
CVaR; - CVaR, (R(2, Sc
11 d' log 121
In total, the sample complexity is upper bounded by ò
The MLE oracle is called
δ
11 A=" 121
times and the rest of the computation cost is δ
H?2 a log
The proof is deferred to Appendix D.2 Theorem indicates that even when the reward contin- uous, Algorithm can still achieve polynomial sample complexity and polynomial computational complexity given an MLE oracle.
C PROOFS FOR SECTION
Proof Sketch Recall that R and c the exploration policy and initial budget output from Line 16 of Algorithm D at the end of the k-th iteration, respectively. In the proof, we show that, with probability least 1 5, it holds that
K dx=
F FH
Hk
Regret(K) -
1 Ad V Kyllo
log
[+
log
(10)
which is formalized in Lemma C.I of ((t x²)} satisfies that
Once is established, the suboptimality the uniform mixture
1 K Σ
[ H
CVaR;
(R(T. -- Ad AaRk-t V log
++ dx
log
(11)
K
8
km1
Let the RHS smaller than e, we have that when
H A2d4
K
FlH
Hk
K 0
log
log
7222
dXT
5
16

---

2: Calculate the discretized reward distribution F. Published as a conference paper at ICLR 2024
Algorithm 3 ELLA
Require: Risk tolerance T E (0, 1J, number of iterations K, parameters {1* )EEK and {a heijj
models F = { }), failure probability E (0, discretization precision v, CVaR-
LSV/parameters X, 8, Ti, T2.
Set datasets D/, Dr < for each h E [H- 1/.
3: Initialize the exploration policy TO < {=](s, U(A), any 5,0 s i z
[H/u]he(HH]
4: Initialize the budget 10 -[H/vl.
5: for iteration & = 1...., do
6: Collect a tuple ($1, Q1, (22) by taking 01 U(A), (1)))
7: Update D -- D U (51 (1,
8: for h = I,...
do
9:
Collect two transition tuples (sh, an 8h41) and (sn+1: Wn+1, s/42) by first rolling out æk-1 (defined in (8) starting from (81, (t-1o) into state 8h. taking on U(A), and receiving 5h+1
Ph(-ssp.a, an), then taking ä++1 U(A) and receiving s
Pt++1(155)+ ah+1).
10:
Update Dr, + Dr U {(shs on: $ht2)}-
Update DA+1 + DA+1 U ((5h+1, an+t, ( +2) (iiiiffl if H
12:
Learn representations via MIEE
Pr = (Vn. Gw) + arg max (F.
Σ
log (V(5)+1), 0(5h) an))
ash (E
Update empirical covariance matrix En Elss)Epaon(ss.)) (ss, + + Set the exploration bonus:
13:
14:
(s + min ( h H 2 h -
0
15:
end for
for
0, [H/u]] do
Run CVaR-I.SVI (Algorithm 2 with MDP model (P,r), bonus b, initial budget in and
17:
parameters (, Ti. T2) and let the returned value estimate and policy be (81, iv) and (i).
18:
end for
Obtain 2h + arg maxogig(H/a) iv - ( iv) and x + ((²*).
19:
end for Ensure: Uniformly sample k from [K]. return (), (5* itv)..
20:
the uniform mixture of {(** } is an e-optimal policy. Finally, noting that H trajectories are collected per iteration, we conclude the proof of Theorem 4.1 To establish (10). we decompose the suboptimality of the k-th iteration into
CVaR; CVaR, (R(x", ch)
=c"
Inn
1 11 (81,
(V(a+ (o)ttt,)))))))))) CVARR (c)) (e' -
1, (op=.)((11.c))
<a
yo
1,50 (8),
-- - ct))) ViTP--o(s,,c') ( -6----
CVaR,
1,50 1T
<--1 yir (i )²)
1,84 (e), +
Vm ( Va ((.p==)(1,.c))
(0
17

---

Published as a conference paper at ICLR 2024
where the first inequality holds by the fact that x² is greedy (Line 16 of Algorithm I and the last inequality holds by
CV(R-(R((a e²)) sup (t (t-- ot ) R)+1) 2 c - - R att) I(ee R)+1
tEk
Utilizing simulation lemma C.3 for risk-sensitive RL, we further upper bound terms (i) and (ii) by the error in estimating the transition kernel and the bonus terms, i.e.,
term (i) S (f (% a)
+ +3/1 IE (f (s, a)]
H (8, (s.
term (ii) S E
where (s. == 11 (- a) || By the analysis in Lemma inequality (TO)
C.I and C.2
we prove the
Before proceeding to the detailed proofs, we first introduce the essential regret decomposition.
Lemma C.1 (Regret), With probability 1 8. we have that
K
K dya
[FIH
CVaR; (VaR, cth - /
log
1+
log
(12)
1=1
Proof. Letting (s) PP (-|s,a) a) (-1s, a)ll. condition the event that for all (k, h) [K] x [H], the following inequalities hold
E Bapph (U [1
()) a)) s ct, Bonn (s)) s*
1 (o(s,a)l(s0) a)ll ( - O(Ilo(s, (0 l))l(s (xcca)))))
By Lemmas E.1 and E.2 this event happens with probability 5. For any iteration k, we have that For fixed iteration k, we have that
CVaR CVaR, (*))
=c - VV 1, (01, CVaR, c.)) + CVaT, - (c' - (s1,
1,
Sch - -- lpv 1, (81, (8), - (R ,,,)),)))))r)r) -c- - VT,,,,,011,,''' ( ---
-c0 1,5e (81,
pa
ST-1 (V. - yxt (s), + (vx* Vi (81, VT
(13)
1 VHHAC by Lomma
C.2
where the first inequality holds by the fact that T² is greedy (Line 15 of Algorithm 1 and the last inequality holds by
(VaR,(((T** )²) sup -T-T--ERRRRN eh 1tt R)+1) c - ER at lt)lle R]+1 1ER
Therefore, it remains to bound the first term, which by simulation lemma C.3 can be further written
Va (
1, (81,c*)
( (0-
11
)
(( (
-Ept,p- p-
Th (s and Σ
E Pa
ra(s,, (r--n(shaan)
Σ h=1
Σ T (sh an
=
4=1
H1
E
12 (sn, and =
H.
E (s.a)rdf dey [s,
k po
h=1
h=1
11
E (frt, (5)())))
+3H
E
(x. (att) (ot [1h
(14)
18

---

Published as a conference paper at ICLR 2024
where the last inequality holds by the simulation Lemma E.5 for risk- RL and the fact that
1 0c S 2. where the last inequality holds by I|V Pk + llee S 2. We first consider term (i). By
Lemma E.4 and noting that the bonus term B% is (1), we have
Th ())
(s.a)rdd (ek)
min { a abb
E
(s.a)madh (otictt
x xx x .2
Am 1
A (at)2
E3 Esn ano())
110( (|)
--1
of xxuuca00
H-2
Σ
E
(ma))afftt ett
h+ XUCA)
11 2
<
(s.a)mdffffeh
(1, of/.0
k(at)}AA Ee a (n((
11 (s, a)l
+ 4
1=1
+ xuca)) h+7
+
A (at)2 BaND(LNNU(A)
1 (1))
of xFUUCDs
dA(a*)²
H12
ddA(a)) + +4X
Σ
(s.a)aaf (otictt
[1)
(15)
k
h=1
where the last inequality holds by k- Bospp (A)
1 al
kTr (BoxnuLasla (o)))))))
KE A (1 ++ x+)= sd
x
Similarly, for term (ii), we have that
H
E
(a.a)afft
[st a)]
(1)()
A EUMAA)
H-2
Σ
E
(1ob (s.a)
itt
RA (aU((A)) [(+t+1
424d
n-
h=1
Sv Act + k
Σ
E
(1 ())s
(16)
h=1
where the last step uses
FlHK
* S Ad log
8
Combining 13
14).
15
and
16
we obtain
(CVaR; CVaR, (B( (c)))))))))
K
dA(a*)2
K H-2
110% (3)s),)))ls (103(6.001l.. 1)
+ AP
2H d E
k=l h=1
19

---

Published as a conference paper at ICLR 2024
K
2-2
da(ah)2 + 4
E (s.a)adh ,oty
11 (s.
a)
1=1
h=1
<11²Ac
Ad
1.10
FlHk
E
(s.a) (.aa)akkk..l ok
|102 a)ls,,)))l=---
12.00
K
[
HK
2H
Log
1
log
dx1
8
where the last inequality holds by (Uehara et al.
2022 Lemma 18), i.e.,
K
Σ E
| a)l
$ dK log 1+ K
(s.))
dd
Therefore, conclude the proof.
Lemma C.2 (Almost Optimism at the Initial Distribution). Consider an episode k E [K] and set
Fi 8
|
x -0===(aa
-
FIHK )) =0= (+] log
F H
a
HP (P(A+ log
(17)
with probability 1 - 6, we have that
v 1, B (81, c*)
VTTP--o0s: c*)
)+) S A2
(18)
Proof. Similar to the proof of Lemma C.1
letting (s. P a) P% (-1s, a)ll, we con-
dition on the event that for all (k: h) E [
[H], the following inequalities hold
Esppt (A)
[1h a)) 27
S <( ane
[s)) s5
|| (0(s,))l
((I I)( (
From Lemmas E. and E.2 this event happens with probability 1 - Note that b/ (s,a) a) = f (s,a) = 0 for any (8, E S x A. Then, for any policy म, from the simulation Lemma C.3 we have that
1 L. (81,
- 11,,,,0(81,0 c()
H -
+
H
H
=E r,,
(o an)
Σ
(sh an) c1 =
Ege,pi
Σ
nu (3h, an)
h=1
h=1
h=1
11
(laa)dd
-
(19)
h=1
For any h + 1E E .2....,A H H-
1}, by Lemma E.3 and noting that [l. 2, we have that
(s' ('' (5t (s' a'))
<E, (m0))a
(1t a))::
V KA Es 1 [fhh (s', a(])"
+ 4 + =4kC*
Hence,
-E -B (stt"'''aa)) -VBh E. ((aa)aa( B4
|| (s. xxuccas
(20)
2,
where
-= * hc* s (A+ (og(
20

---

Published as a conference paper at ICLR 2024
Combining 119 and 20
further derive
V8a
Le (51,
Ví.p- c(s,,c")
H12
E
(1,0) (f
(S a)
V H2
H
Σ
E
(s (s
fr [
41
1-2
(s.a) of
(5) (
+ Σ
E
(o.a)aa
min a0110% a))ls>
2 + VII2A
Therefore, we conclude the proof.
Lemma C.3 (Simulation lemma for risk-sensitive RL). Given two episodic MDPs (H, P
(Ph (H))) and (H, = (Pahnemm:T), for any fixed E [0, and policy = {Th : x [0, H] + ((A)) we have that
H c) H
Vi.,,0($1,
(aa [fr((s
(21)
h=1
where (1(8,a) = |P 8 a) - Pr,-ls,, a)ll for any (h, E [H] x A
Proof. By definition, we derive that
V[..,((1,.)) VTT (81,)))
Eg Egr -er
V25 (2,,,o0,,ccr))) - (arnn)_----ppa ((
Vx 12
E BiinP((l EB (a
VT V2p,ols',c - 10 (5,
+ BewP(((le)a))
( - P( - (2,,,((,c-m1))
RB (es Ry By (1))))))
-V- c2p,ol''ccm) V ( (5', c- - c-n) + H B( (8)
H
S... SH
Σ (ooad
which concludes the proof.
D PROOFS FOR APPENDIX B
D.1 PROOF OF THEOREM B.2
In the following discussion we use 0% to denote T, (5/, a and (PrV) iv. a) to denote
or Patl V (ss' (8',i0 iv - -r)]
We also use Gr. denote the filtration generated by {(// o 2) ) (8/ (sh af).
U
First, note that we have the following concentration lemma:
Lemma D.I. For all h [H] t s [H/v], with probability 8/4, have
Htd
HdT:
(hri(sh P/.) - P h+ 1 (5/ iv, ab)
log
1h
vō
1=1
(AR)
21

---

Published as a conference paper at ICLR 2024
The proof is deferred to Appendix D.3 Let & denote the event in Lemma D.1
On the other hand,
further bound the difference between is, and (s, + a)) T whf (iv) follows:
Lemma D.2. For any policy conditioned on ε,, have for all S,0 S i s [H/ul,a A [H, t E [Ti]
that
(s, a) + (s, (tv) - (s, a) (PA (V (Ph vitt)) (s, iv, + iv,
where (s, in a)l 8 oh (s. ()
The proof of Lemma D.2 follows the same arguments in the proof of Jin et al. (2020) Lemma B.4] and thus is omitted here.
With Lemma D.2 we can prove that the estimated Q function Q" is optimistie:
Lemma D.3. Conditioned on event ε,, we have for all & E S,0 S < [H/o], [M] i e (7i)
that V (s, iv) s (s) where (s,ss sup, V (s. iv).
The proof is deferred to Appendix D.4
Combining Lemma D.2 and Lemma D.3 we can bound the regret of Algorithm as follows:
Lemma D.4. With probability at least 8/2, we have
T1
(
Σ Vi (s1, vi(
where: log² HdT: 26
The proof is deferred to Appendix D.5
Denote the event in Lemma D.4 by &g.
Lemma D.4 implies that by setting Ti Ô
we have conditioned on event & that u"
min V (11 (
(s1, E//2.
Let & denote arg (in V. ($1, hv). Then on the other hand, by setting T3 Ô (H²
[12logg 7 6²
with probability at least 5/2 have that for all & (Ti).
Vi (s1, - Vi (s1 S E//4.
Denote the above event by Eg and let ãे denote arg ming. Vi (1), Then conditioned on event Eg Ea, we have
V (51, - (i(s) VV, (s1, -V s v (S1, - ii( 4 78.
D.2 PROOF OF THROREM B.3
First, we show that Algorithm can achieve sublinear regret in the discretized MDP M. Let (m) i*) arg max fell. any 0S [H/v] CVaR,(R(m) in)). Note that from 4 have
CVaR = - 1,P (11,
This implies that
CVaR" CVaR, (R( stv))
22

---

Published as a conference paper at ICLR 2024
i'u u - T V V
1, (s1,
CVaR, (R(T,, + (i' - - 1, (31, -00
(iv- Vi
1, (31,
P-V- - Vi
CVaR, (R(x", {() + 1, (x
Vi .o ($1 (s1."²))
(22)
Suppose in k-thh iteration, CVaR-LSVI returns V 1e Be (8), for the initial budget i*v. Then from Theorem B.2
we know
V 1 (1,
V ix T 8
This implies that
i'v
V 1, 84
(51, 01, 1 - (s),
t V
1,
+
S k t 1,
(23)
where the last step is due to Theorem 5.1 On the other hand, from know
CVaR, v)) 2 th Vi (s,,
(24)
Plug Equation 23 and
24 into
22 we have
CVaR - -CVR, (R(T", x))) ST-
(VP,,0001, - V & (81, (01,
(V 1, ( (01,
V x ( i0) u))
6
Then, following the same arguments in the proof Theorem 4.1 we can obtain
Ke
CVaR - CVaR, x x)) S H6
Ad
Vlgg ((F18))
+ 6
(25)
Next we bridge CVaR, and CVaR, via Proposition B.I Note that from Proposition B.1 we have
K
CVaR CVaR, (R(T", u)) < CVaR - CVaR, ( ;²,,,,))))))) + KHv
(26)
Combining
25 and 26 we have
K
CVaR CVaR, Av)) S S . log ((F1/8) +
Ke K
Substituting the values of the parameters, we will obtain
K Σ CVaR, CVaR-(R(T** ,,))(()+,))))))) Se.
This implies that the uniformly mixed policy of {( (k) is coottmal. The total number of collected trajectories is KH ò 117 A3 log
23

---

Published as a conference paper at ICLR 2024
Now, we discuss the computational complexity. The MLE oracle is called KH times. For the rest of the computation, the cost is dominated by running CVaR-LSVI in Line 17 of Algorithm 3 In CVaR- LSVI, we compute (AA,)- 1 by the Sherman- Mortaanonn formula, then the computational complexity of CVaR-LSVI is dominated by Line 6 of Algorithm which requires O AT's time per step and leads to total computational complexity of O AH for each call of CVaR-LSVI. Note that CVaR-
LSVI is called totally KH times in Algorithm 3 and thus the total computation cost of Algorithm
KR [
2 log 1
Ô
16611
D.3 PROOF OF LEMMA
The proof largely follows the proof of Jin al. (020)[Lemmi B.3]. We first bound wf (iv). Note that we have for any vector e E IRd where d == d(1 + [1/u]) that
10 (iv) S
0. (TAA) -1 -00%
T (AA) (1
Σ ph
10
.H
S <Hllool
Σ (oh)
(A())-
Note that with Lemma E.6 we have E/1l (%)) (AA) for u E Rd
S d and therefore we can obtain that
td X
Twt(iii) s H
H|llll
which implies that [lo (fv) < /
To utilize Lemma E.7 we further need to bound the covering number of the class of estimated value
functions. Fix E H.. it can be observed that all (s)))) where E [7i] belongs to the following function class V parametrized by w and A:
{v ((, iv) = min Clipp-H.HI ( (s,)) - (a(s, a) - |1 (s, a) a))l
where [[w(i))] 5 H X and |||| S /²/A. Then for any Vi (parametrized by w1, A1) and V/2 (parametrized by w2, A2), we know
sup VV iv) V2(8, iv) SES,OSiS[H/v]
1h (s,a)(ur((v) wz((t)) - (3,((,
sup NES.GEADSIS
sup [0
(wi(iv) - (2(to)) + sup
|
|
sup 03/5
aan (iv) w2(iv)]l + VIA A2
This indicates that the covering number of V with respect to lx norm can be upper bounded by the covering number of and A. More specifically, let (c) denote the covering number of y with
24

---

Published as a conference paper at ICLR 2024
respect to &o norm, then we have
log)(c)) so aaa+
log
HTid c
0
Hd ui
log
HTid cxu
Substituting the above bound into Lemma E.7
concludes the proof.
D.4 PROOF OF LEMMA D.3
The proof is conducted via induction. For the base case, when h = H + 1, we have V (8, V #r41 (5, iv) = iv for all E S and S S [H/u].
Then suppose have V (s)
V (s, for all S and 0 S [H/u]. For any S,a E A and 0 S i < [H/v]. if Q (s, iv, -H, then iv, S (s, naturally holds. Otherwise, from Lemma D.2 we know
Q% (s, iv, - (s, a) v (s) a) + (o)(s, wf(()) - 10 - (s, -0,
- Pn Vh+1 - - (s, a) s.
Therefore we have Q (s, a) S Q, is, for all s E S,a E A and 0 < i [H/u]. which leads to V (s, I iv) for all S and S S [H/v] as well. This concludes our proof.
D.5 PROOF OF LEMMA D.4
First note that from Lemma D.3 we have (11,41)) 2 V (81 for all (Ti). This indicates that conditioned on E
Vi (s, (s) ( Σ Vi ( (i) s
(27)
Fix t E [Ti] and then we know
V (81, - (s1, = री (si, - (s,
- ((n, af) s 0. Otherwise, we have कf (f,, Φ (81, fr af) < Φ af, + (st. at) - (((tv))) Bl
(s), hu, af) H, then we know (sf,
Then with Lemma D.2 we know
o (st, of) Q'1 (1,, < (Pn ( - -v)) (st of) + 23
(28)
Let i denote
- - - h-1 The and let ((C)) M 17, denote the following random variable:
{
0. if there exists some N' < h.t. Tn ($
H, va
ch {
(Pn (V=+ (iati-vi+jj vi++1) (s), K.. ah) - (V (sh+1:
u)) otherwise.
It can be easily observed that G/ E Gen+1 and E(Gh = 0. which means that {(A)) 1 is martingale with respect to ). Then when (sf /10, a}) + H. Equation 28
equivalent to
की (sf, af) (11, fv af) V (5) dbu) V2 k2) + ch + 231 1l
Repeat such expansion till step he such that Qh (sh,, th, u, afh) = H or he = + 1. Then we have
H
h
h
H
V (8 - (i <
Σ
ch
+ 23
(all S
Σ ch + 23
1=1
-=1
h=1
4=1
(29)
25

---

Published as a conference paper at ICLR 2024
Therefore combining
28 and 22
we know
21
Σ
Vi (s),
Sh 23
1
(30)
For the first term of the RHS of (30). from Azuma-Hoeflding's inequality, have with probability at least 1 - -0/2 that
ch S 2H T.H
For the second term, utilize the elliptical potential lemma (Lemma E.8 in Appendix which yields
T WE
H ΣΣ
2dT 7
Ti
VV
t= ==1
t=1 h=1
Plug the above two inequalities into (30) leads to the result in Lemma D.4
E AUXILIARY LEMMAS
Lemma E.1 (MLE guarantees), For any fixed kh, E [H] x [K], with probability at least 1 - 6, we have that
[g-[ +0.5mk) ), (A) (-ss)) P1 a) S s. 5 : log((F1/6)
(31)
k
Using union bound, direct corollary is: with probability at least - 5 the following holds for all HH E [K]
E Ee 50.5%% ).- a-) (-I (-s,,, a) S 0.5c* s²== == log([F[HH]]
(32)
k
Lemma E.2 (Concentration of the bonus term). Set x ((dlog((H))7)0) at the k-th episode. Define
Eppe K o0 a) ( (s,
XII En Σ
a(s,)) (o, X*I.
a,aEDs
With probability 1 - 8. we have for any k Nt, ( d
[ a) (1 = (I0((s, (
Lemma E.3 (tee-teep back inequality for the learned model). Let { S 10 +
A A(A)) denote any policy the augmented state. Fix initial budget E [0, Take any g: S x AH I such that || & B. We condition on the event where the MLE guarantee 32
Banpt (A)) (s, 5*
holds for any h E [H]. For h = 1, we have that
E
(oaamata lole) a)] S V A.E.E an (A)
For any h + E (2, ... HJ and policy n, we have that
E
(s',0') (o
lo(s',a')]
SB
10 ()) bopa (ma))oftaa))
KA Bu (rccs
B +B2Ck
(33)
kE s (A) where E "2XXU(A),
1
26

---

Published as a conference paper at ICLR 2024
Proof. For h 1, we have that
(als) (}(s)((a)
(f 1,8E
()( sp
max s,a
B Bampt (L
A E an (s.
where we use the fact that dj = p.. Recall that (s( = 2x di (s) is the (expected) oceu- pancy of any s E S in dataset D/ Let ((,e) S x A H A(0 1]) denote the distribution of the remaining budget at timestep á conditioned on any (s.a) E S x A when rolling policy π in an MDP with transition kernel P and the initial budget C1. For any h E {1,-.. .. -1,, we have that
h.P
=B (aalaa mi
E
Pt(len))) h. ( (o('',
E
ph(s,a) [s (i(('))
=E
(sa) h,BL
n. (1s.))))) ( d')
<R. (sa)) h,Bl
( 1155 pe xxoca).33 x
1/ (h('') (n hi
"dd''
where the last inequality is because of CS inequality. For any (s, E S x A, we have that
1/ ( (s') co (waoa//cccccooooooommmaaaac l9(s' d')s ho h,
Ph (s')TE
(2)) T x²1]
Th( hink (e )'dd'
[V
27 coww (www ( a'jlds) )
<k Bampph
(i(s') 2h a)
(
+ +B>x
where we use the assumption
oney ( < B,
(1o0)) he
and
(s'(s'') S Vd.
for any y S + [0, 1]. Note that (s')
(3, a) PL (s'13, a). Further, we derive that
)
27
k. (E
Ph (s (s]
( (18.)))) (wa. 10 ( h,
+ +BAxdd
<k Egspp
BB h.pk (taa 1ol + BB
<k Essppt Essppt (A))) (1 |a B2
<kA . (F
27

---

Published as a conference paper at ICLR 2024
Note that & ~ ph: ~ U(A), (1)3,ā is equivalent to s' 1h+1 Therefore,
E
lg(s',
(
|
<B
10% a)ll xucuaaa
Σ
(s')) (s'
Eerra
9(s a')ds'
(8.0)
b xU(A)
<B, (ss))mafte)) k.Pk
(8, a>]l
kA Be (-) x01a).3
which concludes the proof.
Lemma E.4 (One-step back inequality for the true model). Let {
S x [0, H
hetm denote any policy on the augmented state. Fix an initial budget e₁ E [0, 1]. Take any g A R such that lIglooo S B. Then for h= 1, we have that
E
(a.))at (g(s, a)) - V A.E.rpt O0
For h + 1 .., HJ. we have that
V VKA ar Xt E a lgl's (o(s',a') d')] s E (f ( 02
Proof. For h = 1, we have that
di (1(s) (s()(((a)
E (e.a))aff [o(s, (0
E Banpt (0100s))) S VA Eampt (A) (A) (s)(s,
(m.C) Let wh (x,01) = wh,p- denote the distribution of the remaining budget c at timestep h conditioned
on any (s,a) E S x A when rolling policy и in the (true) environment and the initial budget c₁. For + EE ... HJ. by CS inequality, we derive that
E (0' ( 1000 (ss''aa')]
(s,a)aaf
PN (-10,a) E (1.9)) (T ( eoaf(t
lg(s', do)s',d')]
10% (1)(5))) o /1 / cnu
<E
SE (s.a)aa(tio)
For any (s,a) ESS x A, we obtain that
118 1/ (5')B cove (m.e1) n y lo(s' a d')lds'
Fchio.
(A(5E oree ((rc1)) ( lo(s' a')dd''
(B (0)())) + X²1}
Vi ooagfte (a a''d'''
<KE st~ P. (.8) Bew.ograd (8', x
SkA Ey-no a - (s', a')] + dB
where the last inequality holds by the fact that (3, â) p s' ~ (5, â) is equivalent to s' phtz and importance sampling. Therefore, we conclude the proof.
Lemma E.5 (Simulation lemma for risk- RL). Let M and M be MDPs with the same state and action spaces, but they have different reward and transition fransition,uucctions, i.e. (Fh, Ph Ph) and
28

---

Published as a conference paper at ICLR 2024
(rh, Pulh=r respectively. Consider any policy {mh:: : A(A))ne(m) denote (V, 1H and (V Jh=1 be the value functions. Then we have that
h hm
V (11) - (s1 E R (Fa(s,a) rn(s,a) + (0000+((PP((..p (P
P,(-1s, ((+(()))
Equivalently, we have that
(11) (T((s)=
Σ B(sa))dR (m((s))) + (aaaa)))(((((sss. ( - V V (()))))))
where VH1 V M 0 (as the episode ends at H).
(s. a) are the occupancy measures any (s, E S A at timestep h E [H] when executing policy in M and M, respectively. By definition, have that V (8)) (s1)
Proof. Recall that (s, a) and d", "7,7((s
(1 a)
- (s(), Σ (PP((ools)) a) (6)) - -((())))))
a
f2(s, (s) + (P((11,a), p2 - (2(()) + (P1(11, (((())))((()))))))))))))))))))) a), (), v2(1)] (n(8,a) (s) + (Pa(11) Pa(l)s, vit+(())
= (((
1,
H
E (sssa)ad
Equivalently, we have that
VTT (1,,7((1) (81
- 13(() - (Pi(-1s.a) -A(())))A()))))) -P(-s, V= (), -B(x fi((s - rr(ss + (P((-)s,)) De (T)(()) -
H
Σ EssayyaR ()) (s, + (Pr(-1s, - - Da (
h=1
which concludes the proof.
Lemma E.6. Let A = A E/=1 (0') where 05 E RR, > 0, d > 0, then we have
To))~ dd
Proof. Please refer to (Jin et al. 2020 Lemma D.1).
Lemma E.7. Let { be stochastic process on the space (S, (iv) with corresponding
filtration { Let (ō, - be an I valued stochastic process where θ, Gj-1, and 11 S 1. Let A₁ XI + Σド 0 Then for any 5 0, with probability at least 1 5, for all 0. and any V E V that sup, [V(x) H, we have:
t t+ A + log
No 8
St2
Σ
< 2
log
+
X
A
where No is the e-covering number V with respect to the -nom sup, -Vxx)-V((C V'(x))
Proof. Please refer (Jin et al. 2020 Lemma D.4).
29

---

Published as a conference paper at ICLR 2024
Lemma E.8. Suppose क, E I and |,²||| I+ ++E= o o. Then we have
1 for all t 0. For any 2 0, define A.
dee(Ae) det(Au)
1 - 2 log
==1
Proof. Please refer to (Jin et al.
2020
Lemma D.2).
30


Reviews:
[{"review_id": "CMpoQBpBrS", "reviewer": "Reviewer_htXD", "summary": "This paper studies risk-sensitive RL in in low-rank MDPs with nonlinear function approximation, where the goals is to maximize the Conditional Value at Risk (CVaR). The authors proposed ELA (REprensentation Learning for CVAR) as shown in Algorithm 1, which contains a MLE oracle and uses UCB-based bonus to do exploration. They proved that the sample complexity of ELA is $\\tilde{O}(1/\\epsilon^2)$ The authors then proposed ELLA (REprensentation Learning with LSVI for CVAR) algorithm, which leverages least-squares value iteration to improve computationally efficiency.", "questions": "1. In Algorithm 1, for the part of collecting two transition tuples, could you explain why using different policies to sample the two actions.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The problem of study is interesting, i.e., risk-sensitive RL in in low-rank MDPs.\n2. The presentation is clear and easy to understand.\n3. Results seem reasonable and novel to me.", "weaknesses": "1. The proposed and improved algorithms are computationally inefficient in the sense that they still require to call MLE oracles.", "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": "W6S0lNpwBn", "reviewer": "Reviewer_i64s", "summary": "In this work, the authors propose the Representation Learning for CVaR (ELA) algorithm for maximizing the Conditional Value at Risk (CVaR) in low rank Markov decision processes (MDPs). The authors then propose a modification of the ELA algorithm, called ELLA, that improves upon the computational complexity of the former. The authors then provide probably approximate correct (PAC) guarantees for both ELA and ELLA.", "questions": "Aside from the questions mentioned in the weaknesses section, I also want to ask where the novelty in this work lies. This work seems like it combines the setting and results of Wang et al, 2023 [1] and Uehara et al, 2021 [2]. What, if anything, needs to change? Does your results nicely follow from adapting the REP-UCB algorithm Uehara et al, 2021 [2] with the CVaR bonus of Wang et al, 2023 [1]? \n\nAlso, if you consider time-homogenous transitions as was done in Uehara et al, 2021[2] do you match their dependency on $H$? Also do you think your dependence on $d$ and $H$ are tight? If yes, then why? If no, then where to do think this looseness arises from and how can it be improved?\n\n[1] Wang, Kaiwen, Nathan Kallus, and Wen Sun. \"Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR.\" arXiv preprint arXiv:2302.03201 (2023).\n\n[2] Uehara, Masatoshi, Xuezhou Zhang, and Wen Sun. \"Representation learning for online and offline rl in low-rank mdps.\" arXiv preprint arXiv:2110.04652 (2021).", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The authors do a good job in introducing both risk sensitive RL and the CVaR objective in Low Rank MDPs. The main result for the ELA algorithm and its ensuing discussion are also well-written. Furthermore the authors partially address one the problems posed in Wang et al, 2023 [1] on whether their minimax CVaR guarantees for tabular MDPs can be extended to low rank MDPs. \n\nAlso the introduction and related works do a nice job of setting up the problem and informing the reader on the current state of CVaR and risk-sensitive RL.", "weaknesses": "The main weakness of this work lies in the tightness of their guarantees. While the authors provide upper bounds for their ELA and ELLA algorithms, they do not provide lower bounds for CVaR in low rank MDPs. Therefore it is hard to see whether the bound the authors propose is reasonable (see questions for further details).\n\nAnother weakness is in the writing of section 4.1. This is a very weird policy to me. First the agent follows the policy to state $s_h$ then takes a uniform action $a_h \\sim U(\\mathcal{A})$ and receives the next state $s_{h-1} \\sim P_h(\\cdot | s_h,a_h)$. If the agent is taking uniform actions in step $h$ then how is it following policy $\\pi_k$. Wasn't $s_h$ the state the resulted in taking a uniform action $a_{h-1}$ in the previous state $s_h$? Anyways maybe I missed something here but this seems very weird?", "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": "6CuYwCcVbR", "reviewer": "Reviewer_yZ3N", "summary": "This paper studies risk-sensitive Reinforcement Learning (RL) in the context of low-rank Markov Decision Processes (MDPs), employing the Conditional Value at Risk (CVaR) risk metric. The proposed algorithm bears resemblance to value iteration techniques, incorporating exploration bonuses based on the Upper Confidence Bound (UCB) principle, a well-established concept within the field of RL. Furthermore, the authors introduce a discretized variant of the least-squares value iteration approach and demonstrate its capacity to approach near-optimal policy solutions within a polynomial computational time framework, given access to a Maximum Likelihood Estimation (MLE) oracle. This novel contribution enhances the body of knowledge in this area of research, delivering valuable insights to the academic community.", "questions": "Please see the above section and correct me if I misunderstood some results. I am happy to increase my score if that is the case.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "(+) The paper is generally well-written and the technical exposition is overall sound.  \n\n(+) I personally find the computationally efficient algorithm a nice addition to the paper. I do not see any citations in Section 5 so I assume that these are novel contributions of the authors.", "weaknesses": "(-) In Section 4.1, it is mentioned that the algorithm requires two sets of trajectories. Is it true that a *simulator is required* to obtain these two sets? By simulator, I meant the ability to draw samples from the *true* transition probability $P^*_h$. If this is indeed required, it is a major assumption that the authors fail to disclose in the abstract or in a formal statement. I strongly encourage the authors to highlight this fact.\n\n(-) Again, suppose my understanding of the above is correct. In that case, the result becomes fairly trivial: combining the realizability assumptions with a finite model class (assumption 3.2) with access to a simulator, it is easy to see that given enough samples, any algorithm is no-regret. Nevertheless, there is still credit in proving finite-sample regret bounds in Theorem 4.1.\n\n(-) The claim that this is the first provably efficient CVaR RL algorithm is incorrect. There have been regret bounds for CVaR RL in function approximation settings in the literature. \n\n(-) I also encourage the author to at least discuss the difference between dynamic and static CVaR, as this has non-trivial implications in algorithm design and theoretical analysis.", "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": "ngMoSPrqU6", "reviewer": "Reviewer_hVSJ", "summary": "This paper study risk-sensitive Reinforcement Learning under low-rank MDPs, where the transitions of MDPs admit a low-rank decomposition into two unknown low-dimension embedding functions and the goal is to maximize the conditional value at risk (CVaR) with certain risk $\\tau$. This paper first propose an efficient upper confidence bound type algorithm and then provide regret bound $\\tilde{\\mathcal{O}}(\\frac{H^7A^2d^4}{\\tau^2\\epsilon^2})$. In addition, this paper disigns a computational efficient LSVI algorithm for planning.", "questions": "Could the authors also provide some motivation examples of CVaR RL under low-rank MDPs? It will help the readers to understand the significance of this setting and how this formulation is related to real-world applications.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper propose an agorithm with theoretical regret bound, which is new for CVaR RL under low-rank MDPs.\n\n2. This paper propose an computational efficient algorithm for planning.\n\n3. The presentation of this paper is easy to follow and clear notations tables are provided.", "weaknesses": "1. My main concern is that the algorithm 1 is quite close to [1]. It seems that algorithm 1 is just an application of REP-UCB in Augmented MDPs. The analysis of regret bound is also similar to [1], with only difference to convert CVaR into value function (as Eq. (13) in Page 17), which makes the result not so surprising and significant. It is likely that I miss some novel analysis techniques, so please bring it out and I think it is also important to stress the novelty in the paper.\n\n2. The authors claim the worse dependency of regret bound on $H^7$ is due to the non-stationary transitions in Page 7. I want to point out it may be wrong. Another previous work considers regular low-rank MDPs with finite horizons and time-dependent transition kernels [2], which is the same as this paper, even has better dependence on $H^3$. It is likely that the worse dependency on $H$ of this paper is due that [1,2] assume that the accumulative discounted reward is in $[0,1]$ and this paper only assumes $[0,H]$. I guess that applying similar assumptions and techniques to clip value functions in [2], the regret bound may acheive the same dependence on $H^3$.\n\n3. Based on the two points above, I think the authors can try to enhence this paper by buliding a lower bound of CVaR RL under low-rank MDPs with better dependence on $\\tau$, or try to improve the algorithm to better regret bound.\n\n[1] Masatoshi Uehara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline RL in low-rank MDPs. In International Conference on Learning Representations, 2022\n\n[2] Cheng, Y., Huang, R., Liang, Y., & Yang, J. Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPs. In The Eleventh International Conference on Learning Representations, 2023.", "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)