Zeroth-Order Policy Gradient for Reinforcement Learning from Human Feedback without Reward Inference

Authors: Qining Zhang, Lei Ying
Primary area: reinforcement learning
Keywords: reinforcement learning theory, human feedback, zeroth-order optimization

Abstract:
Reward inference (learning a reward model from human preferences) is a critical intermediate step in the Reinforcement Learning from Human Feedback (RLHF) pipeline for fine-tuning Large Language Models (LLMs). In practice, RLHF faces fundamental challenges such as distribution shift, reward model overfitting, and problem misspecification. An alternative approach is direct policy optimization without reward inference, such as Direct Preference Optimization (DPO), which provides a much simpler pipeline and has shown empirical success in LLM applications. However, DPO utilizes the closed-form expression between the optimal policy and the reward function, which is only suitable under the bandit setting or deterministic MDPs. This paper develops two RLHF algorithms without reward inference for general RL problems beyond bandits and deterministic MDPs, and general preference models beyond the Bradley-Terry model. The key idea is to estimate the local value function difference from human preferences and then approximate the policy gradient with a zeroth-order gradient approximator. For both algorithms, we establish polynomial convergence rates in terms of the number of policy gradient iterations, the number of trajectory samples, and human preference queries per iteration. Numerical experiments in stochastic environments validate the performance of our proposed algorithms, outperforming popular RLHF baselines such as DPO and PPO. Our paper shows there exist provably efficient methods to solve general RLHF problems without reward inference.

Decision: accept (poster)
Reviewer scores: 8, 3, 8, 8

Reviews and discussion:
<thread>
creation date:
1730042242364

thread_type:
official_review

<thread_object>
creator: reviewer_9hse

<content>
summary:
This paper introduces two new algorithms for RLHF that do not require learning a reward function. The core algorithm is a variation of reinforce, using a zero-order gradient approximator (the two proposed algorithms differing in the choice of the perturbation direction). To avoid learning a reward function, the authors assume that the preference model is Bradley-Terry-like (considering a more general sigmoid link function, instead of just the logistic function), that $M$ human raters (with $M$ large enough) are available for ranking $N$ pairs of completions (current policy - perturbation), and then use the  inverse of the link function to estimate the reward difference from the empirical preference probability, this reward difference being used for the zero-order gradient estimate. The authors show a convergence result for each algorithm, with rate of convergence (the same), for reaching a stationary policy (not necessarily the optimal one, but one with zero gradient). They also provide some explanations about the technical difficulties of their proof (full proofs being provided in the appendix). There is no empirical study.

strengths:
* The proposed algorithms are interesting, at least from a theoretical viewpoint
* The paper is overall clearly and well written
* There is a nice discussion of the technical difficulties for proving their results, which is quite helpful
* The provided theoretical results sound plausible (some questions about the proofs of Thm1 though, and Thm 2 has not been double-checked)

weaknesses:
* There are overclaims and/or lack of discussion of the limitations of the proposed approach. Drawbacks of DPO or classic RLHF are discussed at length, suggesting that the proposed approach alleviate them (which is only very partly true), but not the limitations of the proposed approach. The strongest issue is that it is assumed that $M$ humans are available for rating $N$ pairs of trajectories for each gradient step (and this must be done online, because the proposed approach is purely on-policy). So, it is hard to see any setting where this could be applicable or reasonable, and it is a strong drawback compared to more practical RLHF approaches. It may be fine to have an algorithm with theoretical guarantees that is not fully applicable, but this should be discussed.
*  The proposed algorithms seem to be new, and they are explicitly positioned as addressing shortcomings of classic RLHF or DPO, which would call for some empirical results, at least on bandits or toy MDPs (possibly comparing with classic RLHF, DPO, but also things like online DPO, eg see « Direct language model alignment from online ai feedback » by Guo et al). There is no such empirical study, and it would really strengthen the paper by providing some empirical evidences on some claims done in the paper.
* There are parts of the paper and of the proofs that are not totally clear, see questions.

questions:
## Lack of discussion 
* Can you please discuss more thoroughly the limitations of the proposed approach (like the need to have on-policy online human raters), and in more details what are the pros and cons compared to DPO and classic RLHF?
* One advantage claimed compared to DPO is the ability to handle stochastic transitions. However, the focus is also mostly done on LLMS. Can you explain in which case we would have stochastic transitions in this context (and how it is handled by your framework)?
* There is no KL regularization, compared to all other works for doing RLHF (and not without reason). Can you expand on this, is it no longer required (from a practical perspective)?
* The paper claims going « beyond the BT model », but the generalization is rather weak, could it handle more general preference models such as those considered for example in « Nash learning from human feedback » by Munos et al?

## No empirical study
* Given that the analyzed algorithm is not representative of practical approaches, and that the second proposed algorithm is motivated by computational aspects (memory, distributed aspect), would it make sense to at least provide some minimal empirical study (with the proposed algorithms, but also DPO, classic RLHF, online DPO)? Or to provide a clear discussion about why it would not bring interesting evidences?

## Aspects to clarify and/or correct 
* It is claimed (l.163) that the considered setting encompasses things like convex MDP. Can the authors expend on this (from the setting, they do not make the assumption that the return is sum-decomposable, but why would this tell that it can be framed as a convex function of the occupancy measure)?
* Would it be possible to group or recall the properties and assumptions of the link function, as it is a quite central object? For example, should we not assume also that $\sigma(x) = 1 - \sigma(-x)$, or is it a consequence of what is already written? Could you also give some examples of the Lipschitz constants $L$ (Assm 2), for example for the logistic function used in Bradley-Terry?
* There is a typo l. 305 (as written, the gradient is always zero, issue in the second value index)
* Assm 2 and 3, the same notation $L$ is used for the Lipschitz constant of $\sigma^{-1}$ and for $L$-smoothness of $V$. There is not reason for these two values to be the same. They are also confused in the proofs. Would it be possible to restate the results by making them distinct (or at least by stating that it’s for some upper-bound of both terms, if that's enough to make proofs work)?
* In Thm 1 and 2, $M$ is a function of $D$, quantity which has never been defined. Even checking the proofs it is not clear what $D$ is. Please clarify (and this is especially important as it is the number of human raters).
* Corollary 1 doesn’t seem to be proven, even in the appendix, can you provide a proof?
* l. 435, how does $\theta^*$ appear with a telescoping argument (plus, the corresponding equation in the appendix involves $\theta_T$, which seems more logical)?
* Lemma 2, would be helpful to explain why the trim operator is introduced (as the result would hold without the trim according to the proof)
* l. 977, typo (parenthesis)
* l. 1014, is it the same $L$ as in Assm 3?
* the end of proof of Thm 1 is pretty unclear (line 1104 to the end of the proof), which is a pitty, as it is the clever part of the proof discussed l.455-465. Why do we have Eq 1106, and why does it lead (and how) to the equation line 1110? It is claimed to be for the case of large gradient, but line 1119 it is again for the case of large gradient. How is the Eq line 1122 obtained, and how does it relates to the one in line 1107? Do these both equations covers all possible gradient cases, and why? L. 1134, how are combined the bounds (max of them, summing them, something else)? Overall, could you reexplain this overall important part?
* l. 1214, there is a missing term (or the line should be removed) * l. 1230-1241, why the 3 factor? (not wrong, but why)
</content>
</thread_object>

</thread>
<thread>
creation date:
1730646629574

thread_type:
official_review

<thread_object>
creator: reviewer_bweu

<content>
summary:
This paper proposes the use of zero-th order algorithms to align a policy to preference data. They propose ZPG, based on random spherical perturbations, and ZBCPG, based on subblockwise perturbations, and prove sample complexity and convergence rates. These algorithms generalize from a Bradley-Terry preference model to general preference model with a specified link function, as well as generalize from deterministic to stochastic domains.

strengths:
- The methods ZPG and ZBCPG work for a general class of link functions (beyond the BT-model) and stochastic dynamics as well.
- Theoretical sample complexity and convergence rates that give an idea of the dependence on the number of human preferences needed, and prove convergence exists. I have not checked the proofs in detail.

weaknesses:
- ZPG and ZBCPG do not work directly from an offline dataset like DPO can; they require online human preferences for the current samples. - Furthermore, even comparing ZPG to online DPO, it seems that ZPG requires more trajectory samples (i.e. more forward passes) because you need multiple perturbations, which is multiple times more costly than online DPO.
- Zero-th order methods may be slower than gradient-based methods, especially for very large models like LLMs.
- No toy experiments. While LLM experiments would seem daunting in addition to the theoretical contribution, toy experiments in simple, stochastic domains to illustrate how DPO would fail but ZPG would work, would be a great addition to further motivate the need for a DPO alternative. I would be willing to increase my score if toy experiments are added to the paper.

questions:
- You mention that classic RLHF and DPO use human preferences to construct a global model, while your method uses the preferences only to locally estimate the policy gradient. While that’s true in theory, however in the actual DPO algorithm in practice, it is also using the expected difference in preference between two generations to construct a policy gradient. Like you mention, because of function approximation, the global BT model assumed by DPO no longer holds, so the empirical DPO also ends up only using local information to estimate the policy gradient. Especially if DPO is used online instead of from a fixed offline dataset. So in practice, both DPO and ZPG are using local information to estimate a policy gradient, and the global-local divide isn’t really clearly there anymore. Could you update the discussion to reflect this?
- You mention the link function generalizes the BT-model. Could you give one or  more motivating examples of non-BT models and link functions that could be applicable (no need for experiments or deep analysis, just give some intuition on when non-BT models could be useful)? I think this would strengthen the contribution of the more general link function.

-- After Author Response --
Thank you for adding the additional numerical experiments and non-BT explanations. I have increased my score.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730657618025

thread_type:
official_review

<thread_object>
creator: reviewer_hh3a

<content>
summary:
The paper proposes a zero-order optimization algorithm for RLHF. The idea is to carry out random perturbation in the space of parameters directly and construct gradient updates based on the random samples. The paper presents some theoretical results that characterize the bias and convergence property of the algorithm.

strengths:
The paper presents theoretical guarantees for zero-order optimization algorithm for RLHF.

weaknesses:
The idea of applying zero-order optimization is not novel. Similar ideas have been extensively studied in the deep RL literature. Much literature reference is missing from discussion. A theoretical paper like this is not very valuable to the RLHF or deep RL community.

questions:
### === Zero-order method in deep RL ===

The idea of applying random perturbation to model parameters and construct gradient accordingly, has been studied extensively in the deep RL literature as replacement for REINFORCE or PPO like algorithms. It seems that much discussion is missing from the paper such as [1] which basically started the trend of zero-order based method for deep RL.

[1] Salisman et al, 2017, Evolution Strategies as a Scalable Alternative to Reinforcement Learning

### === Relevance to RLHF ===

It's not clear if the discussion here is specific to RLHF at all. Do RLHF allow us to assume additional structure on the rewards or the parameter space? No such discussion is furthered in the paper - in regular RL or deep RL setups, the same algorithmic discussions apply. And as a result, the paper is not really a RLHF specific algorithm, the algorithm itself has been extensively studied in the RL literature as well.

### === Empirical ===

There is no empirical backup of the results at all, not even tabular experiments. I think a theoretical paper in its current form like this would not offer too much additional value to the field of RLHF or deep RL. Certain amount of experimentation is warranted, and in the case of RLHF, it is also interesting to see if the algorithm can work at all and how it compares with REINFORCE / PPO.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730697193340

thread_type:
official_review

<thread_object>
creator: reviewer_6mwn

<content>
summary:
This is a novel result that establishes local convergence for an RLHF setup utilizing a novel method to estimate the difference in value functions. However, given the current literature which has established global convergence with a better sample complexity. I do not think this work has sufficient novelty for acceptance.

strengths:
The paper utilizes a novel method for estimation of the difference in the value functions using the inverse of the preference functions. It is able to prove local convergence for a non-deterministic MDP. The paper is well laid out and easy to read.

weaknesses:
The paper can only establish local convergence for the RLHF setup with a sample complexity of $\epsilon^{-5}$. In contrast Xie et al. (2024) established global convergence with sample complexity of $\epsilon^{-2}$.  Even though that case is for a finite state and action space, given the improved sample complexity and global convergence Xie et al. (2024) seems to be the more relevant result.

I am open to improving my score if the authors can give an argument as to why their work improves upon the cited work.



References:


Tengyang Xie, Dylan J. Foster, Akshay Krishnamurthy, Corby Rosset, Ahmed Awadallah, and Alexander Rakhlin. Exploratory preference 
 optimization: Harnessing implicit q*-approximation for sample-efficient rlhf, 2024.

questions:
Is there a way to go from local to global convergence? Perhaps is global convergence can be achieved, the work may be accepted for publication.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732296025133

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response to Reviewers

comment:
We thank all the reviewers for their time reviewing our paper, and we answer common questions raised by the reviewers in the general response.

# Numerical Experiments
We conducted a numerical experiment and added a section to our rebuttal revision to discuss the empirical performance of ZPG and ZBCPG. We tested our proposed both algorithms on a GridWorld environment with **stochastic transitions**, where the stochasticity comes from imperfect control of external disturbances that prevent that agent from performing the action that it chooses. We compare to popular RLHF baselines: DPO, PPO with reward model, and online DPO. The complete results and discussions can be found in Sec. 5 of our revised paper, e.g., Fig. 2. Here, we outline the average trajectory return (value function) of the final policy as follows:

| Algorithm | Average Return of Final Policy |
| ----------- | ----------- |
| ZPG (ours) | 2.01 |
| ZBCPG (ours) | 1.96 |
| PPO+RM| 1.67|
|Online DPO| 1.68|
|DPO| -4.22|

With the same number of trajectories and the same number of human queries, it is shown that **both our algorithms perform better than all three baselines**. The reason partially lies in that PPO suffers from inaccurate reward models, and both online and offline versions of DPO suffer from the error of DPO loss, which is only valid and meaningful in deterministic MDPs, not stochastic ones studied in our paper, and the offline DPO is constrained to the neighborhood of a sub-optimal reference policy. These observations coincide with our discussions of the limitations of RLHF baselines in our paper and also coincide with our motivation to develop RLHF algorithms without reward inference for general RL problems. We believe the numerical experiments serve to validate the consistency of our theoretical results. It also shows the potential of applying our proposed algorithms to practical problems in the field of general RL beyond LLMs.

We also compare ZPG and ZBCPG under distributed implementations to demonstrate the advantage of block coordinate gradient descent, i.e., for every parameter block, we estimate their gradient in parallel after partitioning the human panel. Results are provided in Fig. 2(b). It also shows that as we divide the parameters into more blocks, the faster ZBCPG converges to a stationary policy. However, fewer human evaluators for each block will also introduce bias which harms the overall optimality of the converged policy.

# Non-Bradley-Terry Model
In this paper, we consider preference models assuming latent utility function, which naturally implies transitivity. Non-Bradley-Terry models under this category have been studied extensively in the discrete social choice theory (or random utility model), e.g., a comprehensive study can be found in [1][2]. Besides the BT model (also referred to as logit model), the probit model which uses Gaussian CDF as the link function is also one of the most used utility models. It is the first studied utility model due to the naturalism that the individual utility of different decision-makers is normally distributed [3]. The model correctness is validated with several datasets in [4]. The BT model has a much heavier tail probability than the probit model so is more suitable to analyze comparisons from crowdsourced human individuals since they are less trained and the variation of individual preference is large among populations. The probit model is more suitable when feedbacks are compared to well-trained panelists since the outcomes from different people are mostly aligned even when the reward difference is small. Other preference models such as the Weibull model is proposed for preferences without antisymmetry, i.e., $1-\sigma(-x) \neq \sigma(x)$ [5], which can also be used in our approach as well. In general, which model fits best depends on the specific application and there is much value in studying non-BT models to formulate RLHF approaches suitable in different domains. 

[1] Train, Kenneth E. Discrete choice methods with simulation. Cambridge university press, 2009.

[2] Azari, Hossein, David Parks, and Lirong Xia. "Random utility theory for social choice." Advances in Neural Information Processing Systems 25 (2012).

[3] Thurstone, Louis L. "A law of comparative judgment." Scaling. Routledge, 2017. 81-92.

[4] Gulliksen, Harold, and John W. Tukey. "Reliability for the law of comparative judgment." Psychometrika 23 (1958): 95-110.

[5] Greene, William H. "Econometric analysis 4th edition." International edition, New Jersey: Prentice Hall (2000): 201-215.

***
We hope our response can address the reviewers' concerns, and help the reviewers understand further the contribution of our paper.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper is primarily theoretical. The authors propose zeroth order optimization methods for RLHF, prove sample complexity and convergence rates.
The algorithm is quite interesting from a theoretical perspective.
The method is new and seems to alleviate some of the limitations of current algorithm for RLHF.

The main limitation, although not extensively highlighted by the reviewers, is the lack of a comprehensive empirical study.