RA-PbRL: Provably Efficient Risk-Aware Preference-Based Reinforcement Learning
Authors: Yujie Zhao
Jose Efraim Aguilar Escamilla
Weyl Lu
Huazheng Wang
Venue: NeurIPS 2024 poster (2024)
Keywords: Reinforcement Learning Human Feedback
Risk-aware Reinforcement Learning
Primary area: reinforcement_learning

Abstract: Reinforcement Learning from Human Feedback (RLHF) has recently surged in popularity, particularly for aligning large language models and other AI systems with human intentions. At its core, RLHF can be viewed as a specialized instance of Preference-based Reinforcement Learning (PbRL), where the preferences specifically originate from human judgments rather than arbitrary evaluators. Despite this connection, most existing approaches in both RLHF and PbRL primarily focus on optimizing a mean reward objective, neglecting scenarios that necessitate risk-awareness, such as AI safety, healthcare, and autonomous driving. These scenarios often operate under a one-episode-reward setting, which makes conventional risk-sensitive objectives inapplicable. To address this, we explore and prove the applicability of two risk-aware objectives to PbRL : nested and static quantile risk objectives. We also introduce Risk-AwarePbRL (RA-PbRL), an algorithm designed to optimize both nested and static objectives. Additionally, we provide a theoretical analysis of the regret upper bounds, demonstrating that they are sublinear with respect to the number of episodes, and present empirical results to support our findings. Our code is available in https://github.com/aguilarjose11/PbRLNeurips.

RA-PbRL: Provably Efficient Risk-Aware Preference-Based Reinforcement Learning
Yujie Zhao', Jose Efraim Aguilar Escamill', Weyl Lu', Huazheng Wang"
University of California, San Diego, Oregon State University, 3 Uniiversity of California, Davis yu22850ucsd. edu, aguijose@oregonstate. edu,
adslu@ucdavis. edu, huazheng.. wangdoregonstate.eduu
Abstract
Reinforcement Learning from Human Feedback (RLHF) has recently surged in popularity, particularly for aligning large language models and other Al sys- tems with human intentions. At its core, RLHF can be viewed as a special- ized instance of Preference-bere based Reinforcement Learning (PbRL), where the preferences specifically originate from human judgments rather than arbitrary evaluators. Despite this connection, most existing approaches in both RLHF and PbRL primarily focus on optimizing a mean reward objective, neglecting scenarios that necessitate risk-awareness, such as Al safety, healthcare, and au- tonomous driving. These scenarios often operate under a one-episode-reward setting, which makes conventional risk-sensitive objectives inapplicable. To ad- dress this, we explore and prove the applicability of two risk-aware objectives to PbRL: nested and static quantile risk objectives. We also introduce Risk-Aware- PbRL (RA-PbRL), an algorithm designed to optimize both nested and static objec- tives. Additionally, we provide theoretical analysis of the regret upper bounds, demonstrating that they are sublinear with respect to the number episodes, and present empirical results support findings. Our code is available in cttiub..oomm/uuuuuu
INTRODUCTION
fundamental framework for sequential decision-making, enabling intelligent agents interact with and learn from unknown environments. This framework utilizes reward signal to guide the selection of policies, where optimal policies maximize this signal. RL has demonstrated state-of-the-art performance in various domains, including clinical trials [Coronato et al. 2020], gaming [Silver et al. 2017]. and autonomous driving [Basu al. 2017]
Reinforcement Learning (RL) [Russell and Norvig 2010
Despite its performance, significant limitation of the standard RL paradigm is the selection of state-action reward function. In many real-world scenarios, constructing explicit reward function often complex or unfeasible task. As compelling alternative, Preference-bare
Reinforcement
Learning (PbRL) [Busa-Fekete et al.) 2014 Wirth et al. 2016] addresses this challenge by deviating from traditional quantifiable rewards for each step. Instead, PbRL employs binary preference feedback on trajectory pairs generated by two policies, which can be provided directly by human subjects. This method is increasingly recognized as more intuitive and direct approach in fields involving human interaction and assessment, such as autonomous driving [Basu et al. 2017). healthcare [Coronato) ctt al. 2020]. and language models [ai et al. 2022] ,A specialized and increasingly popular variant of PbRL is Reinforeement Learning from Human Feedback (RLHF) et al. [2022]. which has garnered considerable attention for aligning Al systems with human intentions particularly in the domain of large-scale language models.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Previous approaches to PbRL Xu et al. 2020a Coronato et al. 2020 Xu et al. 20206 Chen et al. 2022 Zhan al.] [023] mainly aim to maximize the mean reward or utility, which is resk-neutral. However, there is growing need for risk-aware strategies in various fields where PbRL. has shown empirical success. For example, in autonomous driving, PhRL. reduces the computational burden by skipping the need to calculate reward signals for every state-action pair [Chen et al. 2022]. Despite this improvement, the nature of the problem makes dangerous actions costly. Thus, such senk-sensttive problem settings require risk awareness to ensure safety.
RiskeAware PbRL also has implications for fields like generative AI [OpenAl 2023 Chen al. 2023], where harmful content generation remains a challenge for fine-tuning. In this scenario, a large language model (LLM) is often fine-tuned with user feedback by generating two prompt responses, A and B. Many approaches using RLHF [Ouyang et al. 2022] consider human feedback to penalize harmful content generation. Unfortunately, current approaches only minimize the average harmfulness of response. This can be a challenge when responses are only harmful to minority of users. Risk-aware PbRL, tackles this challenge by directly aiming to decrease the harmfulness directly, rather than indirectly as with human feedback fine-tuning.
Despite substantial evidence highlighting the importance of risk awareness in PbRL, significant gap persists in the theoretical analysis and formal substantiation of risk-aware PbRL approaches. This deficiency has spurred us to develop risk aware measures and their theoretical analysis within PbRL. In standard RL, a variety of risk-aware measures have been explored, including general family of risk-aware utility functions (Fei al. 2020]. iterated (nested) Conditional Value Risk (CVaR) (Du et al. 2022), and risk-sensitive with quantile function form [Bastani et al. 2022]. In general, these measures can be categorized into two types: nested or static. Nested measures [Fei et al.) 2020. Du
et al.] 2022 utilize MDPs to ensure risk sensitivity of the value iteration at each step under the current state, resulting in a more conservative approach. In contrast, static risk-aware measures Bastani et al. 2022 analyze the risk sensitivity of the whole trajectory's 's reward distribution. In developing and introducing risk-aware objectives PbRL, we have encountered the following technical challenges in algorithm design and theoretical analysis:
Rewards are defined over trajectories preference In PbRL, the reward function depends on the preference between two trajectories generated by the agent. We refer to this difference in how the reward function is computed as the one-episode-feedbal objectives of standard RL like Du et al. [2022] and Fei et al. [2020] become unmeasurable since they depend on the state-action reward.
characteristic. Consequently, the risk-aware
Trajectory embedding reward assumption When computing the trajectory reward, it is assumed that an embedding mapping exists. By using the trajectory embedding along with some other vector embedding pointing towards high-rewarding trajectories, the reward computed with a dot product. Unfortunately, the embedding mapping may not be linear. This means that the embedded trajectory vectors may not follow the Markovian assumption, making the embeddings historr-deeenndent.
Loss of linearity of Bellman function When using a quantile function to transform a risk-neutral PbRL algorithm into risk-aware algorithm, the Bellman equation used to solve the problem becomes non-linear. This change to the bellman equation disrupts calculations on regret, making nistanl PbRL inapplicable. This is primarily due the additional parameter a, which modifies the underlying distribution.
In this paper, we address these challenges by studying the feasibility of risk-aware objectives in PbRL. We propose a provably efficient algorithm, Mlis--Awar-PPRL(RRA. (RAPPRA) with theoretical and empirical results on its performance and risk- Our summary of contributions is as follows:
1. We analyze the feasibility of several risk-aware measures in PbRL settings and prove that in the one-episode-reward setting, nested and static quantile risk-aware objectives applicable since they can be solved and computed uniquely in a given PbRL MDP.
2. We expand the state space in our formulation of a PbRL MDP and modify value itera- tion to address its cestory-dependen characteristies from the one-episode setting. These modifications enable us to use techniques like DPP to search for the optimal policy.
3. We develop a provably efficient (both computationally and statistically) algorithm, RA-PbRI. for nested and static quantile risk-aware objectives. To the best of our knowledge, are the

---

first to formulate and analyze the finite time regret guarantee for a risk-aware algorithm with Mon-Markovian reward models for both nested and static awske objectives. Moreover, we construct hard-to-learn instance for RA-PbRI. to establish regret lower bound.
2 Related Work
2.1 Preference-based Feedback Reinforcement Learning
The incorporation of human preferences in RL, such as Jain et al. 2013). has been a subject of study for over decade. This approach has proved to be successful and has been widely used in various applications, including language model training [Ouyang et al. 2022]. clinical trials [Coronato) al. 2020]. gaming [Silver al. 2017). and autonomous driving [asu al., 2017). PbRL can be categorized into three distinct types Wirth et al. [2017]: action preference, policy preference, and trajectory preference. Among these, trajectory preference is identified as the most general and widely studied form of preference -ased feedback, as evidenced by the rich literature on the topic Chen al. 2022]. Xu et al. [2020a]. Wu and Sun (2023). As noted in our introduction, previous theoretical explorations on PbRL have predominantly aimed at achieving higher average rewards, which encompasses nestall PbRL. We distinguish our work by taking the novel approach of formalizing the risk-aware PbRL problem.
2.2 Risk-aware Reinforcement Learning
In recent years, research risk-aware RL has proposed various risk measures. Works such as Fei ct al. 2020). Shen et al. 22014) Briksson and Dimitrakakis [019]] integrate RL with general family
of risk-aware utility functions or the exponential utility criterion. Accordingly, studies like Bastani
ct al. [2022]. Wu and Xu [023 delve into the CVaR measure for the whole trajectory's 's reward distribution standard RL. Further, Du et al. [2022) propose ICVaR-RL, a nested risk- aware RL formulation that addresses both regret minimization and best policy identification. Additionally, the work of Chen al. (2023) presents an advancement in the form of nested CVaR measure within the framework of RLHE. The limitation of this work lies in the selection of a random reference trajectory for comparison, causing an unavoidable linear strong nested CVVaR regret. Consequently, we are left with only preference equation from which we are unable to compute the state-action reward function for each step.
Practical and relevant trajectory or state-action embeddings are described in works such as [Pacchiano al., 202T]. Therefore, the one-episode-rewate might not even be sun-decomposable (the trajectory embedding details can be seen in sec 3.1). Compared to previous work, we use non-Markovian reward models that do not require estimating the reward each step and explore both nested and static rask- objectives, aiming to provide more general method.
3 Problem Set-up and Preliminary Analysis
3.1 PbRL MDP
We first define a modification of the classical Markov Decision Process (MDP) to account for risk: Risk Aware Preference-Based MDP (RA-PB-MDP). The standard MDP is described tuple, M(S,A, rē , H). where S and A represent finite state and action spaces, and H denotes the length of episodes. Additionally, let S == |S] and A == |A| denote the cardinalities of the state and action spaces, respectively. P x A - P(S) the transition kernel, where (2))) denotes the space of probability measures on space X. A trajectory is sequence
En Z
Zp
where
Z (S x A)h-1 x S.
Intuitively, a trajectory encapsulates the interactions between an agent and the environment M up to step h. In contrast to the standard RL setting, where the reward function (sh, ax) specifies the reward at each step h, a significant distinction in the PbRL MDP framework is that the reward function r* is defined (E() (S M) x S [0, 1]. denoting the reward of the entire trajectory.
3

---

Reward model for the entire trajectory. For any trajectory εx, we assume the existence of trajectory embedding mapping @ Zn - didrr and the reward of the entire trajectory is defined as the function: r5(En) == (Ø(En)) w²). Here, dimg denotes the trajectory embedding dimension. Finally, we denote ((EH) (01 (EH). (.dt)).)....m..((( (EH)).
Assumption 3.1. We assume that for all trajectories Eи and for all d E { dimr), (( )ll E {0) U [6, B3] where b, B > 0 are known. ||w; S Pw and pw is known as well.
Remark 3.2. We assume the map á is known to the learner. The sum of the state-action reward used in Chen al. [2023] is one case of such map, where o(En) = - H - Therefore, for all de E fl...., dimr). }. ([ || E
I (sh: an) and dimr S A.
Remark 3.3. Assumption 3.1 implies that there is a gap between zero and some positive number b in the absolute values of components of trajectory embeddings. This is evident for finite-step discrete action spaces, where we can enumerate all trajectory embeddings to find the smallest non-zero component, satisfying most application scenarios.
At each iteration & E [ the agent selects two policies under a deterministic policy framework, T1.A and k2 which generate two (randomized) trajectories & and 5 In PbRL, unlike standard RL where the agent receives rewards every step. the agent can only obtain the preference og between two trajectories (4//² 22.)) ). -2x))
By making query, we obtain preference feedback O₁ E {0, } that is sampled from a Bernoulli distribution:
ok ~ Ber (o (st(( - (2
where a IR + 10, 1] is a monotonically increasing link function. We assume a is known like the popular Bradley-Terry model [Hunter, 2004), wherein is represented by the logistic function. It is known that we can not estimate the trajectory reward without a known σ. Also, we assume a is Lipschitz continuous and is its Lipschitz coefficient.
History dependent policy. Since the algorithm can only observe the reward for an entire episode until the end, it cannot make decisions based solely the current state. The agent cannot observe the individual reward rn (s, a) and thus cannot compute the target value at each step. To circumvent this challenge, the algorithm should take action according dependent policy IT = (Th ) is defined as a sequence of mappings tha 2, > A. providing the agent with guidance to select an action, given a trajectory &n E 2n, at time step h. For notation convenience, let II denote the set of all history-dependent deterministic policies.
diistor--deeender policy. A history-
3.2 Risk Measure
Because in PbRL we can only estimate the reward for the entire trajectory, the risk measure selected for PbRL must rely solely on the reward of the entire trajectory. That is, two trajectories with the same trajectory reward should contribute equally to the risk measure, even if their potential rewards Unlike|Chen
at each step are different. Unlike Chen et al.] (2023) that decomposes the reward at each step (where the solution is likely not unique) and then calculates the risk measure, this requirement ensures that the risk measure consistently and holistically reflects the underlying preference. We refer to risk measures that suitable for PbRL problems as PbRL-risk-measurer Here, we introduce two different risk-measures: nested and static quantile risk-aware measures, which are appropriate for PbRL-MDPs.
We first introduce the definition of quantile function and risk-awan objective. The quantile function of random variable X is Fx (7) inf (x E IR (x(x)) 2 7). We assume Fx is strietly monotone, so it is invertible and we have (T) = Fx (7). The aiske objective is given by the Riemann- Stieljes integral:
4(x) = [' (TG())(T)
where X is the random variable encoding the value of MDP, and G is a weighting function over the quantiles. This class captures a broad range of useful objectives, including the popular CVaR objective [Bastani et al. 2022).

---

Remark 3.4. (a-CVaR objective) Specifically, in a- VaR,
1 if a, G(r) if 2 a.
and ((X) becomes
1
((X) =
Jo Fx (T)
Assumption 3.5. G is Li-Liscchitz continuous for some La E Rso. and G(0) 0, G1)
For example, for the a-CVaR objective, we have LG = 1/a..
There are two prevalent approaches to Bark--wwrre-MDDPP nested (or iterated) (such as Iterated CVaR (ICVAR) [Du et al., 2022] and Risk-Sensitive Value Iteration (RSVI) [Fei al.) 2020)), )) and static (referenced in [Bastani et al. 2022 Wu and Xu 2023). MDPs characterized by an iterated risk-aware objective facilitate value function and uphold Bellman- taap recursion.
For standard RL's MDP, the nested quantile risk-aware measure can be elucidated in Bellman equation type as follows:
Nested
(x) (s, a) + + (Vi+1 (s'), (s))s)))
(s) QT (s, (s))))
(3)
(s) =0, E
Here r (s. a) denotes the decomposed state-action reward in step h.
For the PbRL-MDP setting M(S,A, rē. P', H) the state-action's reward might be calculated the reward of the entire trajectory might be decomposed. Therefore, the policy should be history-dependent. We rewrite the nested quantile objective's Bellman equation with the embedded trajectory reward follows:
o (Vizi (s' o (Eh, a)), ~ -ss(s.)), (EN) Q% (Eh, (T(E)))
(En a)
VH(En) (EH))
For any PBRL MDP M(S, r,,,,, H.H,, we use T. (En) to denote the value iteration under the policy where is history dependent policy.
Lemma 3.6. For a given tabular MDP, the reward on the entire trajectory can be decomposed as r (E.)) Σ rh (8h, ax), Vi in Eq. and V in Eq. are equivalent.
The proof is detailed in Appendix B.Idue to space limitations.
Static rheesuess--maasures. Standard MDPs with a static risk aware objective [Bellemare et al.) Dabney al. 2018 can be written in the distributional Bellman equation follows:
2017
H
(/0 (Ex) =
Σ
(sw aw), EH P. Ex(En) = En.
Fz (e)
Σ
P(& [S(E), (()) 2 (so(e (x - (sh,
(5)
3'ES
(T(s) [' F (T) dG(())
Where S(E) s for E (...,s) the current state in trajectory &. Ex(E=)
(81, A1, 82, a2
3h-1, Qh-1, 9h) denotes the first h steps' trajectory. 2 (Ex) denoted the re- ward from step given the current history. The static reward of is z(n) (E), where & (8) E 2 for D is the initial history.
5

---

Also, we modify the distributional Bellman equation for PbRL MDP M(S,A, Pr, .". H) settings as follows:
TT² (EN) - =r((EH) СH P- (- = En)
(x(())) P(s (((), n4 (E)) (11) (Es
F 2/ (Ex) (z) Σ
(6)
S'ES
VT(() S (T)(T) dG(()
Lemma 3.7. For tabular MDP and a reward of the entire trajectory can be decomposed as ră (Ew) = - h== Th (8h, an), VT in Eq. and V/ in Eq. Gare equivalent.
The proof is detailed in Appendix B.2 due to space limitation.
Each of these risk measures possesses distinct advantages and limitations. Nested risk measures, which incorporate Bellman-type recursion, can directly employ techniques such as the Dynamic Programming Principle (DPP) for computation. However, they are challenging to interpret and are not law-invariant [Hau et al. 2023). On the other hand, static risk measures are straightforward to interpret, but the resulting optimal policy may not remain Markovian and becomes history-dependent. Consequently, techniques such as the DPP and the Bellman equation become inapplicable.
3.3 Objective
We define an optimal policy as:
n"" E argiaax ViT
ie., it maximizes the given objective for M. ViT (s)) will be decided by the selected risk measure, where value iteration calculated using Eq Eq and static calculated using Eq, 6
given algorithm for Assumption 3.8. Regardless of nested static CVaR objectives,
computing "M for a known PbRL-MDP M.
formal proof of Assumption 3.8 is given in Appendix When unambiguous, we drop M and simply write ..
At the beginning of each episode [K]. our algorithm 2 chooses two policies (T1,k) 72,2) 1k O === the random set episodes observed so far. Then,
(. where H₂ = {&I,.. 52, goal is to design algorithm 2 that minimizes regret, which is naturally defined
K
Regret(K)
Σ k=0
2V/ (s1) V (s1) V.TT. (s1)
(8)
Risk Aware Preference based RL Algorithm
In this section, we introduce and analyze an algorithm called RA-PbRL for solving the PbRL problem with both nested and static risk aware objectives. Also, we establish regret bound for it.
4.1 Algorithm
RA-PbRL is formally described in Algorithm T The development of RA-PbRL primarily inspired by the PbOP algorithm, as delineated in Chen et al. [022). which was originally proposed for resk-neutral PbRL environments. Building upon this foundation, one significant difference how to choose a risk aware policy in estimated PbRL MDP, where the value iteration is different. We also use novel techniques to estimate the confidence set and explore for policy, instead of using bonus (which is difficult to calculate in risk-aware problems) in standard RL.
[Chen et al. 2022

---

Algorithm RA-PbRL
Require: episode K, step H. initial state space P, initial reward space R, risk level a, confidence
parameter
1: Set B P, 3 R. Execute two arbitrary policies 11,0 and T2,0 for episode, respectively, and then observe the trajectory 71,0 and 72,0 and the preference Ou-
2: for k = 1...... K do
3: Calculate the probability estimation Pæ:
P&= arg minpep E Li=1& Ex Ex=
ai (.), (Ks)
4: Update transition confidence set:
25 25 2KHSA n4 (x,0))
P' P'
p* s,)) P' (s' 33,0) -
n R-
5: Calculate the reward estimation:
(x(()) arg minGeR Ex - oz
6:
Update the confidence set:
B% - -
Σ (o(Fx(TIN)) - fx(T2K)) - (TI,)) r (T2 Shal n k==0
1-1
7: Update policy confidence set:
I1, {IT m
(VT.,, V p(11)) 2 0, 2,
8:
Compute (T1,e, T2,a):
(Ti,A: T2,a) = arg max m PeBB (V (()) - V p...) mll
9: Observe the trajectory &1 &2 H. and the preference ON Calculate the state-action visiting time before episode (s(88)) a)
11:
end for
The overview the algorithm. Now we introduce the main part of our algorithm. In line we initialize the transition kernel function and reward function confidence set, and execute two arbitrary policies at first. For every episode, we observe history samples and accordingly estimate the transition kernel function (line 3) and update its confidence set (line 4) well as the reward function (line 5) and its confidence set (line 6). Both estimation and calculation used the standard least-squares regression. Based the confidence sets, we maintain policy set in which all policies are near-optimal with minor sub-optimality gap with high probability in line 7. In line 8, we execute the most exploratory policy pair in the policy and observe the preference between the trajectories sampled using these two policies.
The key difference between nested and static objective. The estimation of the transition kernel (line in Algorithm I and the construction of confidence set (line in Algorithm [ are similar for both nested and static objectives. The difference lies in the value iteration, which defined in Eq. for nested objective and Eq. for static objective. The bounds for regrets are different since the going show below.
estimation emror' impact is different
4.2 Analysis
Theorem 4.1 Nested object regret upper bound). With at least probability 8, the nested quantile risk aware object regret of RA-PBRL is bounded by:
Reg Regneste (K)
KHSA 8
00
LcHtVK
V /min ym N.ww i (()) With (8)
B xb
Kddim 8
K (1 2Bpw)
+0
dimt
log
log
(9)
min Wdiim (e)

---

Where (s) denotes the probability of visiting state-action pair at h th step with policy and min 5 () denotes probability of trajectory En 's d th feature 4 Pa(En) * with the policy n.
The proof of this theorem is provided in Appendix D.20, The first term of the regret arises from the estimation error of the transition kernel, primarily dominated by A...., (+)20 (7,4(s). The second term due to the estimation error of the trajectory reward weights, significantly impacted by muw (d). In fact, these factors are unavoidable in the lower bound in certain challenging cases. Thus, they characterize the inherent problem difficulty, i.e., in achieving the nested risk-aware objective, the agent will be highly sensitive to some state-actions or features that are difficult to observe and require substantial effort to explore. This may result in inefficiency in many scenarios.
Theorem 4.2 (Static object regret upper bound). The static quantile risk aware object regret of RA-PBRL is bounded by:
Regstatic( (
so so <L
(K/0) + +o (Lodinrry K log(KB log
K (1 (1+ 2Bw
(10)
The proof of this theorem is provided in Appendix DD21 Notice that the regret for both the nested risk objective and the static risk objective of Algorithm| are sublinear with respect to K, making RA-PbRL the first provably efficient algorithm with one-episode-rewar for these two objectives. Additionally, compared to Chen et al. 2023), we achieve the goal of having both policies gradually approach optimality. Moreover, in comparison the nested risk-aware objective, the static objective focuses on the risk measure of the entire distribution, primarily influenced by the Lipschitz coefficient LG of the quantile function and is less constrained by certain specific cases.
Theorem 4.3 (Nested object regret lower bound). The nested quantile risk aware object regret of RA-PBRL is bounded by:
AK Regret K) 2 O min Bpw min min h.spp. Wr, (s, a) min Wdim,, or (d)
AK
B
(11)
We provide our proof in by two hard-to-leam constructions. By the two instances, we show that the two factors, min sh.pp. (s)s0 Wx,h (s), ming, Wdim,x , are unavoidable in some cases.
Theorem 4.4 (Static object regret lower bound). The static quantile risk aware object regret of RA-PBRL is bounded by:
Regret(K) 2 O(S dimm)
The proof of this theorem is similar to Theorem 4.5 in Chen al. 2022)
5 Experiment Results
In this section, we assess the empirical performance of RA-PbRL (Al (Algorithm Tp. For comparative analysis, we select two baseline algorithms: PbOP, as described in Chen et al. [202]], which is a PbRL algorithm utilizing general function approximation, and ICVaR-RLHF, detailed in Chen al. [023] which is a risk-sensitive Human Feedback RL algorithm. These baselines represent the most closely aligned algorithms with RA-PbRL, especially in terms of employing general function approximation.
The evaluation of empirical performance is conducted through the lens of static regret, as defined in Eq.
5.1 Experiment settings: MDP
In our experimental framework, we configure straightforward tabular MDP characterized by finite steps H = 6. finite actions A = 3. state space S = 4, and risk levels E {0.05, 0.10. 0.20, 0.40). For each configuration and algorithms, we perform 50 independent trials and report the mean regret across these trials, along with 95% confidence intervals. 'he outcomes are depicted in Figures and 3] where the solid lines represent the empirical means obtained from the experiments, and the width of the shaded regions indicates the standard deviation of the experiments.
8

---

X330
4000
0.40
Exi
30000
153.0
3000
Encla atiet
2300
2000
2000
4535
30000
700 000 60W
VOS 1996
4921 600 2010
2000 10/0 (631 0531 100 (1890
0.
2001 4511
0.05
0 0.10
(c) 0 0.20
(d) a: 0.40
Figure 1: Cumulative regret for static CVaR over different
10009
40:000
30500
PSCP
250.0
1030
11:00
10000
2006 <bw 2003 300 2600
4030 5000
150 1200
4300 60/0
200 1200
200 6836 00.0 1200
(a) 0.05
(b) 0.10
(c)
0.20
(d) = 0.40
Figure 2: Cumulative regret for nested CVaR over different a.
5.2 Experiment settings: Half Cheetah
Aditionally, we implement our algorithm to solve MuJoCo's 's Half-cheetah simulation. We implement our proposed algorithm alongside PbOP and TRC and Oh) (2022]. The objective of the algorithms to learn control robot simulation of cheetah to run forward. This problem differs from the previous setting in that it is more challenging and uses continuous state-action space. Because the algorithm ws originally implemented for discrete state-action spaces, we assume the transition, reward, and policy functions can be parameterized by a linear function, which is optimized for using gradient descent.
Similarly to the previous experiment, we run both policies in the MuJoCo setting until 1,000 timesteps have passed. We repeat this for 100 episodes, saving the interactions and final preferences based on the cumulative reward after each episode. Finally, we use the data to perform gradient descent for pre-defined number of repetitions. We repeat the cycle interaction and training another 100 times. In total, the algorithm sees 10,000,000 timesteps and 10,000 preference reward signals.
The key idea behind the implementation of our algorithm lies in the initial optimization of the learned transition and reward functions using the data collected during the interaction. We iterate through tuples containing the initial state, action taken, and transitioned state. We perform stochastic gradient descent to find the best vectors that parameterize the transition and reward functions to predict the collected data.
After obtaining the best transition and reward functions, we use their parameterization to create new parameterization of the value function in line 8. In our case, simply concatenate the vectors parameterizing the transition and reward functions alongside a vector parameterizing the policies. The policy vector used depends on the policy being optimized (the best or exploratory policies.) We then compute the a-CVaR over the preferences obtained using the final cumulative reward. We then optimize the value function parameterization using this as the training data, and perform stochastic gradient descent. To follow the theoretical bounds we establish, we compute the distance between the initial transition and reward parameterizations used in the value function, rolling back the parameterization if the distance is larger than what is established by the theoretical bounds.
5.3 Experimental results
As depicted in Figure 1 and 3 the regret of RA-PbRL over static and nested CVaR initially exhibits linear growth with respect to K, transitioning to sublinear growth upon reaching a certain threshold. This behavior aligns with the conclusions drawn in Section 4.2 It is important note that increased

---

Experiment
0.45
Experiment
ClaPtPoRL (Procosad)
CVaR Poo (Proposed)
1902
TRC
0.00
0.40
PSDP
0.42
0.30
035
0.25
Timeetop
0
200
400
600
800
1000
Timestop
(a) Cx 0.05
(b)
0.10
0.40
EVOR PMRI (Prooood))
Experiment
Chav2-PN (Proprow)
Expetiment
TTCC
CoR
0.30
0.20
0.15
0.15
0.10
600
800
1000
200
4:00
C00
B10
1030
Tirmslep
(c) a 0.20
(d) 0.40
Figure 3: Cumulative regret for static CVaR in the MuJoCo setting over different a.
risk aversion (a - 0) introduces greater uncertainty, evidenced by the larger variance regions observed in the experiments. Notably, the regret of the bad-scenarios associated with RA-PbRL. is significantly lower compared those of other algorithms. It can additionally be observed that as is increased, the regret improves, which is expected as riskier behavior can also improve the odds of finding useful behaviors.
6 Conclusion
In this paper, we investigate a novel PbRL algorithm for solving problems requiring risk awareness. We explore static and nested measures introduce risk awareness PbRL settings. To the best of our knowledge, our proposed RA-PbRL algorithm is the first provably efficient Preference-bate Reinforcement Learning (PbRL) algorithm that incorporates both nested and static risk objectives in one algorithm. Our algorithm is built on innovative techniques for the efficient approximation of regret. A core finding our investigation is the strong influence of the state and trajectory dimensions with respect to the nested risk objective regret. On the other hand, the static risk objective regret is mainly determined by the quantile function.
We have also identified the following four limitations to our work. (1) Our comparison feedback is limited to two trajectories. An interesting, more general approach could consider n-wise comparisons. (2) The reward functions are assumed to be linear in this work for the sake of simplicity. (3) Although this work has considered more general risk measures, we have still made certain assumptions that limit the generality of our results. (4) There is still room for future improvements to further close the gap between upper and lower bounds. We believe this work opens several avenues for future research, including establishing the concrete lower bounds of risk-aware PbRL, improving the computational complexity of the algorithm, and conducting experiments in more diverse and interesting eavironments/simulationn
References
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference Machine Learning, pages
10

---

463-474. PMLR, 2020.
Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al. Training helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint arXiv:2204.058N 2022.
Osbert Bastani, Jason Yecheng Ma, Estelle Shen, and Wanqiao Xu. Regret bounds for risk-sensitive reinforcement learning. Advances in Neural Information Processing Systems, 15:36259-36200 2022.
Chandrayee Basu, Qian Yang, David Hungerman, Mukesh Singhal, and Anca D Dragan. Do you want your autonomous car to drive like you? In Proceedings of the 2017 ACM/IEEE International Conference on Human-Robot Interuction, pages 417-425, 2017.
Nicole Bäuerle and Jonathan Ott. Markov decision processes with average-valuu-attrisk criteria. Mathematical Methods of Operations Research, 74:361-379, 2011.
Marc G Bellemare, Will Dabney, and Rémi Munos. A distributional perspective reinforcement learning. International conference on machine learning, pages 449 458. PMLR, 2017.
Róbert Busa-Fekett Balázs Szörényi, Paul Weng, Weiwei Cheng, and Eyke Hüllermeier. Preference- based reinforcement learning: evolutionary direct policy search using preference-based racing algorithm. Machine learning, 97:327-351, 2014.
2014.
Xiaoyu Chen, Han Zhong, Zhuoran Yang, Zhaoran Wang, and Liwei Wang. Human-in sentaa-in-tthe-loge Provably efficient preference-basee reinforcement learning with general function approximation. In International Conference on Machine Learning, pages 3773-3793, PMLR, 2022.
Yu Chen, Yihan Du, Pihe Hu, Siwei Wang, Desheng Wu, and Longbo Huang. Provably efficient iterated evar reinforcement learning with function approximation. arXiv preprint arXiv:2307.02844 2023.
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.
Will Dabney, Mark Rowland, Marc Bellemare, and Rémi Munos. Distributional reinforcement learning with quantile regression. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017.
Yihan Du, Siwei Wang, and Longbo Huang. Risk-sensitive reinforcement learning: Iterated and the worst path. arXiv preprint arXiv:2206.02678, 2022.
Hannes Eriksson and Christos Dimitrakakis. Epistemic risk-sensitive reinforcement learning. arXiv preprint arXiv:1906.060
2019.
Yingjie Fei, Zhuoran Yang, Yudong Chen, Zhaoran Wang, and Qiaomin Xie. Risk-sensitive rein- forcement learning: Near-optimal sasple tradeoff regret. Advances Neural Information Processing Systems, 33:22384 22395, 2020.
Robert Givan, Thomas Dean, and Matthew Greig. Equivalence notions and model minimization in markov decision processes. Artificial Intelligence, 147(1-2):133-223, 2003.
Jia Lin Hau, Marek Petrik, and Mohammad Ghavamzadeh. Entropic risk optimization in discounted mdps. In International Conference on Artificial Intelligence and Statistics, pages 47-76. PMLR, 2023.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. The collected works of Wassily Hoeffdding, pages 409-426, 1994.

---

David R Hunter. Mm algorithms for generalized bradley-terry models. The annals of statistics, 32(1): 384 984-006,20 2004.
Ashesh Jain, Brian Wojcik, Thorsten Joachims, and Ashutosh Saxena. Learning trajectory preferences for manipulators via iterative improvement. Advances in neural information processing systems, 26, 2013.
Dohyeong Kim and Songhwai Oh. Tre: Trust region conditional value at risk for safe reinforcement learning. IEEE Robotics and Automation Letters, 7(2):6221 --2288, 2022.
Daniel Lowd and Jesse Davis. Learning markov network structure with decision trees. In 2010 IEEE International Conference on Data Mining, pages 334-343, IEEE, 2010.
R OpenAl. Gpt-4 technical report. arxiv 2303.08774. View in Article, 2:13, 2023.
Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. Training language models to follow instructions with human feedback, 2022.
Aldo Pacchiano, Aadirupa Saha, and Jonathan Lee. Dueling rl: reinforcement learning with trajectory preferences. arXiv preprint arXiv:2111 11.4450, 2021.
Stuart Russell and Peter Norvig. Artificial intelligence a modern approach. London, 2010.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 26, 2013.
Yun Shen, Michael J Tobia, Tobias Sommer, and Klaus Obermayer. Risk-sensitive reinforcement learning. Neurul computation, 26(7):1298-1)))
2014.
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):544-55, 2017.
Christian Wirth, Johannes Fürnkranz, and Gerhard Neumann. Model-free preference-based rein- forcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
Christian Wirth, Riad Akrour, Gerhard Neumann, Johannes Fürnkranz, et al. A survey of preference- based reinforcement learning methods. Journal of Machine Learning Research, 18(136): 466 2017.
Runzhe Wu and Wen Sun. Making rl with preference-based feedback efficient via randomization. arXiv preprint arXiv:2310. 14554, 2023.
Zhengqi Wu and Renyuan Xu. Risk-sensitive markov decision process and learning under general utility functions. arXiv preprint arXiv:2311..3588 2023.
Yichong Xu, Ruosong Wang. Lin Yang, Aarti Singh, and Artur Dubrawski. Preference-basee reinforcement learning with finite-time guarantees. Advances in Neural Information Processing Systems, 33:1878441888 18794, 2020a.
Yichong Xu, Ruosong Wang, Lin F. Yang, Aarti Singh, and Artur Dubrawski. Preference-based reinforcement learning with finite-time guarantees. arXiv preprint arXiv:2006.08910, 2020b.
Andrea Zanette and Emma Brunskill. Tighter beolem-deppedeett regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 7304 7312. PMLR, 2019.
Wenhao Zhan, Masatoshi Uehara, Nathan Kallus, Jason D. Lee, and Wen Sun. Provable offline preference-based reinforcement learning. arXiv preprint arXiv:2305.1443 2023.
12

---

A
Notation
We clarify the notations that appear uniquely in this paper to avoid confusion.
variable with"
Ground truth of the variable.
S, A
Finite state space, action space.
8, a
State, action.
S. A
Dimension of state space, action space.
P
Probability transition kernel.
H
Length of episode.
Bh
Set all h-step trajectories.
Eh
A trajectory contains h steps.
(x)
State of h-th step of a trajectory.
(Et)
h steps trajectory
-tep trajectory.
Th (8p,aa))
Reward function of single step h.
(E(EH)
Reward function of whole trajectory.
r1sh
Reward of the ~ h steps of a trajectory.
(
Value function of state step h under policy π in normal MDP.
Value function of state step h under policy in PbRL-MDP.
((X)
Riemann-SStellie integral of over random variable X, i.e. the risk-
aware objective.
N (FR: [00)
Covering number of function class FR scale 1/K K under ||
norm.
B Risk Aware Object Computability
Unlike standard RL where each step's reward can be observed, PbRL represents type of RL characterized by pnce-per-episoee feedback. As a result, our observable and estimable parameters are confined to the trajectory reward r and transition probability functions P". Consequently, the traditional risk-aware objective might be unsuitable, as the reduction in available information prevents the computation of the original risk-aware measure. The risk measure selected for PbRL must satisfy the following condition: should remain unique across MDPs where policies, trajectory rewards and transition probability functions even when each trajectory is fixed, but different step rewards, r* (s, a), vary. This requirement ensures that the risk measure consistently reflects the underlying preferences regardless of variations in specific step rewards.
B.1 Nested Object
Theorem B.1. For the tabular MDP and the reward of the entire trajectory be decomposed as r (EH)
2k=1 r7 (8h, (n),, VI in Eq. and V in Eq are equivalent.
Proof. Firtly, according to Givan et al. (2003], Lowd and Davis 2010), any tabular MDP can be reformulated as a decision tree-like MDP. Thus, considering a tree-like structure for an MDP implies the following characteristics:
The state transition graph of the MDP connected and acyclic. Each state in the MDP corresponds to unique node in the tree. 3. There is single root node from which every other node reachable via a unique path. 4. The transition probabilities between states follow the Markov property, i.e., the probability of transitioning to any future state depends only on the current state and not on the sequence of events that preceded it.
Formally, let S' be the set of states and Pıj the transition probabilities between states s; and sy. The transition matrix P for an MDP with tree-like structure defined such that:
Pij > if there is an edge between s; and sj in the tree, and Pij otherwise.
Moreover, for each non-root node sj. there exists exactly one such that Pij > 0, and s; is the unique parent of 8j in the tree structure.
To classify the two value iteration in Eq. 3 and Eqq we denote the value given by Eq. as V and the value given by Eq.
3 as Vi"" thus, in tabular tree-like like MDP with the reward of the entire trajectory
13

---

which can be decomposed as (EH)
Σm= =/=11 17 (5h, o/), we have the following relationship:
VT V + +rin-1
where Ti-h denotes Reward of the mathematical induction.
steps of a trajectory. We prove this relationship by
Initial case. Using the tree-like PbRL-MDP algorithm and the initial conditions of the Bellman equation, at the final step = H, we have
V r' (s (EH-11) + ri.
(12)
V ri:H-1
(13)
Induction step. We now proved that if
Vh+1 = Vi++ + rish
holds, then
VT V. + rin-1
also holds.
Since this tree-like MDP's policy π is fixed, it has only one path to arrive h th state (s%), denoted as:
Ex((H,1) = (5H22) vεHμ, SH E {EH (A(EH) = sh
(14)
Therefore, rim-1 is unique.
Vi + (Vi++ (6/+1) + rin)) 1/41 ~ (*(s,a)
(15)
+ (Viee (5/+1) + + Th (fx)) + rim--1,
1/1 ~ Ps(
(16)
+ (Vi+1 (6/+1) + + (En))) + Tim-1
6/41 P ('(s.u)
(17)
VE + trin-1
(18)
By applying conclusion, we observe that when
VTT
Thus, have proven that the for the tabular MDP and the reward of the entire trajectory can be decomposed as r (Err) = E r (sh, an), Vi in Eq. and Eq. 4 are equivalent.
B.2 Static Object
Lemma B.2. For the tabular MDP and the reward of the entire trajectory can be decomposed as rt (EH)
- ri (Sh, ),), V in Eq. 5nnd V in Eg are equivalent.
Proof. To classify the two value iteration in Eq. 5 and Eq. 6 we denote the value given by Eq. 5 as V and the value given by Eq, 6 as V thus, in tabular tree-like MDP with the reward of the entire trajectory which can be decomposed as rš (EH)) - rh (sh, ax), we have the following relationship:
VH V +rin-1
where Tish denotes Reward of the ~ h steps of trajectory.
Now, We prove this relationship.
Since this tree-like MDP's policy is fixed, has only one path arrive h th state (st). denoted as:
Ex,E..) = (5())) VEH,I, EH12 E {EH Sx(En) = sn.
(19)
14

---

Therefore, rim--1 is unique. By definition,
V = rE((Et) ÊH ~ (x(H)) = En)
(20)
= =r((En(EH)) + rim-1 εH ~ (- (n(En) = (k)
(21)
V/ + ri--1
(22)
By applying conclusion, we observe that when h = 1
VT VT*
Thus, we have proven that the for the tabular MDP and the reward of the entire trajectory can be decomposed as r'g (CH) = Sh=1 r (5h, an), VTT in Eq. and V/ in Eg equivalent.
C Difference between nested and static risk measure
To explain the difference between nested and static risk measure, present simple example that demonstrates their characters.
Anaasbaaee Amond
Accumslatie Aroidd
Presabiit
Auconca
52-02
03
000
5--02
63
000
A
J
5-01
05
013
5-01
06
002
07
12
0d
0.t
(a) policy
(b) policy B
Figure 4: Cumulative regret for the different a
First, we construct MDP instance in fig. 4 where two policies exhibit identical reward distributions and consequently demonstrate equivalent preference will be observed However, within this instance, these policies yield different outcomes under the nested and static CVaR metrics.
The state space is S {S1, S2,1 S2,2, S2,2, S3,2, S3,3, S3,4), where S1 is the initial state.
The policy space is IT AT TB}. Both policy have have the same action in the first step (a1) and second step (a2), but have the different action in the third step (a3, azz).
The reward functions are follows. r(S1,a1) r(Sa,1, 0g) = 0.3, r(S32,, (z) = 0.2, r(S3,3, az) = 0.4, r(S,,2, 0z) = 0.5. r(S3,1, ag)) = 0.6,
r(S2,1, a2) 0.1, r(S2.2, ag) 0.2,
r(S3,2, a/)) 0.2, r(S3,3, a²) = 0.4, r(S,, d²² 0.2.
The transition distributions are as follows. P PS2..1 a1)a)) = 0.5, (S2.2 S1,a1) 0.5.
P (Sa,1 (2,,, .2) 0.1, P (Sa.2 S2,1, 02) 0.9, P (Sa,3 S 02) 0.1, (S S2,2 a2) 0.9.
As depicted on the right side of the figure, the distribution of rewards is consistent. Consequently, the human feedback preferences for the two policies are identical. We list the differing risk measures for these two policies in Table C
Metric
Value(T
Value(#g)
Nested CVaR
0.2
0.33
0.36
Static CVaR
0.2
0.41
0.41
D REGRET UPPER BOUND FOR ALGORIHTMI 1
In this section, we present the full proof of Assumption I regret upper bound. The proof consists of parts.
15

---

D.1 REWARD ESTIMATION ERROR
Lemma D.1. Reward confidence set construction. Fix 8 E (0, 1), with probability least 1 6, for
all k E [K],
Σ
Br.k
(23)
W=1
where
1 K
dimplog (K (B+))) + logl log(
Bro
6, 0
(24)
Proof. This lemma can be proved by the direct application of Lemma G.5
Let X, = (Ct.1 E1.2
and Y, Ot, and F,,, (--ls(----) = (r(-) r(:))- Then, have that X is F measurable and Y2 is Fr measurable. According to Hoeffding ' inequality (Theorem G.8 {Y
(X,)) is
-suub-gaussian conditioning, and E YY; fr (X.) F(-1] By Lemma G.5 and G.4 since the
linear trajectory embedding function Zн - RR didim with probability at least 8, we have
Bri (0,
1 - K
50 dimmlog (K 2L+))) + log(
(25)
Lemma D.2. Reward estimation error of trajectory embedding. For any k E [O,..., K], reward con- fidence set By where the reward function embedding weight can be noted as W, (Wi,-. ... Wdimy/ ). any fixed trajectory En E Zu, trajectory embedding Φ(Eh) (01,.... ;dsmmr) with probability at least 1 - 8, it holds that,
dimmllog (K (1 + 2Bpw)) log(
ma (Wrrdd Wra s SOS
(26)
kb
Rdim..K (d)
where ng denotes the number of times EH was visted up to episode k.
Proof. According to Lemma D.1 and the assumption of link function, for fixed & E [o,.... K1, and E (O.... dim..] we have,
k
max E
(Wrid wra.e)) (T +
(27)
===1
((Wr wre,d) B))
(28)
3r K
(29)
x²
Where (d) denotes the number of Φa(Eн) + 0 among 1 ~ k episode's trajectory.
Using Cauchy-Schward inequality and Lemma G.6 we have,
dimalog (K (1 + 2Bpw)) + (og(t)
max (Wrr,d Wry,a)l 5 Miss
(30)
xb
D.im. (d)
Lemma D.3. Reward estimation error of the whole distribution.
For (E1,E2) = max, r.ex, ((rr))((((()))) (rr))))) ri(E2)) - (r2(Er) rr((2)))
K
(E (HH,A,) S Oddimay K (log(KBppl) log K (1 2Bpw) BBBp))
(31)
16

---

Proof. Let Fs = (frlfr(2, y) o(r(z) r(v)),r E B% then we define diam FB;
(z. = ma (r) ri(1)) a(r2(x) - -r(()). According to Lemma. D.
òs- maxi diam (Falarx) Let 1/K, T k. and d dime (FR, 1/K)
Accord-
ing to lemma G.6
K
K (1+
x11+BBpu)) 2BPp)
LE 2 O K (l log
(32)
Lemma D.4. Transition estimation error of fixed state action pair. For any fixed k, with probability al least - 26, for any (8,u) E S x A.
2S log (2KHSA
Σ S'ES
P& (s' (s P* (8' 8, a) S SV n
Proof. The proof is same as Eq. (55) in Zanette and Brunskill (011
Lemma D.5, Transition estimation error of whole distribution. For any fixed k, with probability at
least 1 8, for any (s,a) a) E x A, excuted policy Ii T2 E Ilgand any transition possibility kernel
Pr, P2 E B
2 ΣD
H Σ
max P
E
(s' Pi P1
SL,,A, a.,.N) - P- (s') SL,KA, a.,,,))
(33)
im
5O ($
(
AH 3/2 v K log(K))og (K/6)
(34)
Proof. The proof same as Lemma. A.5 in Chen al. 2022).
Lemma D.6. For any iteration value V + R, any two transition possibility kernel P, P. x S A >, and the risk aware object form:
((V(s')) S Fl(o)(E) dG(() ~ a(s.a)
(35)
(Pm((m))) (V (V(s') (s'))
2)- (V (s'))
SIGH H
Σ P (s' 8, P (s' ss,))
(36)
e'SS
Proof. We firstly sort all successor states s S by V (8') in ascending order (from the left to the right) 81 5/2 .2...8' 8's. definition,
And we assume that V(8 = 1) Thus, according to the quantile function's
P(Na())))) (V PP (V (V (s'))
(37)
/ pt (o ( - S (S) dG(())
(38)
/ G(F ((FVA dg S ((Fvr())()) dg
(39)
s ((5(41)- v(s))) (G6))-1G() Σ P(s)((s,))) G Σ ((s)((s,)))
(40)
8 Σ
(V(5/44)) v(())) LG Σ -(ss)))
(41)
1=1
17

---

8
8 LG
(V())41)
Σ ==1
(())]((s,))) ((()s)))))(((((
(42)
1=1
LG
Σ
-P(((() ( v(())
(43)
5=1
La 11
Σ [P()]((s,)) P(5)((s,a))
(44)
The second fourth lines follow the discussion the equivalent expression of the discontinuous distribution & in Lemma 5.1 of Bastani et al. [2022). The fifth line is derived from the properties of Lipschitz functions and Assumption 3.5
Since use the emperical estimation Pa of the transaction kernel P*
k-1 11
P = argminneP
ΣΣ>
(P(s (., (85, (or
(45)
Am ===1k=1
Lemma D.7. Concentration for V.
With probability at least 1 - 28, it holds that, for any k E [K], (s,a) S x A. any transition possibility kernel P1 E B and function V SSS
S + [0, H).
2 (2KHSA) 8
D (2)PP(((a) (V (s')) - ((saa) (V (s'))
2L H
(46)
n& (s(saa) a)
Here ns(s,a) a) is the number of times (s, a) was visited up to episode k.
Proof. According Lemma D.4 recall the definition of the transition possibility confidence set, with probability at least 20,
Σ Pt (s' s,a) -P, (8' ss))]
(47)
E'ES
< Σ E'ES
P (8' 8, - PA (s' 18,)) + PA (8' (,,)) - -P,
(s'1 - (8,))
(48)
(49)
Σ SES
Pk (s' s, P (s' (s' s,a) + Σ
Pk (s' s,a) - Pi s,a)
(50)
e'ES
25 log 2KHSA
121
(51)
(1(()))
Plugging Lemma
D.6 we obtain that with probability at least 1-20 266, for any k E [K], (s, SxA
and function V
[0. H}.
25 log (2HSA
② / (V (s')) (2-P-((6.)) (V (s'))) < 2LG HV
8
(52)
ny (8,a)
18

---

Recall the definition of quantile function 4, G is the quantile CDF weight. Given any target value V : + R, we use pp. (s' s,a) denotes the conditional probability of transitioning to s' from (s, a). conditioning on transitioning to the quantile distribution, and it holds that
++1 BB. (6 8,) = = Pd (T(((((s,))) G() Σ (*()(((s j=1
(53)
Lemma D.8. Quantile Reward Gap due to Value Function Shift. For any (s,a) e 8 A. distribution P, functions V, V : + [0, H,, for any s' E,
2 (()((())) (V' (s') L 2/-P(()aa) (V (5)) S S.. (.1s,a) IV- ('
(54)
This Lemma's 's proof is similar to Lemma 11 in Du et al. (0022).
Lemma D.9. For any (s, E S x A, distribution P, and functions V,V' : + [0, H), for any E.
L (( (V' (s)) - 2smP(()))) (V (c
(55)
Proof. This Lemma comes from Lemma D.8
i+1
g0.v (5 s,
G(
P'
(s(((((s,)))) G( G PM (*(s)((s,a))
(56)
j=1
$ L.
(57)
For any h > 0, E [ and (s. a) E x
A. let (s, a) denote the probability of visiting (s. a) at
step h of episode k. Then, it holds that for any O. [H] and (s, S A, (sn a) E [0.1] and ((,))SSXA (s,(s, =1
Lemma D.10. (Concentration of state-action visitation). holds that
1 Pr a)
HSA
(wn(s,a) - H log
vk > 3. 1
k=1h=1
This Lemma direct application of Lemma G.9 and same as Du et al. 2022 Lemma D.11. (Concentration of trajectory visitation). holds that
dimm
Pr Mdim & (d) Pd (EH) log
Vd [0... diml] 21-8
Proof. This Lemma a direct application of G.9
For any dimension E [O...., dimr]. it holds that
Pa (EH) log (2))
Pr Reimm & (d)
Since d E [O.... dimr). Therefore,
dimm
Pr Ndim & (d) 2 2
Pdim (EH) - logg
d E [0.... dimr] 21-8
19

---

Definition of sufficient state-action visitations. visitations.Follviiin Following Zanette and Brunskill (2019), for any episode & O, we define the set of state-action pairs which have sufficient visitations expectation as follows.
Lx f=:= (1==(100)SSAAAA A:
R-1 H
HSA
Σ pwn(s,a) log
+ H
Definition of sufficient trajetory visitations. Following Zanette and Brunskill (0019), for any episode k > O, we define the set of trajrctory dimension which have sufficient visitations in expecta- tion follows.
Ldim, == d [O...., dimn)
dimt
Ddimm (d) 2 log
+
We use Tedim..ed) to denote the number of da(EH) + among episode's trajectory.
Lemma D.12. (Standard state action visitation ratio). For any K we have
a
KHSA
ΣΣ Σ
/ SA n4(s, a)
8
k=1k=1 (s,a)ECx
This proof is the same as that of Lemma 13 in Zanette and Brunskill [201]].
Lemma D.13. (Standard trajectory visitation ratio). For any K > O, we have
Pdim (d) K
disny
2 dimrr log Kdimm
Tedim (d)
Rim
This proof is the same as that of Lemma 13 in Zanette and Brunskill [2019). Lemma D.14. (Standard Invisitation Ratio). For any K we have
K
Σ
(sn a) < min (s) Pr. (s)
44H log
HSA
+ 5H
(58)
(s.a)ECx
This proof is the same as that of Lemma 10 in Du et al. 2022
Lemma D.15. (Standard trajectory Invisitation Ratio).
For any K
we have
dimr
min pdim,x(d) Pdim,k (d) a.d:padom. (d)20
(4log
daCak
This proof is the same as that of Lemma 10 in Du et al. 2022
Lemma D.16. For any functions + R, > 0, [H] and (s, S A such that (sn(s,a) 0,
Pih (5
G.V
(
mmnn (s..). (w.a).w.,wwee (ts.a)))www.aaaaa........ a( (s,
G.V where Pkh (s, a) denotes the conditional probability of visiting (s, a) at step of episode k, con- ditioning transitioning distortion by the quantion function G which works at each step 1,...,h h 1.
Ga.V (s, a) E Proof. Since Pkh (s, a) is the conditional probability of visiting (8,a), we have Pkh [o, 1]. Since (s a) is the probability of visiting (s, a) at step under policy Th and min,,h. a):. > (x,n(s, is the minimum probability of visiting any reachable (8, a) any step h over all policies म, we have
Pan (s, a) 2
min a (s.0)>0
W (8, a).
20

---

Hence, we have
G.a.V (s,a)
Pich
2
Pich ( (5,0)
1 W W ($,
Lemma D.17. For any functions V S R 0, h [M].
Pdim, &
(d)
1
Pdim, k (d)
min pa (d)
G.V where & (d) denotes the conditional probability of da(En) + 0 of episode k; conditioning transitioning distortion by the quantion function G which always works at each step h 1,...y H.
The proof is similar to Lemma
D.16
D.2
Proof of Algorithm D regret upper bound
Lemma D.18. For probability of - 26, it holds that π E Ll, which calculated as follows:
F = {
(VIT TE (VTro.P(Sn) TH 1, (..g.p((n)) (Sn)) 2 0, Voo}
max
(59)
Proof. It equals to for any policy E IT,
max (VT.,, VI (Eh)) p(r)) 2 T
(60)
According to Lemma D.1 and Lemma D.4 with least possibility 1 26, holds that:
ro E Br P
E
B
(61)
Thus,
max PEBE
I.T.. (Ex)
Vi (Ex))
(62)
Vir P(n)
TT L,rg (Ex)
(63)
Where the last equation comes from the definition of optimal policy x* (Eq. 7
Lemma D.19. Given a positive constant â E (0, 1}, with probability at least 4K8, we have the following inequality holds:
Regnested(K)
(64)
max (V''' 1y .P. (8k,1)
Vi 1,r,,p- (sk.1) (VT.") (sk.1) Vi (sk,1))
(65)
nEB.PP
max BE PEEB
(VT (SK.1) VT22 p. (sk,1) (VT (SK.1) ViT Vi (sw,1)))
(66)
Proof.
Reg(A) (K) Σ
Vx" p. (sk,1) VTr p. (SK.1) + VTr+t.p (SK.1) VIP.. (SK.1)
(67)
k
max
(VT (8R,1) - Vim P.,,,, (SK,1))
(68)
ri PEBB.PEEBE
1=
1.m.P p- (sk,1)
mm p. (SK,1)
max (V/=* (VT,,,,,, (5H,1) Vi P, (SE,
(69)
21

---

max rE PAEBE
(Vi.r..2 (5K,1) - mh (sk,1)
(70)
1,r p. (sk,1) - 1, (5k,1)
(VIT"
1r2, (5k,1) - Vi Pr (sk,1))
max
r2EB; P2EBE
(71)
< &VI.'. p. (Sk,1)
V. 1,r,, (sk,1)
(V (8K,1) - V L.m.P. P, (8k,1))
max
(72)
+ +V I. (Sk,1) T 1. (sk,1)
(V..r..,, (sk,1) 1/ 1.r..p, (sk,
max reB P.EBE
(73)
(V (SK,1) - 1
1,,,,p pp (5x,1) - (VT,,, (Sk,)) - m 1, (sk, 1)}
max
(74)
I,,,, (Ir,", (sk,1) VT p (sk,1) (Vir,,P,, (sk.1) V V.r..PP (sk,1)))
max F2BB P.EBE
(75)
Where (a) comes from the definition of the optimal policy confidence set (Lemma D.18) when
x² E Igg at each episode, (b) derives from the characters of max value.
D.3 Nested Regret
Lemma D.20. Nested regret upper bound. Given positive constant E (0, 1}, with probability at least 1 8, we have the following inequality holds for every k [K].
Regneded (K)
KHSA
0o
La LGH! VKSAlog
min (s, Wox (s,
Kdimr
K 2Bpw)
1
+0
dimt
log
log
(76)
kb
minw, (d)
Proof. We use Vi,r".p (sk,1) to denote that the first h steps in the trajectory & is sampled using policy from the MDP with transition P, and the state-action pairs from step + 1 up until the last step is sampled using policy from the MDP with the true transition kernal p Therefore,
CVaR,a, (s, a) is defined as the Here (a) due Lemma D.7 and D.8 (b) comes from that Pkk probability of visiting (s, a) at step h of episode h under the conditional transition probability
ga (- +.-) for each step h -....,
Firstly, we analyze the term I, and Is. Recall that for any policy n, h E [H] and (s, a) S x A, Wx.h (s. a) and (s) denote th probabilities of visiting (s, a) and at step h under policy respectively. Thus, we have:
H ΣΣ (s,a)LLx
K
G.a.va Puk
2SA log 2KHSA 8
(s,a)Lo HV
(77)
(3,a)
k=1k=1
(3) < LGH / 2SA (
2KHSA
K H
Σ
Pkh
Goo. (s,a)
K
H
Σ
G.a.Vol Pkh
(8,a)
(=(,,))
km 11mml
(s.a)ELx
A=1Aml (s.a)ELx
(78)
22

---

2KHSA
G.a.Vok Pkh
(s,a) .K (pra(s,a) #03 VKH
LaH 2og
ΣE Σ
(x(
k=1h=1 (s,0)ECx
(79)
LoHH 28 ASK log(
2KHSA
ΣΣ
Psh
G.a.
(s, (sh(s,
IK (pnn a) + 0}
Pkn(s,0)
mx(3,0)
k= (a,a)ELx
(80)
2K HSA
1
Pan(s,a)
x LGH 28AKH log(
((s0))) Wn ( a)
nx(5, a)
h= (s.a)ECk
(81)
(c)
2K 2KHSA
25 25log 2KHSA
x LGH 2SAKH log(
nx,
min (e..))) Wreh (8, a)
(82)
2KHSA
(83)
8
(ssap Wa (s,
Here (a) is due to Cauchy-Schwardy inequality and the fact that for any k > 0 and h E H
CVaR,a, /²
E(s.)essxA Pkt
(s.a) 1. (b) comes from Lemma D.16 (c) uses Lemma D.12
and the fact that for any deterministic policy æ, h E [H] and (8,a) E S A, we have ei- ther (x,n(s, n,ww, a (s)>0 (s).
(n,((s) or (x,((s,a) 0, and thus min, (s (s,a(
For the term 12 and To, using Lemma D.14 we have:
K
H
ΣΣ
Σ
Pk.
G.V.
(s, H)
(84)
k=1b=1
(#.O)ECE
HSA
8S log
+ 10S
(85)
min Nowe,, Wr,h
For the term I3 and 17, we have:
G.V.
Paim
(d) [w w
(86)
1=1 de
G.V.S pr Dk Edecau, a Pdsm, Tidim, (d)
K Σ
G.V Pdtimk
(d)
K
(d)
Tetim &
(W
wA B
k=1 deLerrm
k=1 deLaim.
(87)
Σ -==l
K Edecam Pdim, (d)
G.V
B
K ((1+2Bpp
xbl V
dimr log
8
Telim, K (d)
(88)
B xbl
K(1 (11p))pp))
ΣK K Edecam. Pdim,
Ex=1 Pakm.. (d)
G.V
(d)
Paim, (d)
V
dimrr log
8
Ndim, (d)
I
dim, x (d) 0)
(89)
G.V*k
c 2B xb
Kdimr 8
(1 + 2Bpw)
Ek=l Edecamm Pdimnkk
(d)
dimr
v log
log
I(pTt dim, (d) + 0)
Vaim. K (d)
(90)
23

---

2B
K 5
(1 + 2Bpw)
dimr / xb
log
log
(91)
minwa (d)
Here (a) is due Sauchy-Schward inequality. (b) comes from Lemma D.17
(c) uses Lemma D.15
For the term 4 and Ig, using Lemma D.15 we have:
K
G.V.
Paim.
(d)
(92)
1=1
(de Ldim.i
dimer
min
Ps dim Pa.dim(d)
(llog
+5
(93)
x.d:Pr.dim (d)>0
8
Then, summing all the term, we have:
Regnested (K)
KHSA
so
LGH VKSAlg
M (t. Wix A
B
dimu / log
Kdimr
K (1 + 2Bpw)
+0
log
(94)
8
min Wiiim (c)
L
D.4 Static Regret
Lemma D.21. Static regret upper bound. Given a positive constant 8 E (0, 1]. with probability at least - 8, we have the following inequality holds for every [K].
Regstatic
<o (LaS AHiVKlog o (Loddmmry K
K (1112BBpu
log
5
(95)
Proof. We use V (8k,1) to denote that the first h steps in the trajectory & is sampled using policy from the MDP with transition P, and the state-action pairs from step h + 1 up until the last step is sampled using policy x from the MDP with the true transition kernal P*. Therefore,
Regstatic K)
(96)
Vr. pa (sk,1) 11r- pp (sk.1) (VT,,, (sk,1) Vi I. (SK,1))
(97)
I VVT p. (8k,1)
V. (Sk,1) - (Vr.' P. (8k,1) - VT (sk,1))
(98)
.P (SK.1)
Vi (5k,1)
(VT,", (SK,1) - -ir,,p, (Sk,1)
(99)
K
2
H
max P.PP.EBP
P (s' 88,,,,, a....)) P2 (s' Be.,,,n (100)
1=1 k=1
H
Eg
max n.
P (- (.I., arkch, vn (. 8L. a.N.))) fra (. S.R. a(k,)))))
1=1 Am1
(101)
50 T. AH V (K/8)) + 0 (cadimryy K log K BBw)) log [ 2B
(102)
24

---

E Lower bound of the regret.
(a) optimal policy
(b) sub optimal policy
Figure 5: Hard to learn case
E.1 Regret Lower Bound of Nested Reward
Lemma E.1. Nested Regret Lower Bound. There exists an instance of Nested CVaR RL-RM, where the regret of any algorithm is at least:
AK
AK ming, Waim, (d)
Regret(K) 20 min Bp
B
(103)
mill,, h..... (6)20 Wa (8,
Proof. Hard to learn case 1. Consider the instance shown in Figure The state space is de- fined as = {s1, $2...., Sn, 21, I2, Tz); where $1 is the initial state, and n = S 3 < S. We define the trajectory reward functions as follows: For any εH Zu. @(EH) (I(SH(EH) = x1 I(SH (EH) )= = x2 (((HH(EE) = 23 B), w, = (1p, 0.8p. 0.2p)
The transition distributions are follows. Let μ be parameter which satisfies that 0 < < / < 3 For any a E A. (82 81, 81,4) a) = p.pp( (x1 81, 0)
3/. 81, a) = / and p (23 81, a) = J..
For any i E (....., n - }} and a E A. (8 8; = 1 and (x) 8; a) = 1. D2 and T3 are absorbing states, i.e., for any a E A. (x) 21, = (,p x2, a)
and p (23 23 a)
p (z2 8n, a.)) = - + 1/ and p (x3 8n, aJ)
where is parameter which satisfies < 77 < a and will be chosen later. For any suboptimal action E A' {ay} .P (x2 sn, 1- and p (Is Sn. a)
For any aj A. let [ and Pr,[-] denote the expectation and probability operators under the instance with a, = aj. Let Egnit [+] and Pranit denote the expectation and probability operators under the uniform instance.
Fix an algorithm A. Let * denote the policy taken by algorithm in episode Let Ns...yy
EKEnK { (sn) = aj} denote the number of episodes that the policy chooses aj in state 8.. Let Ven.a, denote the number of episodes that the algorithm A visits (sn.9)). Let w (s,)) denote the probability of visiting 8n an episode (the probability of visiting sn the same for all policies).
Then, it holds that E VV.,, az] w (sx) E [N...ay)
According to the definition of nested-CVaR-PbRE risk objective in Eq. have:
(a - 17) 0.2 + 17 0.8
V12 (81)
Bp,
(104)
a
and summing all episodes & [K], we have
K B,(R(K) = Σ (2V (s1) - (81) -ii)) (s1))
(105)
k=1
BBp
0.6 (2K
E2 [Na..a]]
(106)
a
BBp
A
0.6
K
Ej [Nanaa]]
(107)
a
A
i=1
25

---

Therefore, we have
A =
E [[((K)
Σ
(81)
Vi=" (51)
(108)
A
/=1
1
Σ
0.6Bp (K Ey [NNo..e;))
(109)
/=1
A Σ 1=1
= =0.6Bp !
Bj
[N [Nenos]
(110)
A
For any j E (}, using Pinsker's inequality and 0 a
3. we have that
KL (Puni (Sn; (s,)) IIp, (Sns xz(s)))) (I(Ber(a)] Ber(a 1)) S (a-mi
nlll o S e
for some constant 01 and small enough 17. Then, using Lemma A. in Du et al. 2202). we have,
K
By [Nr,] I Eunit
[Nz,] +
2 V
Eumir [Vr,] KL. (TT)()))) [lp (8n, (8n))
(111)
K
cnn²
< Eunir [Nz,]] +
2 V w (sn) Emnit [Nm,]]
(112)
Then, Using
プラ j=1 Bunis [Nenay]]
= 22 and Cauchy-Schwarz inequality, we have:
Kn
Ej
[N
5
Eunis [Nem
(sn) IEuii [Nem.a)]
(113)
2A
1
Kn
Runif
[N [Nsn
+
A
w (8x) .Bunif [Na
(114)
A
2A
j=1
j=1
K
Kn
C1 W (sm) K
<
+
(115)
A
aA
Thus, have
[[((K)) 2 0.6Bp
! a
K
K
K1
C1
w (sn)
K
(116)
A
2
aA
Let 17 = 22 w(s.)K for small enough constant Cz. We have
A
B[R(K)] =
BP
K
(sn)
K
AK
=Ω BPy a (sn)
Hard to learn case 2.
The trajectory reward functions are as follows. For any EH E Zh. Φ(EH) (I(S = z1 B,), =
= 22) (SH(EE)) B)) Wr
(1p, 0.8p, 0.2p, (0.2 p))
The transition distributions are as follows. Let μ be parameter which satisfies that 0 < p < For any A,p (82 a) = μr, (x) $1. a) = 33,, (x2 81, 81, a) = p and p (x3 81, a) μ.
For any E (2...., .n 1} and a E (s 18, = and p (x) 88, (8,
11. T2 and T3
absorbing states, i.c., for any A, (Z) 21, = L, (x) x2,a) and p (23 23,
26

---

xe thu
Breaef-
Brand
optimal policy
(b) sub optimal policy
Figure 6: Hard to learn case
(i2 8n, a.)) 1 a and (zi 8n, a..) a, where v is parameter which satisfies 0 < < and will be chosen later. For any suboptimal action E AA {as} P (xg 8n;a)
and
(xa a) a For any dj A, let [ and Pry[-] denote the expectation and probability operators under the instance with a. = aj. Let lunit [:] and Pronit denote the expectation and
probability operators under the uniform instance.
According to the definition of nested-CVaR- CVaR- risk objective in we have:
V/" (s1) = 0.2n
(117)
Thus,
K
E((R(K)] =
Σ k=1
(2V (81) -V1) ViTa (s1))
(118)
0.2mBB (2K B3 [Nomaa)]
(119)
j=1
= 0.2
(K. K- Σ
Ej [Nan
(120)
j=l
Therefore, we have
1 K Σ
[[R(K)] =
- -VT (s1)
(121)
A
j=l k=1
= Ā
1
Σ
0.2mBpp (K - Ei [Nemas])
(122)
1=1
= 0p
71
K
1
Σ 5=1
[Nan:a,]
(123)
A
For any {A, B}. since the preference based on Bernoulli distribution, using Pinsker's incquality and 0 <a a we have that KL (Punit (sm: (s())) [Ip (Sn, (x,))) KL(Ber(a))] Ber(a
n)) I (0.2 (0.-7) &
ein² for some constant e₁ and small enough 7). Then, we have, 0.16
K
Ej [N,]] < Eunif [Na,]
+
2 V Eanir [Vay] KL (IT (s..) [lp; (8ns (8n))
(124)
K
G177
< R
Fuuir
[N=p] +
w (sn)
Eunit [Nn;]
(125)
2
0.16
Then, Using Σラ= Eunis [Nemlay]
=KK and Sauuchy-Shwwaziiin inequaliit, we have:
27

---

1
Σ
A
[sse $
1
Bunis [N
+
Kr
A
C1
w (d) Bunis [N
(126)
A
A
2A
0.16
==1
==1
==1
Kn
Bunif N NNnaa
(d) Bunif [Nonis]
(127)
A
2A
0.16
K1
C1 w (d)
+
(128)
A
2
0.16A
Thus, we have:
K
Kn
C1
w (d)
K
E [[(K] 2 0.2Bp-
K
(129)
A
2
0.16A
Let 2
0.16A w(d)
for small enough constant Cg.
We have
A
B[R(K)] = Ω Bp
K
(d)
K
AK
Ω
Bp
w (d)
F The optimal policy calculation for known PbRL MDP
In this section, we describe how to compute the optimal policy for the CVaR objective when the PbRL-MDP is known; this approach is described detail in Bauerle and Ott 2011). Bastani et al. [0022]. Following this work, we consider the setting where are trying to minimize cost rather than maximize reward. particular, consider an know PbRL MDP M(S,A, A P", H), where and A, and our goal is to compute a policy æ that maximizes its CVaR objective.
Lemma F.l. CVaR definition. For any random variable we have
CV) sup p 1 pER
Ez [(0 2)+1| -)-+)
a
where the minimum is achieved by p" VaR... (Z).
F.1
Static CVaR object
Since the optimal policy for static CVaR object satisfies:
n E argmax (VaR(Z(T))
(130)
As consequence of Lemma
we have
CVaR (2(7))
max CVaR (Z(T) #ell
(131)
1 p E2((T) (p-2%%) +1
max Hell pER a
(132)
$1.
sup pER
max E Bzm well
(133)
28

---

Thus, the optimal policy is:
(0-
T arg max 2(r)
(134)
mell
where
Bz (0- z(x))
= arg arg (p) where PER
J(p) = -
mmxx mell
(135)
Value iteration. we reconstruct the MDP as enlarge the state space 8n2 = (Sh. p), where will work as quantile value. Letting S be the initial state of the original PbRL MDP M.
We iterate the value and calculate the policy as follows:
V ((E p)) max (E(()))
(136)
/
Vi, ((En. p)) max REA
Vini ((s' o (En, p)) p (s (SA(E))
(137)
x (Ex) = argmatoEd [Thn ((s' (E).a),))) P (s' (SA(E)).
(138)
Then, given an initial state 81, we construct state 31 = (81, -p"), where
p--a { pp-1 ((), }
p²
argsup PER
and then acting optimally in M.
F.2
Nested CVaR object
According to Eq. nested CVaR object could directly use the Bellman equation to iterate the value.
Value iteration. we reconstruct the MDP as enlarge the state space 8n2 = (Sh. p). where will work as quantile value. Letting S be the initial state of the original PbRL MDP M.
We iterate the value and calculate the policy as follows:
Vu ((EH p)) rī (EH)
(139)
1 p- a
( ( Vatn ((s' o (En, a), p1)) }}}
((En, p)) = max sup *ell PER
(140)
E BB (o (p- Vatz ((s' (En, a), p)) }}
((hh) arg max sup Flll PE
p
(141)
then acting optimally in M.
G AUXILIARY LEMMAS
Definition G.I. a-dependence in Russo and Van Roy
(0033]. For > 0 and function X is a-dependent on the set Xn = {21, ... {nn) C X' with respect to 2, if any pair of functions 2, Z with
class whose elements are with domain X, an element
V EE (xx))= (x:))) a satisfies z(x) 2a(x) a. Otherwise, a-independent on X, if it does not satisfy the condition.
Definition G.2. Eluder dimension in Russo and Van Roy (0033) For a > and function class 2 whose elements are with domain X, the Eluder dimension dim 2, a),, is defined as the length of the longest possible sequence of elements in X' such that for some of 2 a, every element o' independent of its predecessors.
29

---

Definition G.3. Covering number Given two functions and u, the bracket [1, u] is the set of all functions satisfying S fs u. An a-bracket bracket [L, u| with ||u vu-1] [|] < a. The covering number (FF a; is the minimum number of c--brckkets needed to cover F.
Lemma G.4. (Linear Preference Models Eluder dimension and Covering number). For the case of d-dimensional generalized trajectory linear feature models rg (EH) := (Ø (E(H). Wr), where o Traj Rddie is known dimer dimension feature map satisfying || (EH) S B and 0 e Rd is an unknown parameter with ||wll22 I Pw- Then the o-Eluder dimension of (EH)) is at most demr
(dimm (og(Bpw/a)) The a covering number is upper bounded by [1+2Bpw
Let (Xp xp Xp) pm 1,2... be sequence of random elements, Xp E X for some measurable set X and Y E R. Let F be subset of the set of real-valued measurable functions with domain X. Let be a filtration such that for all 2 1, (X1, Yi.... xp-1, p Xp) is F F--1 measurable and such that there exists some function f. E F such that E DY, F Fp-1l = fa (Xp) The (nonlinear) least square predictor given (1, Y1, X,, Y)) is ft argmin fEF Ep=1 (f (X,) y,)² We say that Z is conditionally p-subgaussion given the o-algebra F is for all À E RR log E[exp(AZ) IF I 22
== (R (Rp)
holds for all p
For >> 0, let Na be the || -ooeering number
of F scale a. For 3 > 0, define
Fi(B) -
Σ (( S
(142)
Lemma G.5. (Theorem 5 of Ayoub et al.) (2020)). Let F be the filtration defined above and assume that the functions in F are bounded by the positive constant > O. Assume that for each s 2 1. (Yp - J. (Xp)) is conditionalyy o-subgaussian given F p-1. Then, for any O, with probability 1 for all 2 f. E Fr (3,(6, a)), where
()) -002 log (2Na/8) 4ta (C+ o0 2og log(A(((++1)0))))
Lemma G.6. (Lemma 5 of Russo and Van Roy 2013 Let F E B (X,C) C) be set of functions
bounded by C > 0, (Ft) and (5t) be sequences such that F, C F and at X hold for 1 121 1. Let Fl 1yy = {(((m) (x1)..... (vt)) :::))::)))) E F) (C IR') and for S C TR', let diam(S) = SuPa,VES I|u 2112 be the diameter of S. Then, for any T 2 and a > 0 it, holds that
Σ diam (Fll.)) S C(dAT) 28g VTT,
where 6T maxigisT diam (Frlen.)) and d = dimg@F
Lemma G.7. If (Be 2 0 N) is nondecreasing sequence and F, { fEFF | f fr 2.E. S SVB. where frs e argminjer L2,(f) and L2f(f)
ΣT-1 (A(A)) R,)², then for all E NNNo and > 0,
1 (WF, (At) > 5 <
T
(
[33 [45T+1 +1 (Fimg(Fe))
where wr(a) == SuD f(a) -i))-inffeF (a) denotes confidence interval widths.
Theorem G.8. Hoeffding's inequality Hoeffding 1994/. Let X1, X2...., Xn be independent Liml
random variables that are sub- Gaussian with parameter a. Define S, = -i X,. Then, for any t > 0, Hoeffding's 's inequality provides upper bound the tail probabilities of Sn, which is given by:
+2
Pr (IS, E[S,] 2 t) < 2exp
2no
This result emphasizes the robustness of the sum Sn against deviations from its expected value, particularly useful in applications requiring high confidence in estimations from independent sub- Gaussian observations.
30

---

Lemma G.9. (Lemma F.4. in Dann et al. (2117)) Let For i = 1... be a filtratiion and XI....X, be sequence of Bernoulli random variables with (X; 1 F(-1) P. with P. being Fi-1" measurable and X; being F; measurable. It holds that
P
E
X
Po/2 - W/ Se-w
t=1
31

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims made in the abstract and introduction accurately reflect the paper's contribution and scope: RA-PbRL algorithm.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The paper discussed the limitations of the work in section 3.2 and section 6
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
32

---

The paper provided the full set of assumptions and complete proof in Appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The experimental results presented in the paper are reproducible. We have provided detailed pseudocode and full information for implementing the code, allowing any researcher to easily implement our algorithm and benchmark it against other algorithms.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
33

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes)
Justification:
We provide link to our code repository.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurlPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /ttpe//gguudeeeoeeouuuuumbbbba ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Experimental details are provided in section 5.1.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: the results are accompanied standard deviation.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
34

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The computer resources needed to implement experiments are provided in the section 5.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:p////eerrppssccppbbbbbbbb/e
Answer: [Yes]
Justification:
The research conducted with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
35

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: the paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
36

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subject.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subject.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
37


Reviews:
[{"review_id": "z8MQVJu9i1", "reviewer": "Reviewer_TVSN", "summary": "This paper studies preference-based RL (PbRL) where instead of the expected return, the agent optimizes a risk measure based on preference feedback. The authors study two settings called \"iterated\" and \"accumulated\" quantile risks, otherwise known as nested and static risks. They provide sublinear regret bounds for both approaches and instantiate a hard-to-solve MDP to establish a lower bound.", "questions": "- The authors tackle nested and static CVaR with the same methodology. Classically, the static formulation encounters time consistency issues that do not appear in nested CVaR. Why isn't it the case here? Could the authors discuss time-consistent risks in the preference-based setup? \n\n- What does Assp. 3.1 formally say? How should it be interpreted and how restrictive is it? \n\n- lines 142-148: Why can we restrict policy-search to deterministic policies even in the preference-based setting? Is it an underlying assumption or is there a formal result stating that we do not lose optimality? \n\n- Are the results from Sec. 3.2 novel - especially the recursions (5) and (6)? \n\n- It is perhaps a philosophical concern but I would be glad to have the authors' feedback. If the feedback is preference-based, what is the difference between average and risk-sensitive return maximization? In other words, doesn't the agent's objective express itself directly through the preference outputs? This question is crucial to me because I currently do not see the motivation for RS-PbRL.\n\n*Minor comments and suggestions*\n\n- Please follow the formatting guidelines for section titles - Secs. 2, 5\n- line 58: \"may not be applicable\"; line 60: \"cannot\"\n- line 125: \"and the reward\"; line 126: \"the trajectory embedding dimension\"\n- Assp. 3.1: \"We\" - capital letter\n- line 133: \" At each iteration\"; line 134: \"unlike standard RL\"; line 137: \"a Bernoulli distribution\"\n- lines 139-140: \"It is aware\" --> \"It is known\" or \"We are aware that\"; line 157: \"risk-measures\"\n- line 160: \"a random variable\" (remove distribution); line 161: \"then\" --> \"so\"\n- line 163: What is $Z$? Should it be $X$?\n- line 176: \"denotes the\"\n- lines 178-179: Reformulate \"the policy should be history-dependent policies\"\n- line 185: \"The proof is\"\n- Lemma 3.5 and 3.6: \"For a tabular MDP and a reward of the entire trajectory being decomposable as ...\"\n- line 191: \"given the current history\" \n- line 199: \"The proof is\"\n- line 207: \"We define\"\n- line 211: \"regardless of iterated or accumulated\"\n- line 214: \"of the entire episode training\"\n- line 218: \"that minimizes regret\"\n- lines 221-22: \"We present the algorithm called RA-PbRL and establish and upper-bound regret for it\"\n- line 225: Remove \"The algorithm\"; \"defined\" --> \"described\" or \"presented\"; \"which main part\"\n- line 229: \"choose a policy\"; line 232: \"find an estimated optimal policy\"\n- line 236: \"we initialize\"; line 237: \"we observe history samples\"; line 239: \"use\" (present)\n- Algo 1, line 9: \"Receive trajectory ... and preference\"; line 10: italic $k$\n- lines 253, 254: \"with policy $\\pi$\" - remove \"the\"\n- line 274: \"hard-to-learn constructions\" (hyphen and \"s\")\n- lines 275-6: \"are unavoidable in some cases\"\n- line 282: \"For a comparative analysis\"; line 286: \"aligned ... with RA-PbRL\"", "limitations": "Although some limitations are not addressed in this work (see previous remarks), most are properly described in Sec 6.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The proposed research is well-motivated, as it combines the accessibility of preference-based feedback with risk-sensitive RL, which is crucial for safety-critical applications. \n\nIf correct, the contributions are meaningful, as they englobe both nested and static risk measures. \n\nThe text has a nice flow. I have to say that I reviewed a previous version of this submission and the structure is much clearer now.", "weaknesses": "- Some used terminologies are non-standard for the risk-sensitive RL (RS-RL) community. For example, the authors discuss \"iterated\" versus \"accumulated\" risk measures. As far as I know, most of the RS-RL works name these \"nested\" versus \"static\" risk measures [1,2,3]. This confused me, as I could not understand the abstract until the middle of the introduction. \n\n- line 62: \"the optimal policy becomes history-dependent, which is more general than assuming the trajectory reward is a linear function of the sum of per-state features\". Why? This deserves more explanation, as it justifies the novelty of this work compared to Chen et al (2023). \n\n- Previous works have studied RL under trajectory feedback, although not in the PbRL setting, see e.g., [4]. Therefore, contribution 3. seems overstated. \n\n[1] Hau, J. L., Petrik, M., & Ghavamzadeh, M. (2023, April). Entropic risk optimization in discounted MDPs. In International Conference on Artificial Intelligence and Statistics (pp. 47-76). PMLR.\n\n[2] Hau, J. L., Delage, E., Ghavamzadeh, M., & Petrik, M. (2024). On dynamic programming decompositions of static risk measures in Markov decision processes. Advances in Neural Information Processing Systems, 36.\n\n[3] Tamar, A., Chow, Y., Ghavamzadeh, M., & Mannor, S. (2015). Policy gradient for coherent risk measures. Advances in neural information processing systems, 28.\n\n[4] Efroni, Y., Merlis, N., & Mannor, S. (2021, May). Reinforcement learning with trajectory feedback. In Proceedings of the AAAI conference on artificial intelligence (Vol. 35, No. 8, pp. 7288-7295).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your insightful comments and recognizing the potential contribution of our work. Here are the responses to the issues you raised:\n# For Weakness1: \nWe acknowledge your point. In fact, we find the terms \"nested\" and \"static\" risk measures are more widely accepted within the RS-RL community, as mentioned in your references [1,2,3]. We appreciate your critique and will revise our terminology.\n\n# For Weakness2: \nThe reason the reward function is history-dependent and cannot be sum-decomposable is that, in many cases, the trajectory is embedded into a vector which is then dot-multiplied with a weight to obtain the reward（Pacchiano et al. (2021)）. (Details on the trajectory embedding can be found in line 124, under the Reward model of the entire trajectory section). Often, the embedding function is not even linear. Chen et al. (2023) represent a specific instance where the trajectory embedding is a linear embedding (see Remark 3.2). Our approach addresses two main limitations in Chen et al. (2023):\n1. In many scenarios, it is not feasible to calculate the state-action reward function at each step. Consider a straightforward example where two policies each follow a determined  5 steps trajectory. Consequently, we can only obtain a preference equation and are unable to compute the 10 state-action reward function for each step. \n\n2. In many application scenarios, we will only use trajectory embeddings. Practical and relevant trajectory or state-action embeddings are described in works such as Pacchiano et al. (2020) and Parker-Holder et al. (2020). Thus the embedded reward for a single episode may not always be simply represented as the sum of each state-action reward which is suggested by Chen et al. (2023).\n# For Weakness3: \nWhile prior studies have explored RL under trajectory feedback, our work distinctively focuses on risk-aware objectives, which fundamentally differ from previous approaches. Our algorithm specifically caters to both \"nested\" and \"static\" risk measures, The definition of value in our approach (as shown in Eq. 4 and 6, using quantile values) contrasts with the conventional mean value definition used in prior studies). \n\n# For Question1\n\nIt is important to clarify that we do not employ the same methodology for two different objectives throughout. Although the algorithmic processes for calculating nested and static risk measures appear similar. Consequently, our value equations (Eq. 4 and 6) are distinct. Regarding the time-consistency issues associated with nested CVaR, we address these in Appendix F, which details the optimal policy calculation for known PbRL MDPs. This calculation is also applicable to Algorithm 1. We have expanded the state space to $\\tilde{s}_h=\\left(\\xi_h, \\rho\\right)$, where $\\rho$ functions as a quantile value. This expansion allows us to optimize iteratively by incorporating $\\rho$, enhancing the algorithm’s efficacy in handling time-consistent risks.\n# For Question2:\nFormally, Assumption 3.1 implies that the absolute values of the non-zero components of trajectory embeddings have a lower bound b, or in other words, there is a gap between zero and some positive number b in the absolute values of components of trajectory embeddings. This is evident for finite-step discrete action spaces, where we can enumerate all trajectory embeddings to find the smallest non-zero component, satisfying most application scenarios. It is easy to demonstrate that B/b is always greater than or equal to the ratio of max reward to min reward. However, we can always perform a linear transformation on the embedding vector to make the equality hold, thus allowing us to use the ratio of max reward to min reward to estimate B/b.\n\n# For Question3: \nWe postulate the existence of an optimal deterministic policy for any PbRL MDP, consistent with other PbRL research like Chen. et al, 2022. \n# For Question4:\nThe recursions (5) and (6) introduced in Section 3.2 build upon existing methods from Du et al. (2022) and Pacchiano et al. (2023), adapted for our risk-aware PbRL context. These adaptations make our recursive formulas (4) and (6) novel, and specifically tailored to address the complexities of risk-sensitive value iteration.\n# For Question5: \nThe agent expresses its objectives through preference outputs, specifically following a Bernoulli distribution `BN(p)` to choose the better trajectory, where `p` is determined by the reward. Essentially, our method infers the reward function and possibility kernel by observing the agent's objectives, thereby obtaining the policy's reward distribution. The distinction between average and risk-sensitive return maximization can be illustrated as follows:\n|          | Trajectory1                | Trajectory2                | CVaR(`\\alpha=0.1`) |\n| -------- | -------------------------- | -------------------------- | -------------- |\n| Policy A | reward=0.1, possibility=0.1 | reward=0.5, possibility=0.9 | 0.1            |\n| Policy B | reward=0.2, possibility=0.1 | reward=0.3, possibility=0.9 | 0.2            |\n\nThe agents favor Policy A (`P(A>B)=0.9`), but if we can infer and calculate the reward for each trajectory, we would find that Policy B is less risky (` B's CVaR  is lager`).  An example in real life might be: a large language model, fine-tuned with user feedback, generates two text options, A and B, for user selection. For most users, Text A is non-offensive and appears more comprehensive, thus preferred; however, Text A actually contains content offensive to a minority group. On average, the policy generating A performs better because it is chosen by the majority and only offends a few. Nonetheless, overall, we aim to avoid any offensive content completely, which is where risk sensitivity comes into play: after considering risk sensitivity, Text B would prevail. Compared to non-preference-based scenarios, preference-based feedback only affects our methods for estimating rewards and does not alter our consideration of risk.", "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": "yN6h4QQgaX", "reviewer": "Reviewer_QEr2", "summary": "This paper focuses on the theoretical analysis of risk-aware preference-based reinforcement learning and introduces Risk-Aware-PbRL (RA-PbRL) to optimize both iterated and accumulated risk-aware objectives.", "questions": "See above.", "limitations": "None.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper proves that both iterated and accumulated quantile risk-aware objectives can be applied to one-episode reward settings. This may provide a theoretical foundation for future episodic RL or PbRL methods focusing on risk-related objectives.\n- This paper provide analysis of regret guarantee on the proposed risk-aware algorithm.", "weaknesses": "- I think it is necessary to clearly clarify all the strong assumptions, not only the linear reward function assumption, as these strong assumptions typically cannot be met in real-world control scenarios. This would make the theoretical results in this paper more applicable and useful for researchers using deep PbRL methods to address real-world control problems.\n- Why is the regret of RA-PbRL higher than PbOP when $\\alpha$ is small (Fig. 1(b) and 2(b))? Can the authors provide an intuitive explanation for this phenomenon?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the constructive feedback and valuable time for evaluating our paper. We especially thank the reviewer for mentioning that “provide a theoretical foundation for future episodic RL or PbRL methods focusing on risk-related objectives.” The reviewer has raised some valid questions and provided many mindful suggestions. The following are our responses to the reviewer’s comments:\n\n> Weakness1: I think it is necessary to clearly clarify all the strong assumptions, not only the linear reward function assumption, as these strong assumptions typically cannot be met in real-world control scenarios. This would make the theoretical results in this paper more applicable and useful for researchers using deep PbRL methods to address real-world control problems.\n\nThank you for your valuable suggestions. In this work, we primarily extend the frameworks set by Pacchiano et al. in their 2022 PbRL work and Bastani et al. in their 2022 risk-aware RL work. The only modification we made is the assumption that the absolute values of components of trajectory embeddings has a gap between 0 and a positive number \\( b \\) (Assumption 3.1), which is entirely reasonable, especially in the context of a finite-step discrete action space (a common scenario) where its validity is evident. Regarding the practical applications of our work, we have supplemented it with experiments in Mujoco, a commonly used simulation environment in robotics and deep reinforcement learning (see public comments), where our theory-based model performed well, demonstrating the potential of our work to provide useful guidance in real-world problems.\n\n>Weakness2: Why is the regret of RA-PbRL higher than PbOP when alpha is small (Fig. 1(b) and 2(b))? Can the authors provide an intuitive explanation for this phenomenon?\n\nI would like to clarify your question: are you asking why RA-PbRL exhibits higher regret than PbOP in the early episodes under the minimal setting of alpha=0.05, as shown in Fig. 1(a) and 2(a)? Because in the figures you mentioned, Fig. 1(b) and 2(b), our algorithm did not exhibit higher regret.\nHere is an intuitive explanation for why our algorithm exhibits greater regret compared to the non-risk-aware algorithm in the early stages: Unlike PbOP, which solely focuses on maximizing the average reward, our RA-PbRL algorithm emphasizes risk consideration. Imagine a person learning a potentially risky new skill, such as driving or chopping vegetables. They are likely to choose a more conservative strategy with lower expected returns to avoid risks (think about your first driving experience, you couldn’t drive as efficiently as an experienced driver). However, as learning progresses (iterations of the algorithm), and the risk boundaries are gradually mastered, we can maintain high returns while always avoiding substantial losses, thereby surpassing the risk-neutral PbOP after a certain number of episodes. The reason this phenomenon appears only at a small alpha might be because the probability of risk events is low enough that early results can be good even if they are ignored. For larger alphas, risk-neutral algorithms initially fall behind due to these high-risk events.", "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": "rcW7OgEgkA", "reviewer": "Reviewer_EoFm", "summary": "This paper incorporates risk-awareness into Preference-based Reinforcement Learning (PbRL). Specifically, it tackles the issue that under PbRL, the reward is episodic, meaning that it can only be computed on full trajectories. The authors adapt both iterative and accumulated quantile risk objectives to deal with episodic rewards.\n\nAdditionally, the paper presents an algorithm (RA-PbRL) to incorporate these objectives into PbRL.\n\nLastly, the authors provide regret boundaries for both iterative and accumulated quantile risk objectives with RA-PbRL.", "questions": "In PbRL, it is often assumed that the given preferences $o_i$ may be noisy. Do authors assume perfect preferences? If not, it would be interesting to analyse how the amount of noise in the preference affects the regret bounds.", "limitations": "The limitations have been correctly addressed.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "[Quality, Clarity] The paper is well written (particularly the introduction). As far as I could follow the mathematical development is robust, with regret upper- and lower-bounds being established for both types of risk considered.", "weaknesses": "*  **W1** [Quality]: As the manuscript already mentions, the experimental setting is very simple. It would have been interesting to train more complex settings, particular from actual human preferences.\n *  **W2** [Significance]: I think more could be done to stress the important of risk-awareness in the PbRL setting. After reading the paper, it was still not clear to me which applications would benefit from RA-PbRL.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for the positive score and for recognizing the mathematical development of our work. We summarize our responses to the concerns and revisions that we will make to this paper.\n\n> Weakness 1 : As the manuscript already mentions, the experimental setting is very simple. It would have been interesting to train more complex settings, particularly from actual human preferences.\n\nWe have added experiments conducted in Mujoco, a commonly used simulation environment in robotics and deep reinforcement learning (see public comments and attachment), where our theory-based model performed well, demonstrating the potential of our work to provide useful guidance in real-world problems. We also agree that real human preferences constitute a good experimental setting, and we plan to implement our algorithm in this setting in the future.\n\n\n> Weakness2 [Significance]: I think more could be done to stress the important of risk-awareness in the PbRL setting. After reading the paper, it was still not clear to me which applications would benefit from RA-PbRL.\n\nA2:  Thank you for your insightful suggestion. RA-PbRL (Risk-Aware Preference-based Reinforcement Learning) has significant potential for various real-life applications. For instance, in autonomous driving, PbRL can reduce the computational burden by obviating the need to calculate reward signals from every state-action pair, while incorporating risk-awareness to enhance safety (referenced in Chen et al., 2022). Additionally, in fields like generative AI, including systems like ChatGPT (discussed in Zhuo et al., 2023; Qi et al., 2023; Chen et al., 2023), PbRL is utilized to gauge algorithm performance where managing risk is crucial to prevent the generation of harmful content. We agree that emphasizing these applications could better highlight the importance of our contributions, and we will expand on this aspect in our revised manuscript.\n> Question1: In PbRL , it is often assumed that the given preferences o_i may be noisy. Do authors assume perfect preferences? If not, it would be interesting to analyse how the amount of noise in the preference affects the regret bounds.\n\nIn our framework, we do not assume perfect preferences; instead, we model the given preferences o_i as adhering to a Bernoulli distribution, as stated on line 137 of our paper. This setup involves a noisy comparison (duel) between two trajectories, consistent with the settings used in Pacchiano et al., 2023, and Chen et al., 2022. Assuming noise in the utility or reward leads to similar outcomes for preferences since the Bernoulli distribution remains invariant.", "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": "XQ6j6NhCTH", "reviewer": "Reviewer_LP4v", "summary": "This paper studies and proves the applicability of two risk-aware objectives to Preference-Based Reinforcement Learning (PbRL), i.e., iterated and accumulated quantile risk objectives. The authors design an algorithm called Risk-Aware-PbRL (RA-PbRL), which can optimize both iterated and accumulated objectives. Furthermore, the authors provide a theoretical analysis of the regret bounds. The results demonstrate that the regret bounds of algorithm RA-PbRL under both the iterated and accumulated objectives are sublinear with respect to the number of episodes. Finally, the authors present empirical results to support their theoretical findings.", "questions": "Please see the weaknesses above.", "limitations": "Please see the weaknesses above.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1.\tThe studied problem, i.e., applying the iterated and accumulated risk-aware objectives to PbRL, is relevant and useful for some applications such as healthcare and AI systems. The considered reward model depends on the feature of the trajectory, instead of the feature of the state-action pair, which is more general than the prior works.\n2.\tThe authors consider both the iterated and accumulated risk-aware objectives, which encompass the popular CVaR objective. In addition, the authors also design an algorithm and provide regret analysis for both objectives. The algorithm design and theoretical analysis are well executed.", "weaknesses": "1.\tThe proposed algorithm is very straightforward, which seems to simply combine the confidence set construction and the risk-aware objective. This algorithm is computationally inefficient and hard to implement in practice. Can the authors explain more on how to implement this algorithm?\n2.\tWhat is the intuition behind the factor $\\min_{\\pi,d} \\omega_{\\pi}(d)$ in Theorem 4.1? In particular, why the probability that the feature is not zero will influence the regret? More discussions on the regret due to reward estimation are needed.\n3.\tIt seems that $L_G$ appears in the upper bound (Theorem 4.2) but not in the lower bound (Theorem 4.4). Why the authors said that “it demonstrates the significant impact of LG” below Theorem 4.4? In addition, it seems that $dim_{T}$ appears in the lower bound, but not in the upper bound. Can the authors explain more on it?\n4.\tThis paper needs careful proof-reading. There are many typos. For example, the factor $\\min_{\\pi,d} \\omega_{\\pi}(d)$ in Theorems 4.1 and 4.3, and the $O(…)$ notation in Theorems 4.1 and 4.2. In Line 130, “use” should be “used”. In Line 197, the “and” should be moved to the front of “$V^{\\pi}_i$ in Eq.5 …”?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the effort in reviewing our paper and appreciate our versatility compared to prior work. The following are responses to the reviewer’s concern.\n\n> Weakness:  The proposed algorithm is very straightforward, which seems to simply combine the confidence set construction and the risk-aware objective. This algorithm is computationally inefficient and hard to implement in practice. Can the authors explain more about how to implement this algorithm?\n\nThank you for your feedback.We have established a formal algorithmic framework with well-defined regret bounds for the PbRL problem. This \"straightforward\" framework draws inspiration from numerous RL theory papers, such as PbRL by Pacchiano et al., 2023, and risk-aware RL by Bastani et al., 2022. Our main technical challenges lie in estimating the confidence set and proving the regret bounds. We have employed rigorous mathematical techniques for these estimations, including methods like least squares and the application of covering numbers. In practice, to address your concerns about computational efficiency and implementation, we have successfully implemented this algorithm in a Mujoco environment demonstrating good performance. Further implementation details, particularly concerning the construction of confidence sets and integration with risk-aware objectives, are provided in public comments aid practical application.\n\n\n> Weakness2: What is the intuition behind the factor $\\min _{\\pi, d} \\omega_\\pi(d)$ in Theorem 4.1? In particular, why the probability that the feature is not zero will influence the regret? More discussions on the regret due to reward estimation are needed.\n\nThank you for raising this insightful question. We acknowledge the need for more discussion on how reward estimation affects regret and will enhance our paper with a detailed explanation.  The factor $\\min *{\\pi, d} \\omega*\\pi(d)$ in Theorem 4.1 plays a critical role, which influences regret through the exploration of critical but seldom visited states. In particular, Appendix E Figure 4 illustrates a case where states with less possibility to vist, due to their higher uncertainty in estimation, lead to higher regret. This addition will clarify the intuition behind information entropy and its impact on regret calculations. \n\n\n> Weakness 3: It seems that L_G appears in the upper bound (Theorem 4.2) but not in the lower bound (Theorem 4.4). Why did the authors say that \"it demonstrates the significant impact of LG\" below Theorem 4.4? In addition, it seems that \\operatorname{dim}_T appears in the lower bound, but not in the upper bound. Can the authors explain more on it?\n\nThank you for your concern. Indeed, a more detailed explanation of the regret results is warranted. The reason we mention \"it demonstrates the significant impact of L_G\" is as follows: By comparing the lower bound to the upper bound, the presence of $L_G $highlights the unique challenges in risk-aware settings. Reducing the gap between these bounds is challenging because $L_G$, derived from the quantile function, assigns weights to the $\\alpha$-tile states, thereby amplifying the effects of estimation errors.\n\nRegarding the issue with $\\operatorname{dim}_T$, there was an oversight in our documentation. Theorem 4.2 actually pertains specifically to tabular settings. The more general result is found on Page 26, Lemma D.21. We will address this discrepancy and make the necessary corrections in the revised manuscript.\n\n> Weakness 4: This paper needs careful proofreading. There are many typos. For example, the factor $\\min_{\\pi, d} \\omega_\\pi(d)$ in Theorems 4.1 and 4.3, and the $O(\\ldots)$ notation in Theorems 4.1 and 4.2. In Line 130, \"use\" should be \"used\". In Line 197, the \"and\" should be moved to the front of \" $V_i^\\pi$ in Eq. 5 ...\"?\n\nWe appreciate your meticulous review and will carefully proofread the manuscript to correct these and any other typos.", "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:
We thank all the reviewers and ACs for their time and efforts in reviewing our paper and providing insightful comments. We acknowledge reviewers[TVSN,LP4v] for recognizing our contribution of applying both iterated and accumulated risk-aware to PbRL and reviewers [QEr2, EoFm]’s appreciating for our  mathematical development and theoretical analysis.  In addition to the detailed response to each reviewer, here we clarify common concerns and summarize the new results.
1. Since the experiment in our manuscript is simple, we implement our algorithm to solve MuJoCo's Half-cheetah simulation. This setting is more realistic than our previous toy setting and aims at learning how to control a simplified cross-section of a cheetah robot. Detailed information about the experiment can be found in the PDF. The results show our algorithm has a good performance compared to baseline, which demonstrates our algorithm and theory can guide real-life applications.
2. Risk-aware PbRL have many applications. For instance, in autonomous driving, PbRL can reduce the computational burden by obviating the need to calculate reward signals from every state-action pair, while incorporating risk-awareness to enhance safety (referenced in Chen et al., 2022). Additionally, in fields like generative AI, including systems like ChatGPT (discussed in Zhuo et al., 2023; Qi et al., 2023; Chen et al., 2023), PbRL is utilized to gauge algorithm performance where managing risk is crucial to prevent the generation of harmful content. We agree that emphasizing these applications could better highlight the importance of our contributions.

Meta-review: Preference-based reinforcement learning has been investigate under its full settings and reduced formats (preference-based optimization). This paper investigates its conservative form with theoretical guarantees. 

Traditional PbRL aims to maximize mean reward or utility, which is a risk-neutral approach. The proposed RA-PbRL incorporates risk-aware objectives to address scenarios where risk sensitivity is crucial, e.g. in healthcare. The theoretical analysis of RA-PbRL includes establishing regret upper bounds that are sublinear w.r.t.. the number of episodes. The empirical analysis shows that the regret of the RA-PbRL algorithm is lower than that of other representative algorithms.

The meta reviewer read the paper and discussions. Although there is a lack of references on preference-based RL and risk-aware RL, this paper has reached the bar for NeurIPS. Reviewer LP4v considers the paper was written hurriedly. The AC agrees with Reviewer LP4v that this paper can benefit from a detailed round of revision before the camera ready submission.
Decision: Accept (poster)