Provably Efficient Iterated CVaR Reinforcement Learning with Function Approximation and Human Feedback

Weakness

The technical aspects of the algorithms appear somewhat limited and are relatively standard in the literature. Additionally, the algorithms are not efficient, and obtaining a solution for the approximate CVaR operator is not easy.

We appreciate your comments on the technical aspects and efficiency of our algorithms. In our paper, we propose several novel techniques in designing and analyzing sample-efficient algorithms for ICVaR-RL with function approximation and human feedback. We would like to emphasize several novel contributions that enhance the technical depth and uniqueness of our work.

1. Efficient Approximation of CVaR Operator (Section 4.1): In this paper, we introduce a pioneering method for approximating the CVaR operator with provably bounded error and polynomial computational complexity. Our theoretical analysis demonstrates that the maximum difference between the approximate and true operators is small. Further details on this contribution are provided in Section 4.1.
2. Novel transition estimation and concentration (Section 4.1): We present novel least-square estimation and ridge regression techniques with innovative regression features. These advancements provide the first efficient approximation of the transitions in ICVaR-RL with linear function approximation.
3. Novel elliptical potential lemma (Section 4.2): We introduce a novel elliptical potential lemma (the elliptical potential lemma is an important technical tool in studying RL with function approxiamtion) that achieves a sharper order $O(\log K)$ regret in terms of $K$ , improving the previous result $O(\sqrt{K})$ (Ayoub et al., 2020; Fei et al., 2021; Russo and Van Roy, 2014). We have detailed this novelty in Section 4.2.
4. Risk-sensitive RLHF(Section 5): We extend ICVaR-RL to encompass RLHF with general function approximation for both transition probabilities and reward modeling. This formulation represents the first for risk-sensitive RLHF. Furthermore, we introduce the first provably sample-efficient algorithm, ICVaR-HF, with a discretization approach for infinite reward function sets and a novel regret decomposition method to bridge the gap in the risk-sensitive value function. These advancements are detailed in the Section 5.

Regarding computational tractability, we would like to clarify that ICVaR-L with approximate CVaR operator only has polynomial complexity. A detailed analysis of computation and space complexity is presented in the "Computation Efficiency" paragraph on page 5.

We believe these technical contributions significantly enhance the efficiency of our algorithms and provide brand-new technical tools for risk-sensitive RL with function approximation and human feedback. Thank you for your valuable feedback.

Question

1. On page 2, in the first bullet, $\sqrt{\alpha^{-H}} \to \sqrt{\alpha^{-2}}$.

Actually, this is not a typo. It is to show that the exponential term $\sqrt{\alpha^{-H}}$ in the regret bound is unavoidable.

2. On page 8, it should be $\sigma(x)$ in regularity.

We are not sure we fully understand your question. If you meant that we should assume $\sigma(x)$ is regular, we do assume that the link function $\sigma$ has the properties of "Regularity" in Assumption 4. If you have further questions, please do not hesitate to let us know.

3. What is $\tilde\sigma$ in equation (14)?

$\tilde\sigma$ is formally defined in equation (14). This notation is introduced to simplify the log-likelihodd function $\mathcal{L}_k(r)$, and make the proof clear.

4. Compared with the tabular setting, why the linear case has a bad dependence on H?

In the linear case, the bad dependence on $H$ is a shared characteristic with previous works in RL with linear function approximation (Jin et al., 2020, Zhou et al., 2021a, Zhou et al., 2021b). Unlike the tabular setting where the transition distribution is estimated by the sample-mean empirical probability directly, we use ridge regression for estimating the transition parameter in the linear case, which relies on the construction of regression feature corresponding to the value function within the range $[0, H]$. This design choice introduces an additional regret cost associated with $H$.

Improving the $H$ term in linear function approximation is an interesting topic, and is a topic of our future research.

---

We sincerely thank the reviewer for the invaluable feedback. Should our response effectively address your concerns, we kindly hope that you could consider raising the score rating for our work. We will also be happy to address any additional queries or points.

Weakness

While I typically do not complain about the empirical results of this paper, I do expect that some implemented results on real-world practical problems could be contained in this paper.

We acknowledge the importance of practical validation through experimentation to underline the significance and verify the efficiency of our proposed algorithms. In our revision, we have addressed this concern by including numerical experiments in Appendix C. We compare our sample and computation effiticent algorithm ICVaR-L with two close baselines: LSVI (Zhou et al., 2021b) for risk-neutral Linear RL and ICVaR-VI (Du et al., 2023) for ICVaR-RL in tabular MDPs.

The results are presented in Figure 1 and 2 (Appendix C in our revision). As depicted in Figure 1 and 2, ICVaR-L consistently exhibits a sublinear regret with respect to the number of episodes, validating our theoretical result in Theorem 1. Comparing ICVaR-L with the tabular algorithm ICVaR-VI, our algorithm demonstrates faster learning of the optimal risk-sensitive policy, highlighting its efficiency in ICVaR-RL with linear function approximation. Furthermore, LSVI exhibits nearly linear regret with the number of episodes, indicating its struggle to learn the optimal risk-sensitive policy.

These experimental evidences demonstrate the efficiency of ICVaR-L in risk-sensitive linear RL scenarios, providing empirical support for its theoretical advancements.

---

We sincerely thank the reviewer for the invaluable feedback. Should our response effectively address your concerns, we kindly hope that you could consider raising the score rating for our work. We will also be happy to address any additional queries or points.

Weakness 1

1. In the first paragraph on page 2, the paper introduces two proposed algorithms but fails to sufficiently detail how these tools embody and implement the ICVaR concept. This lack of substance makes the uniqueness and contribution of your algorithms unclear.

To maintain the readability of the introduction section, in this paragraph, we only briefly mention our algorithms ICVaR-L and ICVaR-G, as an introduction to the contribution of our paper, and defer the in-depth details for handling the Iterated CVaR concept to Section 4.

We agree with you that this could be made more explicit. Thus, we have revised the introduction to include pointers that guide readers to the detailed discussion in Section 4.

We believe this modification strikes a balance between maintaining readability of the introduction section and ensuring that readers access the necessary details in the corresponding sections. We hope this adjustment addresses your concern effectively.

2. The main argument presented in the second paragraph on page 2 is confusing. It's unclear whether the intention is to highlight the importance of integrating human feedback, with LLM as a successful example of this, or to underline the significance of risk-sensitive RL, with ChatGPT as an example.

In the second paragraph on page 2, we use the example of LLM, specifically ChatGPT, to illustrate the practical relevance of risk-sensitive measures in Reinforcement Learning with Human Feedback (RLHF). Our intention is twofold. Firstly, we use it to underscore the importance of RLHFs, highlighting the practical efficacy of this approach. Secondly, we aim to emphasize the relevance of risk-sensitive RLHF, using ChatGPT as an example to illustrate the necessity of managing risks in RLHF.

Regarding the statement, 'LLMs operate in diverse conversational landscapes, where defining reward signals unequivocally is challenging,' the relevance lies in demonstrating the difficulty of defining explicit reward signals in environments where LLMs operate, which necessitates the use of human feedback oracles in LLM problems (Glaese et al., 2022; Lee et al., 2023) . For instance, in the case of LLM, providing exact reward values for each response is challenging due to the nuanced and diverse nature of conversational landscapes. Consequently, researchers resort to human feedback oracles to gain a better understanding of the underlying reward dynamics and to enhance the performance of LLMs (Ouyang et al., 2022; Gulcehre et al., 2023).

In response to your feedback, we have revised this paragraph to clearly express our intention and motivation. We believe these examples about LLMs effectively illustrate the practical significance of risk-sensitive RLHF, and we hope this clarification and our revision effectively address your concerns.

3. The third paragraph on page 2 attempts to give an outline of the key challenges in theoretical analysis for ICVaR algorithms with function approximation and human feedback. However, critical concepts and symbols which outline these challenges are not adequately defined or explained, which hinders the comprehension of arguments. For instance, without further context or clarification, the term "key elliptical potential lemma" remains obscure to readers. Moreover, the majority of the "challenges" outlined are essentially highlighting that current proof techniques and results cannot be seamlessly applied to your problem setting. However, there's a lack of explanation rooted in the problem's inherent characteristics.

In the third paragraph of the Introduction section, we outline the key challenges in designing and analyzing ICVaR-RL with function approximation and human feedback. To facilitate reading of the Introduction, we only present a high-level summary of these challenges, with detailed explanations provided in subsequent sections.

These challenges are deeply rooted in the inherent characteristics of the problem and cannot be addressed through the straightforward application of existing techniques. For instance, ICVaR-RL poses inherent difficulties due to the distortion of the distribution of every transition by the CVaR measure, disrupting the linearity of the risk-neutral Bellman Equation. Additionally, when dealing with a large or even infinite state space, efficient computation of the CVaR operator becomes impossible. These difficulties are fundamental to the problem and go beyond the limitations of previous techniques, highlighting the necessity for novel approaches to address these intrinsic difficulties.

In response to your concerns, we have refined this paragraph by providing a more accessible overview to ensure the key challenges are effectively conveyed. Please refer to the third paragraph in page 2 of the revision.

Dear wJB8,

The author reviewer discussion period is ending soon this Wed. Does the author response clear your concerns w.r.t. presentation and intuition, or there are still outstanding items that you would like more discussion?

Thanks again for your service to the community.

Best,
AC

Dear Reviewer wJB8,

As the author reviewer discussion period is ending soon, we sincerely thank you for the invaluable feedback. Should our response effectively address your concerns, we kindly hope that you could consider raising the score rating for our work. We will also be happy to address any additional queries or points.

Best regards, Authors