RA-PbRL: Provably Efficient Risk-Aware Preference-Based Reinforcement Learning

Authors: yujie  zhao
jose  efraim aguilar escamill
weyl  lu
huazheng  wang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 05:35:32

Abstract: Preference-based Reinforcement Learning ( PbRL ) studies the problem where agents receive only preferences over pairs of trajectories in each episode. Traditional approaches in this field have predominantly focused on the mean reward or utility criterion. However, in PbRL scenarios demanding heightened risk awareness, such as in AI systems, healthcare, and agriculture, risk-aware measures are requisite. Traditional risk-aware objectives and algorithms are not applicable in such one-episode-reward settings. 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-Aware- PbRL (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.

Main paper: 
 introduction: 
 Reinforcement Learning (RL) (Russell & Norvig, 2010 ) is a fundamental framework for sequential decision-making, enabling intelligent agents to interact with and learn from unknown environments. This framework utilizes a 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 et al., 2017) .Despite its performance, a significant limitation of the standard RL paradigm is the selection of a state-action reward function. In many real-world scenarios, constructing an explicit reward function is often a complex or unfeasible task. As a compelling alternative, Preference-based 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 a more intuitive and direct approach in fields involving human interaction and assessment, such as autonomous driving (Basu et al., 2017) , healthcare (Coronato et al., 2020) , and language models (Bai et al., 2022) .Previous approaches to PbRL (Xu et al., 2020a; Coronato et al., 2020; Xu et al., 2020b; Chen et al., 2022; Zhan et al., 2023) mainly aim to maximize the mean reward or utility, which is risk-neutral. However, there is a growing need for risk-aware strategies in various fields where PbRL has shown empirical success. For example, in autonomous driving, PbRL 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 risk-sensitive problem settings require risk awareness to ensure safety. 
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 a 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 et al., 2020) , gaming (Silver et al., 2017) , and autonomous driving (Basu et 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-based feedback, as evidenced by the rich literature on the topic Chen et al. (2022) ; Xu et al. (2020a) ; Wu & Sun (2023) . As noted in our introduction, previous theoretical explorations on PbRL have predominantly aimed at achieving higher average rewards, which encompasses risk-neutral PbRL. We distinguish our work by taking the novel approach of formalizing the risk-aware PbRL problem.In recent years, research on risk-aware RL has proposed various risk measures. Works such as Fei et al. (2020) ; Shen et al. (2014) ; Eriksson & Dimitrakakis (2019) integrate RL with a general family of risk-aware utility functions or the exponential utility criterion. Accordingly, studies like Bastani et al. (2022) ; Wu & Xu (2023) delve into the CVaR measure for the whole trajectory's reward distribution in 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 et al. (2023) presents an advancement in the form of a nested CVaR measure within the framework of RLHF. The limitation of this work lies in the selection of a random reference trajectory for comparison, causing an unavoidable linear strong nested CVaR regret. Consequently, we are left with only a 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 et al., 2021) . Therefore, the one-episode-reward might not even be sum-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 at each step and explore both nested and static risk-aware objectives, aiming to provide a more general method.3 Problem Set-up and Preliminary Analysis 
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 as a tuple, M(S, A, r ⋆ ξ , P ⋆ , 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 ⋆ : S × A → P(S) is the transition kernel, where P(X ) denotes the space of probability measures on space X . A trajectory is a sequenceξ h ∈ Z h , Z = H h=1 Z h where Z h = (S × A) h-1 × 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 r ⋆ h (s h , a h ) specifies the reward at each step h, a significant distinction in the PbRL MDP framework is that the reward function r ⋆ is defined as r ⋆ ξ (ξ H ) : (S × A) H-1 × S → [0, 1], denoting the reward of the entire trajectory.Reward model for the entire trajectory. For any trajectory ξ H , we assume the existence of a trajectory embedding mapping ϕ : Z H → R dim T , and the reward of the entire trajectory is defined as the function: r ⋆ ξ (ξ H ) := ⟨ϕ(ξ H ), w ⋆ r ⟩. Here, dim T denotes the trajectory embedding dimension. Finally, we denote ϕ(ξ H ) = (ϕ 1 (ξ H ), . . . , ϕ dim T (ξ H )).Assumption 3.1. We assume that for all trajectories ξ H and for all d ∈ {1, . . . , dim T }, ∥ϕ d (ξ H )∥ ∈ {0} ∪ [b, B] where b, B > 0 are known. ∥w ⋆ r ∥ ≤ ρ w and ρ w 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 et al. (2023) is one case of such map , where ϕ(ξ H ) = H h=1 I (s h , a h ) and dim T = S × A. Therefore, for all d ∈ {1, . . . , dim T }, ∥ϕ d (ξ H )∥ ∈ {0} ∪ {1, . . . , H} 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 k ∈ [K], the agent selects two policies under a deterministic policy framework, π 1,k and π 2,k , which generate two (randomized) trajectories ξ 1,k H and ξ 2,k H . In PbRL, unlike standard RL where the agent receives rewards every step, the agent can only obtain the preference o k between two trajectories ξ 1,k H , ξ 2,k. By making a query, we obtain a preference feedback o k ∈ {0, 1} that is sampled from a Bernoulli distribution:o k ∼ Ber σ r ⋆ ξ ξ 1,k H -r ⋆ ξ ξ 2,k H (1)where σ : R → [0, 1] is a monotonically increasing link function. We assume σ 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 σ 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 on the current state. The agent cannot observe the individual reward r h (s, a) and thus cannot compute the target value at each step. To circumvent this challenge, the algorithm should take action according to a history-dependent policy. A historydependent policy Π = {π h } h∈[H] is defined as a sequence of mappings ψ h : Z h → A, providing the agent with guidance to select an action, given a trajectory ξ h ∈ Z h at time step h. For notation convenience, let Π denote the set of all history-dependent deterministic policies.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 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-measures. 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-aware objective. The quantile function of a random variableX is F † X (τ ) = inf {x ∈ R | F X (x) ≥ τ }.We assume F X is strictly monotone, so it is invertible and we have F † X (τ ) = F -1 X (τ ). The risk-aware objective is given by the Riemann-Stieljes integral:Φ(X) = 1 0 F † X (τ )dG(τ ) (2)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. (α-CVaR objective) Specifically, in α-CVaR,G(τ ) = 1 α τ if τ < α, 1 if τ ≥ α.and Φ(X) becomesΦ(X) = 1 α α 0 F -1 X (τ )dτ. Assumption 3.5. G is L G -Lipschitz continuous for some L G ∈ R >0 , and G(0) = 0, G(1) = 1.For example, for the α-CVaR objective, we have L G = 1/α.There are two prevalent approaches to Risk-aware-MDPs: nested (or iterated) (such as Iterated CVaR (ICVAR) (Du et al., 2022) and Risk-Sensitive Value Iteration (RSVI) (Fei et al., 2020) ), and static (referenced in (Bastani et al., 2022; Wu & Xu, 2023) ). MDPs characterized by an iterated risk-aware objective facilitate a value function and uphold a Bellman-type recursion.Nested PbRL-risk-measures. For standard RL's MDP, the nested quantile risk-aware measure can be elucidated in Bellman equation type as follows:EQUATIONHere r ⋆ h (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 not be calculated or the reward of the entire trajectory might not be decomposed. Therefore, the policy should be history-dependent. We rewrite the nested quantile objective's Bellman equation with the embedded trajectory reward as follows:EQUATIONFor any PbRL MDP M(S, A, r ξ , P, H), we use Ṽ π,r ξ ,P h (ξ h ) to denote the value iteration under the policy π, where π is a history dependent policy. Lemma 3.6. For a given tabular MDP, the reward on the entire trajectory can be decomposed asr ⋆ ξ (ξ H ) = H h=1 r ⋆ h (s h , a h ), V π 1 in Eq. 3 and Ṽ π 1 in Eq. 4 are equivalent.The proof is detailed in Appendix B.1 due to space limitations.Static PbRL-risk-measures. Standard MDPs with a static risk aware objective (Bellemare et al., 2017; Dabney et al., 2018) can be written in the distributional Bellman equation as follows:Z (π) h (ξ h ) = H h ′ =h r ⋆ h ′ (s h ′ , a h ′ ), ξ H ∼ P (• | Ξ h (ξ H ) = ξ h ) F Z (π) h (ξ) (x) = s ′ ∈S P (s ′ | S(ξ), π h (ξ))F Z (π) h+1 (ξ•(s ′ ,π h (ξ))) (x -r ⋆ h (s h , a h )) (5) V π 1 (s) = 1 0 F † Z1 (π)(τ ) • dG(τ )Where S(ξ) = s for ξ = (. . . , s) is the current state in trajectory ξ,Ξ h (ξ H ) = (s 1 , a 1 , s 2 , a 2 , . . . , s h-1 , a h-1 , s h ) denotes the first h steps' trajectory. Z (π)h (ξ h ) denoted the reward from step t given the current history. The static reward of π is Z (π) 1 (ξ), where ξ = (s) ∈ Z 1 for s ∼ D is the initial history. Also, we modify the distributional Bellman equation for PbRL MDP M(S, A, r ⋆ ξ , P ⋆ , H) settings as follows:Z (π) h (ξ h ) = r ⋆ ξ (ξ H ), ξ H ∼ P (• | Ξ h (ξ H ) = ξ h ) F Z (π) h (ξ h ) (x) = s ′ ∈S P (s ′ | S(ξ), π h (ξ))F Z (π) h+1 (ξ•(s ′ ,π h (ξ))) (x) (6) Ṽ π 1 (s) = 1 0 F † Z1 (π)(τ ) • dG(τ )Lemma 3.7. For a tabular MDP and a reward of the entire trajectory can be decomposed asr ⋆ ξ (ξ H ) = H h=1 r ⋆ h (s h , a h ), V π1 in Eq. 5 and Ṽ π 1 in Eq. 6 are 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 a 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.We define an optimal policy as:EQUATIONi.e., it maximizes the given objective for M. Ṽ π 1 (s 1 ) will be decided by the selected risk measure, where value iteration calculated using Eq. 4 and static calculated using Eq. 6. Assumption 3.8. Regardless of nested or static CVaR objectives, we are given an algorithm for computing π ⋆ M for a known PbRL-MDP M.A formal proof of Assumption 3.8 is given in Appendix F. When unambiguous, we drop M and simply write π ⋆ .At the beginning of each episode k ∈ [K], our algorithm A chooses two policies(π 1,k , π 2,k ) = A (H k ), where H k = {ξ 1,k ′ ,H , ξ 2,k ′ ,H , o k } k k ′ =0is the random set of episodes observed so far. Then, our goal is to design an algorithm A that minimizes regret, which is naturally defined as:EQUATION4 Risk Aware Preference based RL AlgorithmIn 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 a regret bound for it.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) • The experimental setting should be presented in the core of the paper to a 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. 
algorithm: 
 RA-PbRL is formally described in Algorithm 1. The development of RA-PbRL is primarily inspired by the PbOP algorithm, as delineated in Chen et al. (2022) , which was originally proposed for risk-neutral PbRL environments. Building upon this foundation, one significant difference is 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 a policy, instead of using a bonus (Chen et al., 2022) (which is difficult to calculate in risk-aware problems) as in standard RL.The overview of the algorithm. Now we introduce the main part of our algorithm. In line 1, 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) as well as the reward function (line 5) andAlgorithm 1 RA-PbRL Require: episode K, step H, initial state space P, initial reward space R, risk level α, confidence parameter δ 1: Set B P 0 = P, B r 0 = R, Execute two arbitrary policies π 1,0 and π 2,0 for one episode, respectively, and then observe the trajectory τ 1,0 and τ 2,0 and the preference o 0 .2: for k = 1 • • • K do 3:Calculate the probability estimation Pk :Pk = arg min P∈P 2 i=1 k-1 k ′ =0 H h=1 |⟨P(s i,k ′ ,h , a i,k ′ ,h ), I(s i,k ′ ,h+1 )⟩| 2 . 4:Update transition confidence set :B P k = P ′ | s ′ ∈S Pk (s ′ | s, a) -P ′ (s ′ | s, a) ≤ 2S log( 2KHSA δ ) n k (s,a) B P k-1 5:Calculate the reward estimation:rk (•) = arg min r∈R k-1 k ′ =0 (σ(r(τ 1,k ′ ) -r(τ 2,k ′ )) -o k ′ ) 2 6:Update the confidence set:B r k = r ′ (•) k-1 k ′ =0 [σ(r k (τ 1,k ′ ) -rk (τ 2,k ′ )) -σ(r ′ (τ 1,k ′ ) -r ′ (τ 2,k ′ ))] 2 ≤ β r,k (δ) B r k-1 7:Update policy confidence set:Π k = {π | max r ξ ∈B r k ,P∈B P k ( Ṽ π 1,r ξ ,P (s 1 ) -Ṽ π ′ 1,r ξ ,P (s 1 )) ≥ 0, ∀π ′ } Π k-1 8: Compute (π 1,k , π 2,k ): (π 1,k , π 2,k ) = arg max π1,π2∈Π k max r∈B r k ,P∈B P k ( Ṽ π1 1,r ξ ,P (s 1 ) -Ṽ π2 1,r ξ ,P (s 1 )) 9:Observe the trajectory ξ 1,k,H , ξ 2,k,H , and the preference o k 10:Calculate the state-action visiting time before episode k: n k (s, a) 11: end for its confidence set (line 6). Both estimation and calculation used the standard least-squares regression. Based on the confidence sets, we maintain a 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 set 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 4 in Algorithm 1) and the construction of confidence set (line 6 in Algorithm 1) are similar for both nested and static objectives. The difference lies in the value iteration, which is defined in Eq. 4 for nested objective and Eq. 6 for static objective. The bounds for regrets are different since the estimation error's impact is different as we are going to show below.Theorem 4.1 ( Nested object regret upper bound). With at least probability 1 -δ, the nested quantile risk aware object regret of RA-PBRL is bounded by:EQUATIONWhere w π,h (s) denotes the probability of visiting state-action pair at h th step with policy π and min π,d ω dim,π (d) denotes the probability of trajectory ξ H 's d th feature Φ d (ξ H ) ̸ = 0 with the policy π.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 min π,h,s:w π,h (s)>0 w π,h (s). The second term is due to the estimation error of the trajectory reward weights, significantly impacted by min π,d ω π (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:EQUATION)The proof of this theorem is provided in Appendix D.21. Notice that the regret for both the nested risk objective and the static risk objective of Algorithm 1 are sublinear with respect to K, making RA-PbRL the first provably efficient algorithm with one-episode-reward 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 to the nested risk-aware objective, the static objective focuses on the risk measure of the entire distribution, primarily influenced by the Lipschitz coefficient L G 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:EQUATIONWe provide our proof in E.1 by two hard-to-learn constructions. By the two instances, we show that the two factors, min π,h,s:p π,h (s)>0 w π,h (s), min π,d ω dim,π (d) , 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) ≥ O(S 2 A + dim T ) √ KThe proof of this theorem is similar to Theorem 4.5 in Chen et al. (2022) . 
experiment results: 
 In this section, we assess the empirical performance of RA-PbRL (Algorithm 1). For a comparative analysis, we select two baseline algorithms: PbOP, as described in Chen et al. (2022) , which is a PbRL algorithm utilizing general function approximation, and ICVaR-RLHF, detailed in Chen et al. ( 2023), 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. 8.In our experimental framework, we configure a straightforward tabular MDP characterized by finite steps H = 6, finite actions A = 3, state space S = 4, and risk levels α ∈ {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. The outcomes are depicted in Figures 1 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. Aditionally, we implement our algorithm to solve MuJoCo's Half-cheetah simulation. We implement our proposed algorithm alongside PbOP and TRC. The objective of the algorithms is to learn to control a robot simulation of a cheetah to run forward. This problem differs from the previous setting in that it is more challenging and uses a 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 a pre-defined number of repetitions. We repeat the cycle of 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 a new parameterization of the value function in line 8. In our case, we 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 α-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.As depicted in Figure 1 and 3, the regret of RA-PbRL over static and nested CVaR initially exhibits a 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 to note that increased risk aversion (α → 0) introduces greater uncertainty, as 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 to 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. 
conclusion: 
 In this paper, we investigate a novel PbRL algorithm for solving problems requiring risk awareness. We explore static and nested measures to introduce risk awareness to PbRL settings. To the best of our knowledge, our proposed RA-PbRL algorithm is the first provably efficient Preference-based 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 in 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 environments/simulations.OpenAI, R. Gpt-4 technical report. arxiv 2303.08774. View in Article, 2:13, 2023.Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C. L., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., Schulman, J., Hilton, J., Kelton, F., Miller, L., Simens, M., Askell, A., Welinder, P., Christiano, P., Leike, J., and Lowe, R. Training language models to follow instructions with human feedback, 2022.Pacchiano, A., Saha, A., and Lee, J. Dueling rl: reinforcement learning with trajectory preferences. arXiv preprint arXiv:2111.04850, 2021.Russell, S. J. and Norvig, P. Artificial intelligence a modern approach. London, 2010.  
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, confidence 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.)• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It 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 a 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 of range (e.g. negative error rates). • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in 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 is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses for existing assets Question: 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?Answer: [NA] Justification: the paper does not use existing assets.Guidelines:• The answer NA means that the paper does not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: We clarify the notations that appear uniquely in this paper to avoid confusion. Riemann-Stieljes integral of over a random variable X, i.e. the riskaware objective.N F R , 1 K , ∥ • ∥ ∞ Covering number of function class F R at scale 1/K under ∥•∥ ∞ norm.Unlike standard RL where each step's reward can be observed, PbRL represents a type of RL characterized by once-per-episode 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: it 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.Theorem B.1. For the tabular MDP and the reward of the entire trajectory can be decomposed asr ⋆ ξ (ξ H ) = H h=1 r ⋆ h (s h , a h ), V π1 in Eq. 5 and Ṽ π 1 in Eq.6 are equivalent.Proof. Firtly, according to Givan et al. (2003) ; Lowd & 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:1. The state transition graph of the MDP is connected and acyclic. 2. Each state in the MDP corresponds to a unique node in the tree. 3. There is a single root node from which every other node is 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 ij the transition probabilities between states s i and s j . The transition matrix P for an MDP with a tree-like structure is defined such that:p ij > 0 ifthere is an edge between s i and s j in the tree, and p ij = 0 otherwise.Moreover, for each non-root node s j , there exists exactly one s i such that p ij > 0, and s i is the unique parent of s j in the tree structure.To classify the two value iteration in Eq. 3 and Eq. 4, we denote the value given by Eq. 4 as Ṽ π h and the value given by Eq. 3 as V π h , thus, in tabular tree-like MDP with the reward of the entire trajectory which can be decomposed as r ⋆ ξ (ξ H ) = H h=1 r ⋆ h (s h , a h ), we have the following relationship:Ṽ π h = V π h + r ⋆ 1:h-1where r 1:h denotes Reward of the 1 ∼ h steps of a trajectory. We prove this relationship by mathematical induction.Initial case. Using the tree-like PbRL-MDP algorithm and the initial conditions of the Bellman equation, at the final step h = H, we haveEQUATIONInduction step. We now proved that ifṼ π h+1 = V π h+1 + r ⋆ 1:h holds, then Ṽ π h = V π h + r ⋆ 1:h-1 also holds.Since this tree-like MDP's policy π is fixed, it has only one path to arrive h th state (s h ), denoted as:EQUATIONBy applying conclusion, we observe that when h = 1Ṽ π 1 = V π 1 .Thus, we have proven that the for the tabular MDP and the reward of the entire trajectory can be decomposed asr ⋆ ξ (ξ H ) = H h=1 r ⋆ h (s h , a h ), V π1 in Eq. 3 and Eq. 4 are equivalent.Lemma B.2. For the tabular MDP and the reward of the entire trajectory can be decomposed asr ⋆ ξ (ξ H ) = H h=1 r ⋆ h (s h , a h ), V π 1 inEq. 5 and Ṽ π 1 in Eq.6 are equivalent.Proof. To classify the two value iteration in Eq. 5 and Eq. 6, we denote the value given by Eq. 5 as Ṽ π h and the value given by Eq. 6 as V π h , thus, in tabular tree-like MDP with the reward of the entire trajectory which can be decomposed as r ⋆ ξ (ξ H ) = H h=1 r ⋆ h (s h , a h ), we have the following relationship:Ṽ π h = V π h + r ⋆ 1:h-1where r 1:h denotes Reward of the 1 ∼ h steps of a trajectory. Now, We prove this relationship.Since this tree-like MDP's policy π is fixed, it has only one path to arrive h th state (s h ), denoted as:EQUATIONBy applying conclusion, we observe that when h = 1Ṽ π 1 = V π 1 .Thus, we have proven that the for the tabular MDP and the reward of the entire trajectory can be decomposed as r ⋆ ξ (ξ H ) = H h=1 r ⋆ h (s h , a h ), V π 1 in Eq. 5 and Ṽ π 1 in Eq.6 are equivalent.To explain the difference between nested and static risk measure, we present a simple example that demonstrates their characters. First, we construct a 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 = {S 1 , S 2,1 , S 2,2 , S 3,1 , S 3,2 , S 3,3 , S 3,4 }, where S 1 is the initial state.The policy space is Π = {π A , π B }. Both policy have have the same action in the first step (a 1 ) and second step (a 2 ), but have the different action in the third step (a 3 , a ′ 3 ). The reward functions are as follows. r(S 1 , a 1 ) = 0, r(S 2,1 , a 2 ) = 0.1, r(S 2,2 , a 2 ) = 0.2, r(S 3,1 , a 3 ) = 0.3, r(S 3,2 , a 3 ) = 0.2, r(S 3,3 , a 3 ) = 0.4, r(S 3,2 , a 3 ) = 0.5, r(S 3,1 , a ′ 3 ) = 0.6, r(S 3,2 , a ′3 ) = 0.2, r(S 3,3 , a ′ 3 ) = 0.4, r(S 3,2 , a ′ 3 ) = 0.2. The transition distributions are as follows. P (S 2,1 | S 1 , a 1 ) = 0.5, P (S 2,2 | S 1 , a 1 ) = 0.5,P (S 3,1 | S 2,1 , a 2 ) = 0.1, P (S 3,2 | S 2,1 , a 2 ) = 0.9, P (S 3,3 | S 2,2 , a 2 ) = 0.1, P (S 3,4 | S 2,2 , a 2 ) = 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 In this section, we present the full proof of Assumption 1's regret upper bound. The proof consists of parts.Lemma D.1. Reward confidence set construction. Fix δ ∈ (0, 1), with probability at least 1 -δ, for allEQUATIONwhereEQUATIONProof. This lemma can be proved by the direct application of Lemma G.5. Let X t = (ξ t,1 , ξ t,2 ) and Y t = o t , andF r,t = {f r |f r (•, •) = σ(r(•) -r(•))}. Then, we have that X t is F t-1 measurable and Y t is F t measurable. According to Hoeffding's inequality (Theorem G.8) , {Y t -f r (X t )} is 1 2 -sub-gaussian conditioning, and E [Y t -f r (X t ) | F t-1 ] = 0. By Lemma G.5 and G.4 , since the linear trajectory embedding function ϕ : Z H → R dim T , with probability at least 1 -δ, we haveEQUATION)Lemma D.2. Reward estimation error of trajectory embedding. For any k ∈ [0, . . . , K], reward confidence set B r k , where the reward function embedding weight can be noted as w r = (w 1 , . . . , w dim T ), any fixed trajectory ξ H ∈ Z H , trajectory embedding ϕ(ξ H ) = (ϕ 1 , . . . , ϕ dim T ), with probability at least 1 -δ, it holds that,EQUATION)where n ξ,k denotes the number of times ξ H was visted up to episode k.Proof. According to Lemma D.1 and the assumption of link function, for fixed k ∈ [0, . . . , K], and d ∈ [0, . . . , dim T ] , we have,EQUATIONWheren dim,k (d) denotes the number of ϕ d (ξ H ) ̸ = 0 among 1 ∼ k episode's trajectory.Using Cauchy-Schwarz inequality and Lemma G.6, we have,EQUATION)Lemma D.3. Reward estimation error of the whole distribution.EQUATIONLemma D.4. Transition estimation error of fixed state action pair.For any fixed k, with probability at least 1 -2δ, for any (s, a) ∈ S × A.s ′ ∈S Pk (s ′ | s, a) -P ⋆ (s ′ | s, a) ≤ 2S log 2KHSA δ n k (s, a)Proof. The proof is same as Eq. ( 55) in Zanette & Brunskill (2019).Lemma D.5. Transition estimation error of whole distribution.For any fixed k, with probability at least 1 -δ, for any (s, a) ∈ S × A , excuted policy π 1 , π 2 ∈ Π k and any transition possibility kernelEQUATIONProof. The proof is same as Lemma. A.5 in Chen et al. (2022) .Lemma D.6. For any iteration value V : S → R , any two transition possibility kernel P, P : S × S × A → , and the risk aware object form:EQUATIONEQUATIONProof. We firstly sort all successor states s ′ ∈ S by V (s ′ ) in ascending order (from the left to the right) as s ′ 1 , s ′ 2 . . . s ′ S . And we assume that V (s ′ S+1 = 1) . Thus, according to the quantile function's definition,EQUATIONThe second to fourth lines follow the discussion on 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 we use the emperical estimation Pk of the transaction kernel P ⋆ ,EQUATION)Lemma D.7. Concentration for V.With probability at least 1 -2δ, it holds that, for any k ∈ [K], (s, a) ∈ S × A, any transition possibility kernel P 1 ∈ B P k and function V : S → [0, H],EQUATIONHere n k (s, a) is the number of times (s, a) was visited up to episode k.Proof. According to Lemma D.4 and recall the definition of the transition possibility confidence set, with probability at least 1 -2δ,EQUATION(49)EQUATIONPlugging Lemma .D.6, we obtain that with probability at least 1-2δ, for any k ∈ [K], (s, a) ∈ S ×A and function V : S → [0, H],EQUATIONRecall the definition of quantile function Φ, G is the quantile CDF weight. Given any target value V : S → R, we use β G,V P ⋆ (s ′ | s, a) denotes the conditional probability of transitioning to s ′ from (s, a), conditioning on transitioning to the quantile distribution, and it holds thatEQUATIONLemma D.8. Quantile Reward Gap due to Value Function Shift. For any (s, a) ∈ S × A, distribution P, and functions V, V ′ : S → [0, H], for any s ′ ∈ S,EQUATIONThis Lemma's proof is similar to Lemma 11 in Du et al. (2022) .Lemma D.9. For any (s, a) ∈ S × A, distribution P, and functions V, V ′ : S → [0, H], for any s ′ ∈ S,Φ s ′ ∼P(•|s,a) (V ′ (s ′ )) -Φ s ′ ∼P(•|s,a) (V (s ′ )) ≤ L G P(• | s, a) ⊤ |V ′ -V | (55)Proof. This Lemma comes from Lemma .D.8 and EQUATIONPr n k (s, a) ≥ 1 2 k-1 k ′ =1 H h=1 p k ′ h (s, a) -H log HSA δ , ∀k > 0, ∀(s, a) ∈ S × A ≥ 1 -δThis Lemma is a direct application of Lemma G.9 and same as Du et al. (2022) .Prn dim,k (d) ≥ 1 2 k-1 k ′ =1 p dim,k ′ (ξ H ) -log dim T δ , ∀d ∈ [0, . . . , dim T ] ≥ 1 -δProof. This Lemma a direct application of G.9. For any dimension d ∈ [0, . . . , dim T ], it holds thatPr n dim,k (d) ≥ 1 2 k-1 k ′ =1 p dim,k ′ (ξ H ) -log 1 δ ≥ 1 -δ Since d ∈ [0, . . . , dim T ], Therefore, Pr n dim,k (d) ≥ 1 2 k-1 k ′ =1 p dim,k ′ (ξ H ) -log dim T δ , d ∈ [0, . . . , dim T ] ≥ 1 -δDefinition of sufficient state-action visitations.Following Zanette & Brunskill (2019), for any episode k > 0, we define the set of state-action pairs which have sufficient visitations in expectation as follows.L k := (s, a) ∈ S × A : 1 4 k-1 k ′ =1 H h=1 p k ′ h (s, a) ≥ H log HSA δ + HDefinition of sufficient trajetory visitations. Following Zanette & Brunskill (2019), for any episode k > 0, we define the set of trajrctory dimension which have sufficient visitations in expectation as follows.L dim,k := d ∈ [0, . . . , dim T ] : 1 4 k-1 k ′ =1 p dim,k ′ (d) ≥ log dim T δ + 1We use n dim,k (d) to denote the number of ϕ d (ξ H ) ̸ = 0 among 1 ∼ k episode's trajectory. Lemma D.12. (Standard state action visitation ratio). For any K > 0, we haveK k=1 H h=1 (s,a)∈L k p kh (s, a) n k (s, a) ≤ 2 SA log KHSA δ .This proof is the same as that of Lemma 13 in Zanette & Brunskill (2019). Lemma D.13. (Standard trajectory visitation ratio). For any K > 0, we haveK k=1 dim T d=1 p dim,k (d) n dim,k (d) ) ≤ 2 dim T log Kdim T δ .This proof is the same as that of Lemma 13 in Zanette & Brunskill (2019). Lemma D.14. (Standard Invisitation Ratio). For any K > 0, we have For any K > 0, we haveK k=1 d / ∈L d,k p dim,k (d) < min π,d:p dim,π (d)>0 p dim,π (d) • 4 log dim T δ + 5This proof is the same as that of Lemma 10 in Du et al. (2022) . Lemma D.16. For any functions V :S → R, k > 0, h ∈ [H] and (s, a) ∈ S × A such that p kh (s, a) > 0, p G,V kh (s, a) p kh (s, a) ≤ 1 min π,h,(s,a):w π,h (s,a)>0 w π,h (s, a), where p G,V kh (s, a) denotes the conditional probability of visiting (s, a) at step h of episode k, conditioning on transitioning distortion by the quantion function G which works on at each step h ′ = 1, . . . , h -1. Lemma D.17. For any functions V :S → R, k > 0, h ∈ [H], p G,V dim,k (d) p dim,k (d) ≤ 1 min p π (d),where p G,V dim,k (d) denotes the conditional probability of ϕ d (ξ H ) ̸ = 0 of episode k, conditioning on transitioning distortion by the quantion function G which always works on at each step h = 1, . . . , H.The proof is similar to Lemma .D.16.Lemma D.18. For a probability of 1 -2δ, it holds that π ⋆ ∈ Π k , which is calculated as follows:Π k = {π | max r ξ ∈B r k ,P∈B P k ( Ṽ π 1,r ξ ,P (ξ h ) -Ṽ π0 1,r ξ ,P (ξ h )) ≥ 0, ∀π 0 } (59)Proof. It equals to for any policy π 0 ∈ Π, maxEQUATIONAccording to Lemma D.1 and Lemma D.4, with at least possibility 1 -2δ, it holds that:r ⋆ ξ ∈ B r k , P ⋆ ∈ B P k (61) Thus, max r ξ ∈B r k ,P∈B P k ( Ṽ π ⋆ 1,r ξ ,P (ξ h ) -Ṽ π0 1,r ξ ,P (ξ h )) (62) ≥ Ṽ π ⋆ 1,r ξ ,P (ξ h ) -Ṽ π0 1,r ξ ,P (ξ h ) ≥ 0 (63)Where the last equation comes from the definition of optimal policy π ⋆ (Eq. 7).Lemma D.19. Given a positive constant δ ∈ (0, 1], with probability at least 1 -4Kδ, we have the following inequality holds:Reg nested (K) (64) ⩽ max r1∈B r k ,P1∈B P k { Ṽ π ⋆ 1,r ⋆ ,P ⋆ (s k,1 ) -Ṽ π1 1,r ⋆ ,P ⋆ (s k,1 ) -( Ṽ π ⋆ 1,r1,P1 (s k,1 ) -Ṽ π1 1,r1,P1 (s k,1 ))} (65) + max r2∈B r k ,P2∈B P k { Ṽ π ⋆ 1,r ⋆ ,P ⋆ (s k,1 ) -Ṽ π2 1,r ⋆ ,P ⋆ (s k,1 ) -( Ṽ π ⋆ 1,r2,P2 (s k,1 ) -Ṽ π2 1,r2,P2 (s k,1 ))} (66)Proof.Reg(K) = K k=1 Ṽ π ⋆ 1,r ⋆ ,P ⋆ (s k,1 ) -Ṽ π1 1,r ⋆ ,P ⋆ (s k,1 ) + Ṽ π ⋆ 1,r ⋆ ,P ⋆ (s k,1 ) -Ṽ π2 1,r ⋆ ,P ⋆ (s k,1 ) (67) = K k=1 max r1∈B r k ,P1∈B P k ( Ṽ π ⋆ 1,r1,P1 (s k,1 ) -Ṽ π1 1,r1,P1 (s k,1 )) (68) + Ṽ π ⋆ 1,r ⋆ ,P ⋆ (s k,1 ) -Ṽ π1 1,r ⋆ ,P ⋆ (s k,1 ) - max r1∈B r k ,P1∈B P k ( Ṽ π ⋆ 1,r1,P1 (s k,1 ) -Ṽ π1 1,r1,P1 (s k,1 )) (69) + K k=1 max r2∈B r k ,P2∈B P k ( Ṽ π ⋆ 1,r2,P2 (s k,1 ) -Ṽ π2 1,r2,P2 (s k,1 )) (70) + Ṽ π ⋆ 1,r ⋆ ,P ⋆ (s k,1 ) -Ṽ π2 1,r ⋆ ,P ⋆ (s k,1 ) - max r2∈B r k ,P2∈B P k ( Ṽ π ⋆ 1,r2,P2 (s k,1 ) -Ṽ π2 1,r2,P2 (s k,1 )) (71) a ≤ Ṽ π ⋆ 1,r ⋆ ,P ⋆ (s k,1 ) -Ṽ π1 1,r ⋆ ,P ⋆ (s k,1 ) - max r1∈B r k ,P1∈B P k ( Ṽ π ⋆ 1,r1,P1 (s k,1 ) -Ṽ π1 1,r1,P1 (s k,1 )) (72) + Ṽ π ⋆ 1,r ⋆ ,P ⋆ (s k,1 ) -Ṽ π2 1,r ⋆ ,P ⋆ (s k,1 ) - max r2∈B r k ,P2∈B P k ( Ṽ π ⋆ 1,r2,P2 (s k,1 ) -Ṽ π2 1,r2,P2 (s k,1 )) (73) b ≤ max r1∈B r k ,P1∈B P k { Ṽ π ⋆ 1,r ⋆ ,P ⋆ (s k,1 ) -Ṽ π1 1,r ⋆ ,P ⋆ (s k,1 ) -( Ṽ π ⋆ 1,r1,P1 (s k,1 ) -Ṽ π1 1,r1,P1 (s k,1 ))} (74) + max r2∈B r k ,P2∈B P k { Ṽ π ⋆ 1,r ⋆ ,P ⋆ (s k,1 ) -Ṽ π2 1,r ⋆ ,P ⋆ (s k,1 ) -( Ṽ π ⋆ 1,r2,P2 (s k,1 ) -Ṽ π2 1,r2,P2 (s k,1 ))} (75)Where (a) comes from the definition of the optimal policy confidence set (Lemma D.18) when π ⋆ ∈ Π k at each episode , (b) derives from the characters of max value.Lemma D.20. Nested regret upper bound. Given a positive constant δ ∈ (0, 1], with probability at least 1 -δ, we have the following inequality holds for every k ∈EQUATIONProof. We use V π,h 1,r ⋆ ,p (s k,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 π from the MDP with the true transition kernal P ⋆ . Therefore, Here (a) is due to Lemma D.7 and D.8. (b) comes from that p CV aR,α,V π k kh (s, a) is defined as the probability of visiting (s, a) at step h of episode k under the conditional transition probabilityβ α,V π k h ′ +1 (• | •, •) for each step h ′ = 1, . . . , h -1.Firstly, we analyze the term I 1 and I 5 . Recall that for any policy π, h ∈ [H] and (s, a) ∈ S × A, w π,h (s, a) and w π,h (s) denote th probabilities of visiting (s, a) and s at step h under policy π, respectively. Thus, we have:EQUATIONHere (a) is due to Cauchy-Schwartz inequality and the fact that for any k > 0 and h ∈ [H],(s,a)∈S×A p CVaR,α,V π k kh (s, a) = 1. (b) comes from Lemma D.16. (c) uses Lemma D.12 and the fact that for any deterministic policy π, h ∈ [H] and (s, a) ∈ S × A, we have either w π,h (s, a) = w π,h (s) or w π,h (s, a) = 0, and thus min π,h,(s,a):w π,h (s,a)>0 w π,h (s, a) = min π,h,s:w π,h (s)>0 w π,h (s).For the term I 2 and I 6 , using Lemma D.14, we have:K k=1 H h=1   (s,a) / ∈L k p G,V π r ⋆ ,P ⋆ k,h (s, a)H   (84) ≤ 1 min π,h,s:w π,h (s)>0 w π,h (s) 8SAH 2 log HSA δ + 10SAH 2 (85)For the term I 3 and I 7 , we have:EQUATIONp π k dim,K (d) • I(p π k dim,K (d) ̸ = 0) (90) d ≤ 2B κb dim T log Kdim T δ log K (1 + 2Bρ w ) δ 1 minω π (d) (91)Here (a) is due to Cauchy-Schwartz inequality. (b) comes from Lemma D.17. (c) uses Lemma D.15.For the term I 4 and I 8 , using Lemma D.15, we have:K k=1   (d / ∈L dim,k p G,V π k r ⋆ ,P ⋆ dim,k (d)B   (92) ≤ min π,d:p π,dim (d)>0 p π,dim (d) • 4 log dim T δ + 5 (93)Then, summing all the term, we have: Reg static (K)EQUATIONEQUATIONProof. We use V π,h 1,r ⋆ ,p (s k,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 π from the MDP with the true transition kernal P ⋆ . Therefore,EQUATIONEQUATIONEQUATIONEQUATIONE Lower bound of the regret. There exists an instance of Nested CVaR RL-RM, where the regret of any algorithm is at least:S 1 S 2 ⋯ S n-1 S n x 2 x 3 x 1 μ μ μ μ 1 -3μ 1 -μ 1 -μ 1 -α α Reward = 1 Reward = 0.8 Reward = 0.2 μ μ π ⋆ (a) optimal policy S 1 S 2 ⋯ S n-1 S n x 2 x 3 x 1 μ μ μ μ 1 -3μ 1 -μ 1 -μ α -η 1 -α + η Reward = 1 Reward = 0.8 Reward = 0.2 μ μ π ∈ Π\π ⋆ (b) sub optimal policyEQUATIONProof. Hard to learn case 1. Consider the instance shown in Figure 5 .The state space is defined as S = {s 1 , s 2 , . . . , s n , x 1 , x 2 , x 3 }, where s 1 is the initial state, and n = S -3 < S. We define the trajectory reward functions as follows: For anyξ H ∈ Z H , ϕ(ξ H ) = (I(S H (ξ H ) = x 1 )B, I(S H (ξ H ) = x 2 )B, I(S H (ξ H ) = x 3 )B), w r = (1ρ, 0.8ρ, 0.2ρ)The transition distributions are as follows. Let µ be a parameter which satisfies that 0< α < µ < 1 3 . For any a ∈ A, p (s 2 | s 1 , a) = µ, p (x 1 | s 1 , a) = 1 -3µ, p (x 2 | s 1 , a) = µ and p (x 3 | s 1 , a) = µ.For any i ∈ {2, . . . , n -1} and a ∈ A, p (s i+1 | s i , a) = µ and p (x 1 | s i , a) = 1 -µ.x 1 , x 2 and x 3 are absorbing states, i.e., for any a ∈ A, p (x 1 | x 1 , a) = 1, p (x 2 | x 2 , a) = 1 and p (x 3 | x 3 , a) = 1. p (x 2 | s n , a J ) = 1 -α + η and p (x 3 | s n , a J ) = α -η,where η is a parameter which satisfies 0 < η < α and will be chosen later. For any suboptimal action a ∈ A\ {a J } , p (x 2 | s n , a) = 1 -α and p (x 3 | s n , a) = α For any a j ∈ A, let E j [•] and Pr j [•] denote the expectation and probability operators under the instance with a J = a j . Let E unif [•] and Pr unif [•] denote the expectation and probability operators under the uniform instance.Fix an algorithm A. Let π k denote the policy taken by algorithm A in episode k. Let N sn,aj = K k=1 ⊮ π k (s n ) = a j denote the number of episodes that the policy chooses a j in state s n . Let V sn,aj denote the number of episodes that the algorithm A visits (s n , a j ). Let w (s n ) denote the probability of visiting s n in an episode (the probability of visiting s n is the same for all policies). Then, it holds thatE [V sn , a j ] = w (s n ) • E N sn,aj .According to the definition of nested-CVaR-PbRL risk objective in Eq. 4, we have:EQUATIONand summing over all episodes k ∈ [K], we haveEQUATIONEQUATIONTherefore, we haveEQUATIONEQUATIONFor any j ∈ {A, B}, using Pinsker's inequality and 0 < α < 1 3 , we have thatKL (p unif (s n , π j (s n )) ∥p j (s n , π j (s n ))) = KL(Ber(α)∥ Ber(α -η)) ≤ η 2 (α-η)(1-α+η) ≤ c1η 2 αfor some constant c 1 and small enough η. Then, using Lemma A. 1 in Du et al. (2022) , we have ,EQUATION≤ E unif N πj + K 2 w (s n ) • E unif N πj • c 1 η 2 α (112)Then, UsingA j=1 E unif N sn,aj = 2K and Cauchy-Schwarz inequality, we have:EQUATIONEQUATIONEQUATIONThus, we have :EQUATIONLet η = c 2 αA w(sn)K for a small enough constant c 2 . We haveE[R(K)] = Ω Bρ A α • w (s n ) K • K = Ω Bρ AK α • w (s n )Hard to learn case 2.The trajectory reward functions are as follows.For anyξ H ∈ Z H , ϕ(ξ H ) = (I(S H (ξ H ) = x 1 )B, I(S H (ξ H ) = x 2 )B, I(S H (ξ H ) = x 3 )B, I(S H (ξ H ) = x 4 )B), w r = (1ρ, 0.8ρ, 0.2ρ, (0.2 -η)ρ)The transition distributions are as follows. Let µ be a parameter which satisfies that 0 < α < µ < 1 3 . For any a ∈ A, p (s2 | s 1 , a) = µ, p (x 1 | s 1 , a) = 1 -3µ, p (x 2 | s 1 , a) = µ and p (x 3 | s 1 , a) = µ.For any i ∈ {2, . . . , n -1} and a ∈ A, p (s i+1 | s i , a) = µ and p (x 1 | s i , a) = 1 -µ.x 1 , x 2 and x 3 are absorbing states, i.e., for any a ∈ A, p ( According to the definition of nested-CVaR-PbRL risk objective in 4, we have:x 1 | x 1 , a) = 1, p (x 2 | x 2 , a) = 1 and p (x 3 | x 3 , a) = 1. S 1 S 2 ⋯ S n-1 S n x 2 x 3 x 1 μ μ μ μ 1 -3μ 1 -μ 1 -μ 1 -α α Reward = 1 Reward = 0.8 Reward = 0.2 μ μ π ⋆ (a) optimal policy S 1 S 2 ⋯ S n-1 S n x 2 x 4 x 1 μ μ μ μ 1 -3μ 1 -μ 1 -μ 1 -α α Reward = 1 Reward = 0.8 Reward = 0.2 -η μ μ π ∈ Π\π ⋆ (b) sub optimal policyEQUATIONThus,EQUATIONEQUATIONEQUATIONTherefore, we haveEQUATIONEQUATIONFor any j ∈ {A, B}, since the preference based on Bernoulli distribution, using Pinsker's inequality and 0 < α < 1 3 , we have that KL (p unif (s n , π j (s n ))∥p j (s n , π j (s n ))) = KL(Ber(α)∥ Ber(α - η)) ≤ η 2 (0.2-η)(0.8+η) ≤ c1η 20.16 for some constant c 1 and small enough η. Then, we have ,EQUATIONThen, UsingA j=1 E unif N sn,aj = 2K and Cauchy-Schwarz inequality, we have:EQUATIONEQUATIONEQUATIONThus, we have :EQUATION)Let η = c 2 0.16A w(d)K for a small enough constant c 2 . We haveEQUATIONF The optimal policy calculation for known PbRL MDPIn this section, we describe how to compute the optimal policy for the CVaR objective when the PbRL-MDP is known; this approach is described in detail in Bäuerle & Ott (2011) ; Bastani et al. (2022) . Following this work, we consider the setting where we are trying to minimize cost rather than maximize reward. In particular, consider an know PbRL MDP M(S, A, r ⋆ ξ , P ⋆ , H), where S and A, and our goal is to compute a policy π that maximizes its CVaR objective. Lemma F.1. CVaR definition. For any random variable Z, we haveCVaR α (Z) = sup ρ∈R ρ - 1 α • E Z (ρ -Z) + ,where the minimum is achieved by ρ * = VaR α (Z).Since the optimal policy for static CVaR object satisfies:EQUATIONAs a consequence of Lemma F.1, we haveEQUATIONThus, the optimal policy is:EQUATIONwhereEQUATION)Value iteration. we reconstruct the MDP as enlarge the state space sh = (ξ h , ρ), where ρ will work as a quantile value. Letting S 1 be the initial state of the original PbRL MDP M .We iterate the value and calculate the policy as follows:EQUATIONEQUATIONThen, given an initial state s 1 , we construct state ℑ 1 = (s 1 , -ρ * ), whereρ * = argsup ρ∈R ρ - 1 α • V (π) 1 ((s 1 , -ρ)) ,and then acting optimally in M.According to Eq. 4, nested CVaR object could directly use the Bellman equation to iterate the value.Value iteration. we reconstruct the MDP as enlarge the state space sh = (ξ h , ρ), where ρ will work as a quantile value. Letting S 1 be the initial state of the original PbRL MDP M .We iterate the value and calculate the policy as follows:EQUATIONthen acting optimally in M.Definition G.1. α-dependence in Russo & Van Roy (2013). For α > 0 and function class Z whose elements are with domain X , an element x ∈ X is α-dependent on the set .X n := {x 1 , x 2 , • • • , x n } ⊂ X with respect to Z, if any pair of functions z, z ′ ∈ Z with n i=1 (z (x i ) -z ′ (x i )) 2 ⩽ α satisfies z(x) -z ′ (x) ⩽ α. Otherwise, x is α-independent on X n ifLet (X p , Y p ) p=1,2,... be a sequence of random elements, X p ∈ X for some measurable set X and Y p ∈ R. Let F be a subset of the set of real-valued measurable functions with domain X. Let F = (F p ) p=0,1,••• be a filtration such that for all p ≥ 1, (X1 , Y 1 , • • • , X p-1 , Y p-1 , X p ) is F p-1measurable and such that there exists some functionf ⋆ ∈ F such that E [Y p | F p-1 ] = f * (X p )holds for all p ≥ 1. The (nonlinear) least square predictor given(X 1 , Y 1 , • • • , X t , Y t ) is ft = argmin f ∈F t p=1 (f (X p ) -Y p ) 2 .We say that Z is conditionally ρ-subgaussion given the σ-algebraEQUATION)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 C > 0. Assume that for each s ≥ 1, (Y p -f * (X p )) is conditionally σ-subgaussian given F p-1 . Then, for any α > 0, with probability 1 -δ, for all t ≥ 1, f * ∈ F t (β t (δ, α)), whereβ t (δ, α) = 8σ 2 log (2N α /δ) + 4tα C + σ 2 log(4t(t + 1)/δ) .Lemma G.6. (Lemma 5 of Russo & Van Roy ( 2013)). Let F ∈ B ∞ (X, C) be a set of functions bounded by C > 0, (F t ) t≥1 and (x t ) t≥1 be sequences such that F t ⊂ F and x t ∈ X hold for t ≥ 1. Let F| x1:t = {(f (x 1 ) , . . . , f (x t )) : f ∈ F} (⊂ R t ) and for S ⊂ R t , let diam(S) = sup u,v∈S ∥u -v∥ 2 be the diameter of S. Then, for any T ≥ 1 and α > 0 it, holds that := f ∈ F : f -f LS t 2,Et ≤ √ β t , where f LS t ∈ arg min f ∈F L 2,t (f ) and L 2,t (f ) = t-1 1 (f (A t ) -R t ) 2 , then for all T ∈ N and ϵ > 0, T t=1 1 (w Ft (A t ) > ϵ) ≤ 4β T ϵ 2 + 1 dim E (F, ϵ)where w F (a) := sup f ∈F f (a) -inf f ∈F f (a) denotes confidence interval widths. Theorem G.8. Hoeffding's inequality (Hoeffding, 1994) . Let X 1 , X 2 , . . . , X n be independent random variables that are sub-Gaussian with parameter σ. Define S n = n i=1 X i . Then, for any t > 0, Hoeffding's inequality provides an upper bound on the tail probabilities of S n , which is given by:Pr (|S n -E[S n ]| ≥ t) ≤ 2 exp - t 2 2nσ 2 .This result emphasizes the robustness of the sum S n against deviations from its expected value, particularly useful in applications requiring high confidence in estimations from independent sub-Gaussian observations. Lemma G.9. (Lemma F.4. in Dann et al. (2017) ) Let F i for i = 1 . . . be a filtration and X 1 , . . . X n be a sequence of Bernoulli random variables with P (X i = 1 | F i-1 ) = P i with P i being F i-1measurable and X i being F i measurable. It holds that Justification: The paper discussed the limitations of the work in section 3.2, and section 6. Guidelines:P ∃n : n t=1 X t < n t=1 P t /2 -W ≤ e -W• 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 in 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 on 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - 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. 

- 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). 

- Previous works have studied RL under trajectory feedback, although not in the PbRL setting, see e.g., [4]. Therefore, contribution 3. seems overstated. 

[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.

[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.

[3] Tamar, A., Chow, Y., Ghavamzadeh, M., & Mannor, S. (2015). Policy gradient for coherent risk measures. Advances in neural information processing systems, 28.

[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).
questions: 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? 

- What does Assp. 3.1 formally say? How should it be interpreted and how restrictive is it? 

- 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? 

- Are the results from Sec. 3.2 novel - especially the recursions (5) and (6)? 

- 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.

*Minor comments and suggestions*

- Please follow the formatting guidelines for section titles - Secs. 2, 5
- line 58: "may not be applicable"; line 60: "cannot"
- line 125: "and the reward"; line 126: "the trajectory embedding dimension"
- Assp. 3.1: "We" - capital letter
- line 133: " At each iteration"; line 134: "unlike standard RL"; line 137: "a Bernoulli distribution"
- lines 139-140: "It is aware" --> "It is known" or "We are aware that"; line 157: "risk-measures"
- line 160: "a random variable" (remove distribution); line 161: "then" --> "so"
- line 163: What is $Z$? Should it be $X$?
- line 176: "denotes the"
- lines 178-179: Reformulate "the policy should be history-dependent policies"
- line 185: "The proof is"
- Lemma 3.5 and 3.6: "For a tabular MDP and a reward of the entire trajectory being decomposable as ..."
- line 191: "given the current history" 
- line 199: "The proof is"
- line 207: "We define"
- line 211: "regardless of iterated or accumulated"
- line 214: "of the entire episode training"
- line 218: "that minimizes regret"
- lines 221-22: "We present the algorithm called RA-PbRL and establish and upper-bound regret for it"
- line 225: Remove "The algorithm"; "defined" --> "described" or "presented"; "which main part"
- line 229: "choose a policy"; line 232: "find an estimated optimal policy"
- line 236: "we initialize"; line 237: "we observe history samples"; line 239: "use" (present)
- Algo 1, line 9: "Receive trajectory ... and preference"; line 10: italic $k$
- lines 253, 254: "with policy $\pi$" - remove "the"
- line 274: "hard-to-learn constructions" (hyphen and "s")
- lines 275-6: "are unavoidable in some cases"
- line 282: "For a comparative analysis"; line 286: "aligned ... with RA-PbRL"
limitations: limitations: Although some limitations are not addressed in this work (see previous remarks), most are properly described in Sec 6.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- 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?
questions: questions: See above.
limitations: limitations: None.
paper_summary: paper_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.

Additionally, the paper presents an algorithm (RA-PbRL) to incorporate these objectives into PbRL.

Lastly, the authors provide regret boundaries for both iterative and accumulated quantile risk objectives with RA-PbRL.
strength_weakness: strength_weakness: *  **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.
 *  **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.
questions: 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: limitations: The limitations have been correctly addressed.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1.	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 on how to implement this algorithm?
2.	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.
3.	It 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?
4.	This 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 …”?
questions: questions: Please see the weaknesses above.
limitations: limitations: Please see the weaknesses above.

Comments: title: Thank you
Thank the authors for their response
comment: Thank you for acknowledging our response. We are glad to know our explanation addressed your questions.
Thank you for acknowledging our rebuttal. We are glad to know that we addressed all your concerns.
Thank you for addressing all of my concerns and answering my questions. I  raise my score to 6
Thank you for your responses.

Yes, it is indeed Fig. 1(a) and 2(a). Your explanation makes sense.

I will maintain my score.
We want to express our gratitude once again for your valuable feedback. Since the discussion period is coming to a close, we would be grateful if you could share any additional thoughts you may have about our rebuttal. Thank you for your time.
We want to express our gratitude once again for your valuable feedback. Since the discussion period is coming to a close, we would be grateful if you could share any additional thoughts you may have about our rebuttal. Thank you for your time.
Thank you for acknowledging our response and updating the score. We appreciate your time and efforts.
Thank you for acknowledging our response. We would like to check if our rebuttal addressed the raised concerns. We are happy to address any specific questions remaining.
I thank the authors for their detailed rebuttal and extended experiments. Since authors adequately addressed all my questions and concerns I will raise my score to a 7.
Thank the authors for their response. I tend to maintain my score.