Response to Reviewer cCx6

Thank you for your strong support!

Q1 In the claim of achieving logarithm regret (e.g. remark 4.2), it is better to explain it is because the optimal policy is the one that maximizes the KL-regularized objective, rather than standard objective (cumulative return)

A1 Thanks for reminding this point! We will add this to the revision and state that now our objective is the reward subtracted by the KL-regualrization and is different from the original RL objective. We focus on this objective because as stated in Lines 21-34 right, for post-training in large-sacle models, the trained policy should not move too far from the strong base policy. Otherwise, the "sloignment tax" arises.

Q2 Lack some (at least) simple experiments to demonstrate the proposed algorithm and validate the results.

A2 Since large scale experiments are beyond the scope of this theoretical work, we run simulations for our algorithm under a multi-armed linear contextual bandit. We use different values of KL-regularization parameter $\eta$ and arm number $K$. The results are provided at this anonymous link https://anonymous.4open.science/r/Simulation_KL_RLHF-C092/KL_reg_MDPs.pdf. Since the x-axis has logarithmic scale, the almost linear curve in the figures validates that the regret scales logarithmically with rounds $T$.

Response to Reviewer TRX2

Thank you for your strong support!

Q1 In page 4, it is stated that "Without loss of generality, we assume that the function class has finite cardinality" with a reference to a ~500 page book. How should the proof be modified to handle the infinite case? In order to make the claim that there is no loss in generality, I suggest adding an appendix section to at least state the exact regret bound in the infinite case and include a brief overview of how it could be obtained, with more detailed references.

A1 Thank you for your helpful suggestion! For the infinite case, we will assume that the function class has finite covering number. For each function $f\in\mathcal R$, there exists a cover function $f'$ belongs to the cover such that $f$ and $f'$ are close enough so that we can transform this problem into a finite class and take the uniform bound. Then, in the final regret bound, we just need to replace the class cardinality with the covering number. This analysis is standard in previous literature [1,2] and Chapter 4.6 of Zhang, 2023. We will provide the details in the revision.

[1] Zhao H, et al. Sharp analysis for kl-regularized contextual bandits and rlhf.

[2] Ye C, et al. Corruption-robust algorithms with uncertainty weighting for nonlinear contextual bandits and markov decision processes. ICML, 2023.

Response to Reviewer yuSc

Thank you very much for your strong support!

Q1 It would have been interesting to see computational resource considerations in the analysis of KL-LSVI. For example, in RLHF applications, reward models can be large-scale neural networks. In this case, optimizing a reward model at every episode could be very costly.

A1 Our work focuses on providing a general and standard online framework enjoying logarithmic regret bounds. The computational efficiency is indeed very important for larges-scale models. Hence, to improve efficiency in RLHF applications, it has been shown that low switching techniques [1,2,3] can solve this problem both emprirically and theoretically. Following the batch framework in [1], we can obtain the same sample complexity with $\Theta(d_{\mathcal R})$ number of batches.

Q2 It would be interesting to see generalizations of KL-LSVI to the setting where is a neural network, e.g. optimized via gradient descent during training. I would imagine Line 5 might be replaced e.g. by a stochastic gradient update. I wonder if there are any standard techniques that could be used to generalize this paper’s analysis to such an online SGD setting.

A2 In practice, a promising direction is Thompson Sampling (TS)-based exploration, which can be implemented using Stochastic Gradient Langevin Dynamics (SGLD) to introduce randomness into SGD for regression. SGLD enables implicit posterior sampling during training, potentially improving the balance between exploration and exploitation in the KL-regularized setting.

To extend the current theoretical analysis of KL-LSVI, one could explore whether existing regret bounds for Langevin-based exploration methods apply in this context. Notably, [4] shows that TS with a "feel-good" term achieves an optimal sample complexity bound comparable to UCB in contextual bandits with function approximation. Furthermore, [5] provides a comprehensive empirical study demonstrating the efficiency of TS in RL and the effectiveness of SGLD in approximating TS. We believe investigating sampling-based methods for KL-regularized objectives in RL is an interesting direction for future work.

Q3 I believe it would have been helpful if, when referencing “standard techniques” (e.g. lines 368-369), the authors would have provided specific citations or references to pin down which techniques exactly they have in mind.

A3 Thanks for the helpful suggestion! We will explain the standard techniques detailedly in the revision.

[1] Xiong W, et al. Iterative preference learning from human feedback: Bridging theory and practice for rlhf under kl-constraint. ICML, 2023.

[2] Bai, Y., et al. Training a helpful and harmless assistant with reinforcement learning from human feedback.

[3] Touvron, H., et al. Llama 2: Open foundation and fine-tuned chat models.

[4] Zhang, T. Feel-good thompson sampling for contextual bandits and reinforcement learning.

[5] Ishfaq, H., et al. Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo

Response to Reviewer SUKH

Thank you for your insightful comments! We address your questions as follows.

Q1 The two proposed algorithms are said to achieve regret bounds that scale logarithmically with the number of rounds, T. To support these claims, empirical validations should be conducted in real-world Reinforcement Learning from Human Feedback (RLHF) experiments to provide valuable insights. It is curious whether any empirical validations related could be provided.

A1: Thanks for the point. We would like to clarify that the main focus of this project is to understand the statistical limit of the online decision making under the KL-regularized objective. Past experience suggests these understandings can be effectively connected to the downstream real-world algorithmic designs in principle, though with certain heuristic approximation to overcome the gap between the theoretical side and the empirical side. Even in the RLHF literature, we notice that the theoretical advantage of iterative RLHF/DPO was first established in [1] and then its empirical recipe is presented in [2, 3] and became standard practice in the past year. The idea of pessimism was established in [4], and empirical community construct reward model with uncertainty penalization to mitigate the reward hacking issue [5].

We hope that the insights from this work can motivate a comprehensive study with real-world experiments for future work, which is beyond the scope of this work. Meanwhile, a direct validation of the faster rate with real-world experiments is also not feasible since we have no access to the groud-truth reward.

However, we agree that empirical study can help to make the study complete. Therefore, we conduct some simulated experiments under controllable synthetic environment. Specifically, we run simulations for our algorithm under a multi-armed linear contextual bandit and different values of KL-regularization parameter $\eta$. The result provided at this anonymous link https://anonymous.4open.science/r/Simulation_KL_RLHF-C092/KL_reg_MDPs.pdf validates that the regret scale logarithmically with rounds $T$.

Q2 Both algorithms include bonus terms, specifically a constant value of 1 found in equations (3) and (9). How does the constant affect the uncertainty associated with this bonus and the reward function? Additionally, is it possible to explore other potential bonus terms that could be utilized within these two algorithms?

A2: Thanks for the questions. The central idea here is that we should use an optimistically biased objective to facilitate exploration of the underlying space, where adding an uncertainty bonus is one of the most common approach in the literature. The upper bound of the bonus may be very large compared to the range of the reward, so we usually truncate the bonus by $1$.

From the theoretical perspective, which is also the main focus of our paper, such as bonus should ensure the estimator is an upper bound of the true parameter with high probability and is constructed mostly by the concentration inequality tool from the high-dimensional statistics, where the constants are determined accordingly to satisfy this goal. Meanwhile, any potential bonus that satisfies this condition is valid but we usually take the sharpest estimation for a better theoretical results.

When we move to the practical side, we typically resort to heuristic approximation of the bonus and apply the theoretical insights in principle. For instance, a common way is to use the ensemble method to incorporate the uncertainty into empirical experiments [5]. There are also alternative ways that can be used as "potential bonus" like using a optimistically biased loss function [6, 7]. Nevertheless, the empirical results in these works consistently show that taking uncertainty into consideration can largely improve the real-world performance of the algorithms.

[1] Xiong, W, et al. Iterative preference learning from human feedback: Bridging theory and practice for rlhf under kl-constraint. ICML, 2024.

[2] Guo, S, et al. Direct Language Model Alignment from Online AI Feedback. 2024.

[3] Dong, H, et al. RLHF Workflow: From Reward Modeling to Online RLHF. TMLR, 2024.

[4] Jin, Y, et al. Is pessimism provably efficient for offline rl? ICML, 2021.

[5] Coste, T, et al. Reward model ensembles help mitigate overoptimization. ICLR, 2024.

[6] Xie, T, et al. Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF. 2024.

[7] Liu, Z, et al. Provably mitigating overoptimization in rlhf: Your sft loss is implicitly an adversarial regularizer. NIPS, 2024.

Response to Reviewer b9cv

Thank you for your positive feedback! We answer your questions point-by-point.

Q1 After defining the eluder dimension and providing an example, the authors do not discuss it further. However, the overall regret bound is only logarithmic in $T$ if the eluder dimension is logarithmic in $T$. I understand that there are function classes for which this is true, but the authors need to discuss the implications of this, especially since they promote entropy-regularization for large-scale RLHF.

A1 Thank you for the insightful comment! Eluder dimension plays an important role in our analysis for the regret bound. Here we provide a discussion of the eluder dimension as follows. The concept of eluder dimension is first introduced in [1], which serves as an important complexity measure for studying reinforcement learning with general function classes. It has been shown that for a (generalized) linear function class, the eluder dimension is $\sim d\log T$ where $d$ is the dimension of the function class [2]. Our logarithmic-in-$T$ regret bound holds when the eluder dimension grows at most logarithmically with $T$. We will add the detailed discussion and the clarification in our revision.

Q2 In finite-horizon reinforcement learning it is usually assumed that the value function is bounded by $H$ rather than 1. The authors do not make it clear what the exact dependence on $H$ is if we change this assumption?

A2 Thank you for your insightful question! If the value function is assumed to be bounded by $H$, then $e_j$ in Lemma 5.2 (on page 8) will be $O(H)$ times larger, which further yields an $O(\eta H^4\cdot d \log \mathcal{N})$ regret bound after applying Lemma 5.2. The additional dependence can be removed via variance weighting and the Bernstein inequality, which is, however, not the focus of our work. We will add this disscussion in the revision.

[1] Russo, D. and Van Roy, B. Eluder dimension and the sample complexity of optimistic exploration. NeurIPS 2013

[2] Wang, Ruosong, Russ R. Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. NeurIPS 2020.