Clarifications and Corrections

We sincerely thank the reviewer for going through our paper in detail. We apologize for the confusion caused by typos and have already fixed them in our revision.

Link function: We will revise the paper to state the properties of link function and recall them when needed. We do not require antisymmetry of the link function, and the result still holds as long as the link function is known, e.g. a example could be Weibull link function. The smooth parameter $L$ for BT model can be upper bounded by $4H$ in our setting.

Convex MDP: We apologize for the mistake and have removed the claim regarding convex MDP from the paper. We intend to say that the return in our model can be a convex function of per-step reward.

Smooth parameter $L$: to not introduce additional notations for constants, the constant $L$ in our paper should satisfy both Assumption 2 and 3 simultaneously, i.e., $L$ is the maximum of constant in Assumption 2 and constant in Assumption 3. In addition, this specific $L$ will satisfy Lemma 3. We have remarked in the paper that an upper bound would suffice for all theoretical results.

Theorem 1 and Theorem 2: We apologize for the typo that $D$ should be $H$ in this context. Specifically, if $M=H^2$, we have the result as stated, if $M$ is smaller, an additional term $d^2 H/M$ will appear in both Theorem 1 and 2, so this is not a strict requirement to obtain theoretical results.

Corollary 1: the proof is simply to require all three terms in Theorem 1 and 2 less than $\epsilon/3$. And it will lead to the human query complexity bound in Corollary 1. We omitted the proof in the paper because it seems straightforward from the Theorems, we will add it in our appendix if we are mistaken.

$\theta^*$ in Proof Outline: Neglecting the difference between the value function $V$ and its smoothed version $V_\mu$, this is by replacing $V(\theta_T)$ with $V(\theta^*)$ since $V(\theta_T) \leq V(\theta^*)$ by definition of the best parameter. We have revised the main body to be $\theta_T$ to avoid confusion.

Trim operator: with finite human evaluation, all $M$ feedbacks for the same trajectory pair may be the same, say the feedbacks are all 1, then the inverse link function will possibly output infinity (say under the BT model), which does not make sense since the reward difference is bounded in [-H, H], the trim operator ensures this will not happen and thus the inverse link function provides meaningful reward difference estimation.

Proof of Theorem 1: we apologize for the typos that confuse the reviewer, and we have now fixed all typos and made it clear. Based on line 1182 of the current version, we can upper bound the constants before gradient norm $\|\nabla V(\pi_{\theta_t})\|$ (at LHS) by the gradient norm $\|\nabla V(\pi_{\theta_t})\|$ times $\alpha/8$, and this gives RHS of line 1187. Line 1193 should be for a small gradient norm where the inequality of line 1182 is reversed, i.e., the gradient norm $\|\nabla V(\pi_{\theta_t})\|$ has an upper bound. Then, we can use this upper bound to substitute the gradient norm at the LHS of line 1199 to get the RHS of line 1199. This covers all gradient cases. In line 1212, the bounds are combined by taking a maximum.

Line 1290 missing term: This is not a missing term, it is by merging the $H/M^2$ term into the $1/\sqrt{M}$ term when $M$ is large enough, i.e., $M \geq 8 (H/L)^{\frac{2}{3}}$. In this case, the $H/M^2$ term is less than the latter term times a constant. So the constant in front is changed from $\sqrt{2}$ to 2.

Why 3 factor: To avoid more discussion on the correlation amongst the three terms, we just bound it by $(a + b + c)^2 \leq 3a^2 + 3b^2 + 3c^2$, so there comes the 3 factor.

---

We hope our response can address the reviewer's concerns and help the reviewer understand our contributions more clearly. We would very much appreciate it if the reviewer could consider re-evaluating our paper.

We thank the reviewers for their precious time in reviewing our paper carefully, and for their valuable comments. We apologize that the typos in our original manuscript caused confusion to the reviewer and have fixed all of them. Below, we discuss the points raised by the reviewer.

Human Labeling Complexity and Limitations

It is correct that our algorithm suffers from online human labeling complexity. We thank the reviewer for bringing this up, and we have added a paragraph discussing our limitations. Generally, for stochastic MDPs, DPO-based algorithms have bad performances since the loss is specifically designed under deterministic MDPs. The classic RLHF method with a reward model may be applied but are subject to the error of inaccurate reward model. In our experiment, neither baselines have a performance comparable to our approach. Our methods don't require a reward model but need multiple online human evaluations per iteration. One possible way to alleviate this limitation is to replace human feedback with AI feedback as suggested by online DPO. Another possible solution is to apply variance reduction methods such as momentum in gradient descent so we will require fewer samples and fewer human annotation tasks for each iteration.

Emprical Results

Please refer to the experiment section of our general response. It is shown that both ZPG and ZBCPG have better performance than DPO-based algorithms since the DPO loss is specific to deterministic MDPs. They also perform better than classic RLHF with a reward model, since the reward models may be inaccurate.

Stochastic Transition

Our paper does not focus on applying RLHF in LLMs but on more general RL problems. For example, in robotic learning, agents operating in natural environments may encounter stochastic disturbances such as wind or other natural events. Our paper shows the potential of developing RLHF algorithms and improving the performance of agents in such scenarios.

KL Regularization

The KL regularization used in other RLHF papers served two purposes. First, in deterministic MDPs, the KL regularization ensures an analytical solution of the best policy which is essential in obtaining the DPO loss. Second, it ensures the fine-tuning policy does not deviate much from the initial point, which exhibits stability and preserves good properties of the initial point (usually a pre-trained model). However, if your pre-trained model is not good enough, the KL regularization also limits the possibility of converging to the best policy defined as the policy maximizing the value function. Our paper studies the general RL training process so we focus on finding the best policy and do not restrict ourselves to KL-constrained problems.

Preference Model Compared to Nash Learning

The preference model studied in our paper does not cover the preference in Nash Learning, nor does the preference in Nash Learning cover our preference model. Both models are generalizations of the BT model with trajectory feedback. Our preference model admits transitivity but does not require antisymmetry, on the other hand, the preference studied in Nash Learning requires antisymmetry but does not require transitivity. Moreover, the definition and performance of the best policies are also different, so it is hard to compare from a theoretical perspective directly. A more detailed discussion of our studied preference model alongside its value can be found in our general response. Specifically, the Weibull model allows us to resolve preferences that are not antisymmetric.

We thank the reviewers for their precious time in reviewing our paper and for their valuable comments which help us improve our manuscript. Below, we discuss the points raised by the reviewer.

Online Human Preference Query

Compared to vanilla DPO, both ZPG and ZBCPG are online algorithms and require to collection of human feedback in an online fashion. This weakness is not unique to our algorithms but to all online RLHF algorithms such as online DPO. However, the strength of online RLHF is they usually provide better performances. We can also potentially replace human feedback with AI feedback to reduce the labeling burden.

Computational Cost Compared to Online DPO:

Compared to online DPO, at each iteration, we indeed require multiple samples to estimate the value function difference, which is more costly per iteration than online DPO. However, the value of our algorithm lies in its applicability to general RL problems with stochastic transition, while DPO is for deterministic MDPs and has a poor performance in stochastic MDPs, as shown in our experiment. It is also shown in our numerical experiment that our proposed algorithms, even though require more samples each iteration, need less number of iterations to converge, so the overall computation time is still comparable. In fact, the DPO baselines took longer to run in our experiments overall. The batched sample-query-update workflow used in our algorithms may also more suitable for implementation compared to having a human in the loop to label streaming data as suggested by online DPO, and may also require fewer circles.

Zeroth-Order Method is Slower than Gradient Method:

For large models like LLMs, gradient-based methods are usually memory inefficient, and sometimes not implementable due to the requirement to store the interim gradient results during backpropagation. It has also been shown that zeroth-order methods are a good alternative in this setting[1]. The main aim of this paper is to design provable and efficient RLHF algorithms without a reward model for general RL tasks beyond LLMs, where there are few efficient gradient-based algorithms. Our proposed algorithms serve to fill this gap.

[1] Malladi, Sadhika, et al. "Fine-tuning language models with just forward passes." Advances in Neural Information Processing Systems 36 (2023): 53038-53075.

Toy Numerical Example

Please refer to the experiment section of our general response. It is shown that both ZPG and ZBCPG have better performance than DPO-based algorithms since the DPO loss is specific to deterministic MDPs. They also perform better than classic RLHF with a reward model, since the reward models may be inaccurate.

Local Information Used in Online DPO

We thank the reviewer for this discussion, and we agree that online DPO also uses local information for gradient estimation since it obtains new trajectories and preferences, and then evaluates the gradient based on the current model and the new samples. The global versus local divide is more about comparing to classic RLHF with reward models. We also want to remark that the relation between the optimal policy in deterministic MDP and the reward function is global, and is the core for designing DPO loss, so there is still differences regarding what local information is used. Again, we want to emphasize that DPO is for deterministic MDPs, not for general stochastic MDPs so our proposed algorithms can be viewed as extending this local estimation insight to general MDPs. We have added and updated a this discussion in our revision.

Non-Bradley-Terry Models

Please refer to the Non-Bradley-Terry Model section in our general response. We also added a paragraph in our rebuttal revision discussing a general view on how to model human choices and preferences in the context of random utility theory.

---

We hope our response can address the reviewer's concerns. Given that we indeed provided a numerical experiment which demonstrated the better performance of our approach compared to baselines, we would very very appreciate it if the reviewer could increase their score.

We thank the reviewers for the time they spent reviewing our paper. Below, we discuss the points raised by the reviewer.

Novelty of ZPG Compared to Zeroth Order Methods in Classic RL

Indeed zeroth-order methods have been empirically studied in classic RL in the form of evolutionary strategies. However, the theoretical guarantees of such algorithms are largely under-explored. We want to point out a major difference between classic RL and RLHF: classic RL problems have well-formulated loss functions that can be queried, but RLHF does not. The loss function in classic RL could be value function or KL-constrained value function. It is straightforward to follow the classic zeroth-order optimization framework to design RL algorithms by querying the loss functions, such as evolutionary strategies. However, in RLHF without a reward model, the value function objective studied in this paper cannot be directly sampled, approximated, and queried, since the reward is unobservable. What we can observe is only the trajectory preference feedback. One of the main messages this paper conveys is that human preference feedback can be viewed as a natural source of the zeroth-order gradient since it is more likely to inform the better trajectory. The novelty of this paper lies in designing human query strategies and then extracting zeroth order gradients from human feedback. We want to emphasize that this step is non-trivial and more complex compared to constructing zeroth order gradient in classic RL, since estimating the zeroth-order gradient from human feedback will result in additional bias, as stated in Sec. 4.3. The new bias from human feedback adds more difficulty to the algorithm design since we need to choose the learning rate and perturbation distance much more carefully to balance the bias and gradient noise. To the best of our knowledge, there is no RLHF algorithm for general RL problems with policy function approximation that has a provable theoretical guarantee and does not require a reward approximation. We believe ZPG points out the internal relation between human feedback and the zeroth order gradient, which will motivate more RLHF algorithms in general RL problems beyond LLMs.

Relevance to RLHF

We argue that the design and discussion of our proposed algorithms, i.e., ZPG and ZBCPG, are specific to RLHF, in particular for RL problems beyond LLM. Compared to classic RL, RLHF reveals much less feedback information to the agent, i.e., the trajectory reward is unobservable but only the preference feedback is provided. Therefore, without a reward model, the loss functions used in classic RL algorithms, such as the PPO loss or vanilla value function, are difficult to approximate. It is unclear how to sample the loss function to construct a gradient (either first-order or zeroth-order), which prohibits directly using the zeroth order methods such as the evolutionary strategy to RLHF. The contribution of our proposed algorithms lies in building a relation between human preference and zeroth-order gradient and then constructing zeroth-order information from human feedback. This characteristic makes both algorithms an RLHF-specific algorithm and has essential differences compared to zeroth-order algorithms in classic RL such as evolutionary strategies. We thank the reviewer for mentioning the literature on evolutionary strategies and have added a discussion in our literature review comparing the similarities and differences in the revision.

Empirical Results

Please refer to the experiment section of our general response. It is shown that both ZPG and ZBCPG have better performance than DPO-based algorithms since the DPO loss is specific to deterministic MDPs. They also perform better than classic RLHF with a reward model, since the reward models may be inaccurate.

---

We hope our response can address the reviewer's concerns and help the reviewer understand the difference between zeroth-order methods in classic RL and in RLHF, as well as our contributions. We would very much appreciate it if the reviewer could consider re-evaluating our paper.

Dear Reviewer HH3A,

Thank you again for your time in reviewing our paper and for asking many valuable questions. Please don't hesitate to let us know if you have any other questions/comments before the discussion deadline today. We would be happy to answer. Thanks!

We thank the reviewers for their precious time in reviewing our paper and for their valuable comments. Below, we discuss the points raised by the reviewer.

Comparison to Xie et al. (2024)

We want to point out that the setting and problem studied in our paper have several fundamental differences from XPO in Xie et al, which make it difficult to directly compare the theoretical results. We outline these differences below.

Stochastic versus Deterministic MDPs: One major difference is that Xie et al. only study deterministic MDPs while we study stochastic MDPs, where deterministic MDPs are a special class of MDPs where the transitions are deterministic. The XPO algorithm in Xie et al. is based on the DPO loss which is only meaningful under deterministic MDPs, and the global convergence result is stated only for deterministic MDPs. In contrast, we consider stochastic MDPs which model general RL problems and are much harder to solve. In fact, in Remark 3.2 in Xie et al., the authors state that their results cannot be generalized to stochastic MDPs. Therefore, the global convergence of XPO does not apply to our setting. Our conducted experiment also confirms their statement since DPO has a poor performance in stochastic MDPs. This phenomenon is likely to apply to all algorithms based on the DPO loss, including XPO.

Unconstrained versus KL-Constrained Objective: The definition of optimal policy in Xie et al. is based on the KL-regularized objective, while our definition is based on the vanilla value function. Their results and algorithm cannot cover the case without KL-regularization, i.e., setting $\beta = 0$ is not meaningful in both their algorithm and their convergence result. This again shows that it is not very meaningful to directly compare the two results.

Policy Parameterization: The results in Xie et al. are stated for finite function class with realizability, which is important in deriving their global convergence result, e.g., they assume the optimization problem in Line 6 of Algorithm 1 of each iteration can be exactly solved. Our paper studies general policy parameterization without these assumptions. Even though they can extend the results to infinite function classes such as the parameterization in our paper, exactly solving the optimization problem at each iteration becomes problematic and inevitably requires certain types of gradient descent, which is likely to result in sub-optimality.

Additional Assumptions: The results of Xie et al. also depend on the trajectory density ratio and coverability, which may be large since some trajectories may have zero occupancy measures. We don't require such assumptions, but we require smoothness of the policy parameterization for theoretical guarantees.

Overall, our paper studies a more general MDP with stochastic transition and no KL-regularization, with a more general policy parameterization. The algorithm developed by Xie et al. is not suitable for this setting and new algorithm designs (such as our proposed approaches) are required. The contributions of both papers should be viewed as complementary instead of a direct comparison.

Global Convergence

Given the generality of the RLHF setting studied in this paper, i.e., stochastic MDPs with policy function approximation, it is extremely difficult to establish global convergence even for standard RL, except for specific parameterization or specific algorithms such as tabular softmax parameterization with natural policy gradient. It is unlikely that any algorithm, including XPO in Xie et al., will achieve global optimality in this setting without further assumptions such as convexity or PL condition over the function parameterization. Again, these assumptions are often questionable in practice. Considering the difficulty and generality of the setting, we think local convergence is the best result that can be obtained, and a meaningful result showing the effectiveness of the proposed algorithm to a wider range of RL problems beyond LLMs. This is also confirmed by our conducted experiment which shows a close-to-optimal empirical performance for our proposed algorithm.

---

We hope our response can address the reviewer's concerns and help the reviewer understand difference in the cited work and our paper, as well as our contributions. We would very much appreciate it if the reviewer could consider re-evaluating our paper.