Zeroth-Order Policy Gradient for Reinforcement Learning from Human Feedback without Reward Inference
Authors: Qining Zhang
Lei Ying
Venue: ICLR 2025 Poster (2025)
Keywords: reinforcement learning theory
human feedback
zeroth-order optimization
Primary area: reinforcement learning
TL;DR: We propose zeroth-order policy gradient for RLHF over trajectory preference with provable convergence and no reward model.

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.

Published as a conference paper at ICLR 2025
ZEROTH-ORDER POLICY GRADIENT FOR REINFORCE- MENT LEARNING FROM HUMAN FEEDBACK WITHOUT REWARD INFERENCE
Qining Zhang& & Lei Ying Department of Electrical Engincering and Computer Science University of Michigan - Ann Arbor
Ann Arbor, MI 48105, USA {qiningz, lelying @umi ch. edu
ABSTRACT
Reward inference (learning reward model from human preferences) is 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 much simpler pipeline and has shown empirical success in LLM appli- cations. 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- model. The key idea is estimate the local value function difference from human preferences and then ap- proximate the policy gradient with 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 base- lines such as DPO and PPO, Our paper shows that there exist provably efficient methods to solve general RLHF problems without reward inference.
INTRODUCTION
In the past decade, we have witnessed unprecedented success in applying Reinforcement Learning (RL) to many applications, such as video games (Knox & Stone 2008; Warnell et al.) 2018), rec- ommendation and search (Zeng al. 2016 Kohli et al., 2013). and autonomous driving (Kiran et al. 2022). RL studies the interaction between decksion-making agents and an evolving dynamic environment. At each time step, the agent takes certain decision (action) given the current state, and a reward signal to measure the quality of that decision is provided by the environment. The agent's goal is learn policy maximize the cumulative reward, and the quality of the learned policy will depend on the per-step reward function. In classic RL, this reward function is usually handcrafted by domain experts to ensure aligns with human interests. However, the problem of identifying a "good" reward function, also referred to as Inverse Reinforcement Learning (IRL), is non-trivial and one of the most fundamental problems the history of RL (Ng Russell 2000). In recent years, Reinforcement Learning from Human Feedback (RLHF) that uses human preference feedback as a signal to recover a reward function has emerged to fine-tune Large Language Models
(LLMs), which has delivered significant success (Christiano et al.] 2017; Wu et al. 2021 Nakano
et al. 2021 Ziegler et al. 2019 Stiennon et al. 2020 Ouyang et al. (022)) RLHF follows the diagram shown in Fig. [I, which includes three major steps (Ouyang al. 2022): (i) pre-train pol-
icy neural network, (ii) collect sets of trajectory pairs and query human evaluators for preferences
over trajectory pairs to train reward model using maximum likelihood to align with human feed-

---

Published as a conference paper at ICLR 2025
Tijectory Fair
Dataset
Beiavior Policy
Human Evaludor
Comparison
Trajectories
Inference
DPO
Enviroament
Bradley- Teary
Pre- trained A gent (Policy Netwodk)
PPO
Reward Model my(%.
Figure 1: classic policy-based RLHF and DPO: classic RLHF, such as PPO, involves three steps: (i) policy pre-training, (ii) reward inference, and (iii) policy network training with reward model. DPO does not use a reward network but directly optimizes the policy network from human preferences.
back, and (iii) use policy-optimization saasiiiattio--beedddddd based RL algorithms such as PPO (Schulman et al., 2017) to fine-tune the policy network with the reward signals generated by the reward model. The reward inference intermediate step, which trains the reward network, is crucial to obtaining a high-quality policy through RL in the final step.
Drawbacks of Reward Inference. To train a good reward model, i.e., to infer the underlying per- step reward function from human feedback (Christiano et al. 20177] Wang et al. (023), the most common approach is to assume the feedback is generated based on a preference model such as the Bradley-Terry model (Bradley & Terry 1952), and then maximize the log-likelihood of the collected trajectory comparison dataset accordingly over all possible (parameterizee) reward functions. This
procedure is indeed analyzed in most theoretical RLHF papers for both offline (Zhu et al. 2023
Zhan et al. 2024a) and online settings (Saha et al., 2023 Zhan et al. 2024b Wu & Sun, 2024
Wang et al. 2023 Du al. 2024). However, several challenges occur in practice for reward model training. such as double problem misspecification, reward model evaluation without ground truth, distribution shift, and overfitting in joint reward model and policy training (Casper al. 2023). These drawbacks are also reflected in the theoretical results, e.g., overfitting of the maximum like- lihood estimator (MLE) Zhu et al. (2024). Moreover, similar to the dilemma in IRL, the reward function that could explain human feedback is often not unique, especially when given limited train- ing trajectories (Arora & Doshi 2021 Ng & Russell 2000). Some reward models may make difficult for agents to learn good RL policy.
DPO. To avoid the drawbacks of the reward inference RLHF, Rafailov et al. (2023) proposed an algorithm called Direct Preference Optimization (DPO), which fine-tunes the LLM directly from human preferences. Based on the Bradley-Terry preference model and a closed-form expression of the optimal policy given reference policy and the reward function, DPO constructs loss function directly from human feedback for learning the optimal policy to avoid reward inference. This pro- vides much simpler pipeline and has great empirical performance (Rafailov al. 2023 2024a b). However, the closed-form expression of the optimal policy that DPO builds on is only for non- parametric policies, and its theoretical justification only works for the bandit setting (Rafailov al.) 2023) or RL problems with deterministic transitions (Rafailov et al. (0224b). It remains an open question how solve general RLHF problems without reward inference.
RLHF without Reward Inference. Recently, value-based RLHF algorithms without global reward inference have been theoretically developed and analyzed (Xu al.] 2020); Zhang et al.] 2024a) based on dueling bandit approach (Bengs et al., 2021). The results, however, only hold for MDPs tabular settings with finite state and action spaces. Chen et al. (2022) studied the function approx- imation regime, but their algorithm requires both the true preference model and the transition kernel to belong to known function class, which is also far from practice. The result also depends on the function class complexity, which is usually large for most function approximators in practice. So far, no provable policy- algorithm in this category has been developed.
This paper addresses the following important question:
Does there exist a provably efficient RLHF approach that does not require re- ward model and works for general RL problems such as stochastic MDPs or infi- nite state and action spaces?
2

---

Published as a conference paper at ICLR 2025
1.1 MAIN CONTRIBUTIONS
DPO (Rafailov et al., 2023 establishes a direct connection between human preferences and RL based on the Bradley-Tery Terry model and the optimal policy in closed form:
n (a ()) x <er(alz) exp (E)(e,a)).
(1)
where r(x, a) is the reward in state with action a, Wee is reference policy and n² is the optimal policy. Based on the direction connection, the policy optimization can be formulated as a direct matching between human preference and the optimal policy with log- ligellklihoodd loss function. In a recent paper (Rafailov et al. 2024a), it has been further shown that DPO solves KL-divergence- constrained policy optimization problem for the deterministic token-level MDP for LLMs, where the next state is deterministic given the current state and action. For general RL problems with parameterized policies, equation does not hold, and it is often hard, if not impossible, to obtain a "global" function like it that connects the optimal policy and the reward (hence human feedback).
This paper exploits the "local" relation between human feedback and policy optimization. In partic- ular, given a policy To and a perturbed version of the policy To- where is a small perturbation vector, we use human feedback over the trajectories generated from both policies to inform the di- rection of more preferred policy. Intuitively, if one trajectory is preferred over the other, the policy that generates this trajectory is likely to have a higher value. Then given a preference model such as the Bradley-Terry model, we can further estimate the value function differences of the two policies, ((Te+o)= - (TTo), where (TT) is the value function associated with policy т. Finally, the value difference can be used as an estimator of policy gradient, V VoV(T)), following the zeroth-order optimization approach (Nesterov & Spokoiny 2017 Ghadimi & Lan 2013) to improve the policy.
Based on this idea, this paper proposes two RLHF algorithms without reward inference: Zeroth- Order Policy Gradient (ZPG) and Zeroth-Order Clock-Coordinate Policy Gradient (ZBCPG), both from Human Feedback. ZBCPG differs from ZPG in its policy perturbation rule, which has lower computational complexity and allows parallel optimization since one can sample multiple perturbed policies perform policy gradient and aggregate the estimated gradient. Under mild assumptions, both algorithms have the following rate of convergence to stationary policy:
Hd T
d Mog M Hdyd VN
VM
where d is the dimension of policy network parameter 0, H is the planning horizon, T is the number of policy gradient steps, N is the number of policy perturbations each step, and M is the number of human queries for each pair of trajectories.
We remark that Tang et al. (2024b) proposes similar approach towards utilizing human feedback and a zeroth-order gradient descent algorithm from ranking data. However, they assume an error- free ranking oracle over policies based their value functions, which makes their problem de- terministic optimization problem and does not apply to trajectory preference data like in RLHF and DPO. This paper studies RLHF with trajectory preferences and quantifies the impacts of stochastic trajectories and human preferences on the rate of convergence of RLHF without reward inference.
2 PRELIMINARIES
Episodic RL. We consider an episodic RL problem M (S, A. P.P.P.)). where is the state space and A is the action space (both can be continuous), H is the RL planning horizon, P H ( is the set of transition kernels, and po is the initial distribution. At the beginning of each episode, the agent will choose a policy и represented by H functions { $ - ((A)]= where P(A) denotes the set of all probability distributions over the action space. Then, initial state s1 is sampled from the initial distribution 140- At step h, the agent takes an action a = Tn (5)) after observing state Sh. The environment then moves to the next state 81+1 sampled from the distribution (- on)) without revealing any reward feedback. We use 7 to denote a trajectory with planing horizon H, i.e., T {(S,, a,) 1
Trajectory Reward. we assume the expected reward of each trajectory T is a general function r(7) which maps any trajectory value in [0, H] (Zhang al. 2024a). Without loss of generality,
3

---

Published as a conference paper at ICLR 2025
scale the average per-step reward into [0, 1], and the return of the trajectory does not necessarily need to be the sum of per-step rewards. For any given policy म, we can formulate the initial value function VTT (s) the expected reward of trajectories starting from with policy
(s) = [r(7) $1 = s] E [r(r]] 81 = 8, ... "","""" ~ x].
The goal of the RL problem is find policy maximize ((=) Es- [V (s)).
Policy Parameterization. to address the large state space S and action space A in most RL prob- lems, assume access to a parameterized policy network No S [H] P(A) which takes state and a decision-making step as input, and then outputs the probability distribution of the next action. Here 0 E gd is the policy network parameter vector. Each parameter 0 through the policy network will induce a policy, which we slightly abuse the notation and use T to denote.
Human Feedback. The agent has access to human feedback that provides a preference based on the rewards of two trajectories. In each episode, the agent can choose two trajectories To and to query human preference: one-bit feedback E {0. 1). We assume the preference o generated according to known preference model where the probability of the outcome between two trajectories is de- termined by the difference in their rewards. Since the difference not necessarily a value inside the unit interval, the preference model uses link function RR + rewards to actual probabilities, i.c.,
1] to map these differences of [0,
P(T > )o) = o r(To)),
where 71 > To is the event that the human feedback prefers TI over TO. The human feedback o, therefore, is random sample from Bernoulli distribution with P(o 1) P( > To). The no- tion of link function comes from the dueling bandit literature to model preference with latent utility between arms, e.g., see |Bengs al. (2021 Section 3.2). This preference model has been used in dueling bandits (Bengs et al. [202]] Yue & Joachims) 2009: Kumagai 2017; AAiln et al. 2014) as well as RLHF (Wang et al. (023)). One can see that one specific link function o will define spe- cific preference model Azari et al. 2012), i.e., replacing (-) with logistic function, we recover the Bradley-Terry model (Bradley & Terry 1952). which commonly used in RLHF for both prac- tical (Christiano et al.] 2017] Ouyang et al. 2022; Rafailov et al. (023) and theoretical works (Du) al., 2024] Zhan et al. 2024a b). On the other hand, let (-)) the cumulative distribution func- tion (CDF) of standard normal distribution, we obtain the Probit model (Thurstone) 1927) which has wide application in the study of social choice theory, economy, and psychology Train 2009] Greene 2000). A detailed discussion
other preference models is provided in the appendix. The following assumption on the link function is standard in both dueling bandits (Bengs et al., 2021) and preference- based RL (Wang et al. 2023). One can easily verify that both the Bradley- Terry and Probit models satisfy this assumption.
Assumption The link function (()) in the preference model in equation bounded within [0, 1] and strictly monotonically increasing on [-H, H) with (0) = 1/2.
Problem and Notations. Our goal is to find parameter that maximizes the value function, i.e. maX V (TTT). For scalar a, we use trim [a A] to represent min (maxfa, A). A). For vec- tor v. trim [v] A) represents the vector after applying the trim operator to each element respectively. Let e; T represent the unit vector with all zero elements but on the i-th coordinate.
3 ZEROTH-ORDER POLICY GRADIENT ALGORITHMS FOR RLHF
In this section, propose two RLHF algorithms without reward inference, motivated by the relation between preference and zeroth-order gradient. We first present ZPG, a stochastic gradient descent algorithm, and then ZBCPG, stochastic block-coordinate descent algorithm.
3.1
ZPG: ZEROTH- POLICY GRADIENT FROM HUMAN FEEDBACK
Our first algorithm ZPG, consists of the following five steps in each policy gradient iteration:
From the current policy Ta, first obtained perturbed policy no, (line 2-3). Sample N pairs of trajectories under the two policies ne, and no, tum, (lines 5-6).
4

---

Published as a conference paper at ICLR 2025
Algorithm 1: Zeroth-Order Policy Gradient from Human Feedback
Parameters: initial parameter Oo, learning rate a, trim size A, perturbation distance μs.
for [orl=1 1 7'd. do
sample v, uniformly from unit sphere gd-1 = { E R= ||l| 1}:
obtain a perturbed policy pur+
for 1: do
sample trajectory Tw.0 T0,
sample trajectory Ta.1 + query M human evaluators with (Tv,1, Ta,0) Tn.0) and obtain feedback [on,1. Mn,M]
estimate preference probability Pt, trim
Σ Em=
On.m
M
estimate the policy gradient: 9: E (pt.))
N
Uzi
10
update 0,+1 0: + agi:
For each trajectory pair, say (Tn, Tn.o), obtain M independent human preferences (line 7) and estimate the probability that Tn,1 is preferred over Tu.0 (line 8), denoted by Pt.
Use the N estimates (Pt.n) ) and link function (-) to estimate the gradient 9r (line 9).
Update the current policy new policy 0,+1 using gradient ascent (line 10).
The pseudo-code is presented in Alg. I As we mentioned earlier, our approach uses human feedback in way different from both the classic reward inference in RLHF and DPO. The reward inference uses human preferences to recover the global reward function, and DPO relates the human prefer- ence generation mechanism to the optimal policy. We view the human feedback as local information that points to the direction of more preferred policy, i.e., the policy gradient direction. Some online RLHF algorithms, such as online DPO, also exploit similar local estimation viewpoints, i.e., using new trajectories of the current policy to locally improve the estimation of DPO loss and then pro- ceed. However, we want to emphasize that the relation between the DPO loss and the optimal policy is still global, and it is limited to deterministic MDPs, which shows the novelty of approach. The algorithm we propose has two key components: (i) a value function difference estimator from human preference, and (ii) a policy gradient estimator from value function difference.
Policy Gradient Approximation. At each iteration of the algorithm, it first samples d-dimensional vector v. from unit sphere and then perturbs the policy network parameter O, along the direction of this sampled vector. Then, it uses the inner for loop to construct an estimation of the value function difference between the original policy and the perturbed policy, i.e., V pxx V (T..). We then plug it into the zeroth-orde order stochastic gradient descent (SGD) algorithm proposed in (Ghadimi & Lan 2013) construct a zeroth-order approximation to the policy gradient, i.e.
d (V(TT.+ L
VoV VoV(TO.) z Ev..
V
We remark that the random vector for each iteration can also be drawn from a normal distribu- tion (Nesterov & Spokoiny 2017), but the unit sphere more numerically stable.
Value Function Inference. The inner for loop of Alg. Jamms to estimate the value function differ- ence between the perturbed policy To,+uu and current policy тe, The algorithm samples multiple trajectory pairs with both policies and for each pair, it queries humans multiple times to obtain pair- wise preferences [on.1, ... Mn,M). .. It then uses the preferences to construct robust estimator pt... to approximate the probability of comparison PP > Tn.D). which is further converted to an estimate of the value function difference based on the preference model in equation as follows:
N
((Ta ((TO.) R
(p.,.).
Querying humans multiple times ensures accurate estimation of the reward gap between two trajectories. The reward gap of two trajectories a random sample the value function difference, sample multiple trajectories ensure the average trajectory reward gap converges to the
5

---

Published as a conference paper at ICLR 2025
Algorithm 2: Zeroth-Order Block-Coorddintt Policy Gradient from Human Feedback Parameters: initial parameter Oo, learning rate a, trim size A, perturbation distance μ4, coordinate batch size K.
for f. do
sample a set of K coordinates i, 2,, it, k| from {1,2, ,d]; sample a set A = 24, :. , where each At, is uniformly sampled from {-1,1};
construct the perturbation vector: 1s = VK Ej=r cice
for n =1 1: N do
sample trajectory Ta,0 T0,
sample trajectory Ta.1 T
query M human evaluators with (Tv,1, Tn.0) and obtain feedback [on.1. 1 Mn,M]
estimate preference probability Pt,x trim
Σ
Em=
On.m
M
10 estimate the policy gradient: 9: d E
(pt.n) Uzi
N
11
update 0,+1 = 0: + age:
value function difference. To ensure finite variance after applying (-) function, we trim Pr. with a small constant which can be set to 1- in this case.
3.2 ZBCPG: ZEROTH-ORDER COOORDIAOEE POLICY GRADIENT FROM HUMAN FEEDBACK
In nigh-dimensional optimization problems, it is usually memory and operation- -ineaiionneeffccient to ap- proximate the full gradient and update all the parameters in the policy network at the same iteration step (Malladi al.] 2023 Zhang al. 2024b), which motivates parameter--fffcient fine-tuning (PEFT). The stochastic (block) coordinate descent approach naturally arises because of its ease of implementation, low memory requirements, and adaptability to distributed settings (Nesterov 2012 Lu & Xiao 2013). The same advantage also applies to RLHF when the number of parameters in the policy network too large. Therefore, we propose ZBCPG, a block coordinate version of ZPG, which is summarized in Alg. [ The key difference between ZBCPG and ZPG is the choice of the perturbation direction, where we use Rademacher noise instead of the normal perturbation ZPG.
Zeroth-Order Block Coordinate Gradient Approximation. Instead of sampling from sphere, which perturbs all parameters of the policy network, ZBCPG separates the sampling procedure into two simple parts: first, sample minibatch of coordinates and then sample zero-centered Bernoulli random variable for each coordinate, which still results in a valid gradient estimator.
(T V (TTO.) 0z) Ku
d
( RO Ei,,.
The block-coordinate approach allows us (i) perturb subset of parameters each iteration, e.g., specific layer of the policy network for fine-tuning, and (ii) have parallel implementation where we have multiple gradient estimators 9. when updating the policy. We will later show that both algorithms have similar provable convergence guarantees, but the analysis of ZBCPG is more challenging due to the perturbation mechanism.
4 THEORETICAL ANALYSIS: RATE OF CONVERGENCE
In this section, provide theoretical performance guarantees for both ZPG and ZBCPG. We first provide technical assumptions on the preference generation model, the policy network, and the value function landscape, which are necessary for deriving theoretical insights.

---

Published as a conference paper at ICLR 2025
4.1 ASSUMPTIONS
To infer the local reward difference from human preference probability through the link function a()), we impose the following assumption, which is satisfied by the Bradley-Terry model. A slightly weaker assumption is also adopted by Wang et al. (2023) and justified as minimal requirement to {H)) as the trim constant.
learn the optimal policy. We use A o (-)H )
Assumption The inverse link function o (-) is I.-Lipchitz continuous on [A, A].
We further require the landscape of the value function and the policy network to be "regular", and impose the following assumption, which is a standard assumption used in nonconvex optimization literature (Liu et al. 2019, Bernstein al. 2018 Reddi et al. 2018).
Assumption The value function V ((=o) ( for the policy network parameters O is L-smooth on R
Since a trajectory reward is bounded in [0, H. (( < oo, where 0 is the global optimal solution. For simplicity, we assume L is the constant upper bound for both assumptions.
4.2 CONVERGENCE RATE AND SAMPLE COMPLEXITY
In this section, present the theoretical guarantees for both ZPG and ZBCPG under all three assumptions mentioned the previous sections. We aim to learn an e-stationary policy no with |VoV (VoV(T)) and study the convergence and sample complexity.
Theorem Choose the perturbation distance be μ² o ( V rate to be a O) M Q(H²) and we randomly pick On uniformly from the trajectory
}) and learning
(0u, ...... ,r-11 then the convergence rate of ZPG satisfies:
E [ O Hd d² Mog
M
Hdvd VN
T
VM
Theorem Choose the perturbation distance to be n =
o (max
WMT VAN
( and
learning
rate to be a = Odd-1). M = (2(²2 and we randomly pick On uniformly from the trajectory
(0n, .,, , 1T then the convergence rate of ZBCPG satisfies:
Hd
d² Voolog M
Hava VN
VoV
+
VM
The complete proof of both theorems is presented in the appendix. Here first provide insights into the choice of hyper-parametto and convergence rate results in both theorems, and then we discuss the challenges and technical novelties of our proof.
Insights behind the Convergence Rate. Both ZPG and ZBCPG have the same rate of convergence, which consists of three components: the zeroth-order gradient descent rate, the preference estimation error, and the value function approximation сгтоr
Hd
d Vloog M VM
Hdva VN
Zeroth-Ordie Gradient Descent
Preference Estimation
Value Punction Approximation
The second represents the error that occurs when using multiple human preferences [o,,1. M,,M] approximate the population-level human preference probability for given two trajectories, i.e., P(Tx.11 > Tn.0)- This error will further result in a bias term after being plugged into the inverse link function a (.) to construct an estimation the value function difference. The third term comes from the variance of using multiple trajectory rewards approximate the value function of a policy. The first term represents the error resulting from zeroth-order stochastic gradient de- scent blocked coordinate descent, which matches the state-of-the-ar analysis result (d/TT) for

---

Published as a conference paper at ICLR 2025
non-convex smooth function optimization (Nesterov & Spokoiny 2017). Even though the final con- vergence rates are the same and we both use constant learning rates, how we choose the perturbation distance to obtain the rate differs from (Ghadimi & Lan 2013). Specifically, they chose a small per- turbation distance with 1 = Odd/7 to make sure the zeroth-order approximation error is of lower order. However, this choice will not work for us, because non-linear nature of the link function in preference estimation. If we choose the perturbation dis- lance μ to be too small, the preference estimation error will be amplified by d/p due the formula of zeroth-order approximation 9L- This phenomenon adds complication to our theoretical analysis. Our method to use moderate perturbation distance μ.. Moreover, this moderate perturbation distance also balances the preference estimation and the value function approximation errors.
gradient estimate is biased due the
Based on the theorems, we have the following corollary that characterizes the sample complexity.
Corollary To learn an e-stationary policy, the required number of human preference queries of ZPG and ZBCPG with proper hyperparameters satisfies
TMN = =0 (
( H
)
d
log
4.3 TECHNICAL CHALLENGES AND PROOF NOVELTIES
This section provides overview of the proof of zeroth-order stochastic gradient descent used in (Ghadimi & Lan 2013; Nesterov & Spokoiny| 2017; Gao et al.) [2018] Liu et al. 2019) from Lyapunov drift optimization perspective. We then show the major technical difficulties in applying such a framework to analyze both ZPG and ZBCPG, i.e., the gradient estimator is biased due to
stochastic human preference. Then, we demonstrate our novel analysis techniques to resolve them.
Classic Proof of Zeroth-Order Optimization. To illustrate the procedure of the analysis of zeroth-order gradient estimate, we suppose we can query ((Ta) for any 9. This procedure makes use of the randomized smoothing function (0) (Ghadimi & Lan 2013; Gao et al. 2018)) as V (TT) = Eg, [V (Ta+wer)] where the random vector follows a uniform distribution over unit Euclidean ball. It is shown in (Gao et al., 2018) that the zeroth-order gradient estimator used in ZPG, constructed from sampling v, uniformly over a sphere, is an unbiased estimator of the smoothing function gradient, i.e.,
VoVA(TO) = E.p (V(To+ww) ((TO) ))
where is sampled from unit sphere. The value and gradient of the smoothing function different from the value function, but they are close as long as ja is small (Liu et al. (018b):
(Te V(Te)) = 0 (m²): (VVoV((Te) - VoV(To) l|2 O (ud).
(4)
The standard proof uses the randomized smoothing function Vj (me) as the Lyapunov function and then bounds the drift given the stochastic gradient descent update rule when a ((/dd). Neglect- ing wroblem-independen constants, we have:
V (To,)) (TT.
S - a VV +o (VoVi(TO.). (oV, 9e) + a² l19: (oV
Drift
1st Order: GradBias
2nd Order: GradVarssy
Note the gradient estimator 9. is unbiased and bounded, and the gradient of V, (TTe) is close to V (TTe). taking a conditional expectation over the filtration before time t will result in:
(TV [r] (mo, [F]]
(mo
s - a V < - 0: VoV (mo,) dd
+ (a d2 + a² d
9.)) + pd
where the last step uses equation 4 and the fact that the gradient is unbiased. Let us choose a small learning rate ((1dd) and take an expectation with a telescoping sum to obtain:
( )l - E[V, (TTr))
ΣT
V (To.
x -a
+ap
T
T
O(H/T)
Target
8

---

Published as a conference paper at ICLR 2025
A little manipulation will lead to the following bound, which can be made small when μ v
Target O H/a Ta
11
12dd)) = (
(4/ + 1 = + Hd
Hd
T
Amplified Gradient Biases for ZPG. If we directly apply the steps above to ZPG, we immedi- ately run into the issue that our gradient estimator 9e in expectation is biased even compared to the smoothing function gradient due to preference estimation. Moreover, the second-order gradient variance will be larger since we used the trajectory reward to estimate the value function. From con- centration, we obtain an error bound of using preference to estimate the value function difference:
(V))
E o (pr..) (V ((To.))) S
VM
where Ô hides logarithmic terms. This bias term will be amplified by d/p and then added to the gradient estimation bias in the first-order drift term if plugged into the analysis:
([V (V ) < - - VoV (12 + tzp d2 ta V (mo, l
PV M
Same Drift Before
Additional Bias
Using the same perturbation distance before, the additional bias will lead to an ((VT/M) term in the final bound, which is small only when M is much larger than T and is much looser compared with ours. For example, letting M = 722 the above bound is ((1/VT) while ours is (1/TT).
Our approach avoid this term in the final result is to make of the gradient value V (ooo)))) in the first-order term to cancel out the additional bias on certain occasions. Specifically, we divide the trajectory of 0g into two sets, with relatively large gradient and one with a relatively small gradient. For Og with a large gradient, we use a part of the negative drift to cancel out the additional bias, since the negative drift is the square of the gradient Vo V VoV(TT,) ). which even larger. For O, with small gradient, we know the bias term will be small and thus can provide refined drift bound. Combining this analysis with slightly larger perturbation distance p. we will be able to balance the additional bias with gradient variance to cancel out the ((VT/M) term and obtain the final result.
Implicit Smoothing Function for ZBCPG. Due to the choice of blocked perturbation vector sam- pling procedure, it is difficult obtain the exact analytical expression of the smoothing function (=() whose gradient is the expectation of gradient estimation g. for ZBCPG. This prohibits us from continuing to use V₁ (TT) as the Lyapunov function, as it is hard to analyze the gradient bias and the variance without explicit target format. However, if we rethink the reason for introducing the smoothed function in zeroth-order optimization, we hope the gradient of the smoothed function will be unbiased to cancel out the first-order positive drift. However, this is already not true in the analysis of ZPG since we have gradient estimation bias from human feedback, but it is small enough on average to be controlled. If the gradient difference between the smoothed function (T,) and the vanilla value function V (TTa) is smaller than this additional bias, then we can use the original value function V(TT)) the Lyapunov function at the cost of an additional bias besides preference estimation. Fortunately, this can be achieved through a carefully chosen perturbation distance μ to balance these two types of errors.
EXPERIMENTS
Algorithm
ZPG (Ours)
ZBCPG (Ours)
RM+PPO
DPO
Online DPO
Return
1.94 + 0.09
1.91 + 0.09
1.80 = 0.09
-4.13 = 0.09
1.71 + 0.09
Table 1: Last Iterate Policy Average Return with Tenry Feedback.
We study the empirical performance of ZPG and ZBCPG in stochastic GridWorld environment, where details can be found in Appendix C In our environment, the actions chosen by the agent may be reversed with certain probabilities due imperfect control environmental disturbances

---

Published as a conference paper at ICLR 2025
2PG IN+
BPO Drinn
Bicc
Num
-0
200
400
620
a0o
1000
25
50
75
300
125
153
375
200
Polay Eortt ons
Peticy ftrradooss
(a) performance
(b) parallelization
Figure 2: GridWorld with Bradley-Terry Feedback: (a) the trajectory return of ZPG, ZBCPG, and RLHF baselines, and (b) the return of ZBCPG with different parallelization levels. All results are averaged over 104 repetitions of policy evaluation, and shaded areas indicate confidence intervals.
such wind turbulence. The agent query human evaluators for preference over tra- jectories, and the human feedback is generated from the Bradley-Terry model with a logistic link function. We consider three baselines: (1) RM+PPO (Ouyang et al. 2022). (2) DPO for token-
level MDP (Rafailov et al., 2024b), and (3) Online DPO for token-level MDP (Dong et al. 2024
Guo al. 2024p. All algorithms collect N 1000 trajectory pairs between policy updates, and M 1000 human experts evaluate each pair. The trajectory return for each iteration is compared a). and the return of the final policy is reported in Tab. Both ZPG and ZBCPG perform better than the three baselines in both convergence rates and the quality of the last iterate policy. Compared to PPO, our algorithms converge to a better policy, partially because the reward model inaccurate and the agent is not able learn the optimal policy from it. It is also observed that vanilla DPO has much worse performance than our proposed algorithms. This may result from two reasons: first, the DPO loss is valid only in deterministic MDP, and second, DPO is constrained to the neighborhood of the sub-optimal reference policy. The online DPO algorithm improves over vanilla DPO but still has inferior performance due to the inherent model error of the DPO loss. This also shows the fundamental difference between stochastic and deterministic MDPs and the need to design RLHF algorithms for general RL problems. Moreover, online DPO converges much slower, partly because the DPO loss landscape becomes flat and hard to optimize when the weight of the KL constraint is small for better exploration. In Fig. 2b)), we also compare ZPG to distributed imple- mentations of ZBCPG, where the panel of human evaluators is also separated into small groups for parallelization. shown that as the number of blocks increases, ZBCPG converges faster sta- tionary policy. However, the number of human queries per pair of trajectories in each parallelization also decreases, which introduces a larger gradient bias and leads to sub-optimal policy. Therefore, the trade-off between computation parallelization and accuracy should be taken carefully.
Fig. aa),
6 CONCLUSION
In this paper, we proposed two RLHF algorithms without reward inference based on a zeroth-order policy gradient called ZPG and ZBCPG, which train the policy network directly from human pref- erences without global reward model. Both algorithms are shown have a provable polynomial sample complexity to leam stationary policy under mild conditions and exhibit nice empirical performances in environments with stochastic transitions, outperforming popular RI.FF baselines.
ACKNOWLEDGMENTS
The work of Qining Zhang and Lei Ying is supported in part by NSF under grants 21 12471, 2134081, 2207548, 2240981, and 2331780.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Nir Ailon, Zohar Karnin, and Thorsten Joachims. Reducing dueling bandits to cardinal bandits. In Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceed- ings of Machine Learning Research, pp. 856-864, Bejing, China, 22-24 Jun 2014. PMLR.
Riad Akrour, Mare Schoenauer, and Michele Sebag. Preference-basel policy learning. In Machine Learning and Knowledge Discovery in Databases, pp- 12-27, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.
Saurabh Arora and Prashant Doshi. A survey of inverse reinforcement learning: Challenges, methods and progress. Artificial Intelligence, 297:103500, 2021. ISSN 0004-3702. doi: https://doi.org/1000 a0.1
Mohammad Gheshlaghi Azar, Zhaohan Daniel Guo, Bilal Piot, Remi Munos, Mark Rowland, Michal Valko, and Daniele Calandriello. A general theoretical paradigm to understand learn- ing from human preferences. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pp. 4447- 4455. PMLR, 02-04 May 2024.
Hossein Azari, David Parks, and Lirong Xia. Random utility theory for social choice. Advances in Neural Information Processing Systems, 25, 2012.
Viktor Bengs, Robert Busa-Fekete, Adil El Mesaoudi- Paul, and Eyke Hullermeier. cefferencebbsee online learning with dueling bandits: survey. Journal of Machine Learning Research, 22(7): 1-108, 2021.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signSGD: Compressed optimisation for non-convex problems. In Proceedings of the 35th In- Ternational Conference on Machine Learning, volume 80 Proceedings of Machine Learning Research, pp. 560-569. PMLR, 10-15 Jul 2018.
Ralph Allan Bradley and Milton E. Terry. Rank analysis of incomplete block designs: the method of paired comparisons. Biometrika, 39(3/4):324-345 1952. ISSN 00063444, 14643510.
Róbert Busa-Fekete, Balázs Szörényi, Paul Weng, Weiwei Cheng, and Eyke Hüllermeier. Preference-based reinforcement learning: evolutionary direct policy search using a preference- based racing algorithm. Machine learning, 97:327-351, 2014.
Hanqin Cai, Yuchen Lou, Daniel Mckenzie, and Wotao Yin. A zeroth-order block coordinate de- scent algorithm for huge-scale black-box optimization. Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 1193-1203. PMLR, 18-24 Jul 2021.
Stephen Casper, Xander Davies, Claudia Shi, Thomas Krendl Gilbert, Jérémy Scheurer, Javier Rando Ramirez, Rachel Freedman, Tomasz Korbak, David Lindner, Pedro Freire, et al. Open problems and fundamental limitations of reinforcement learning from human feedback. Trans. Machine Learning Research (TMLR), 2023.
Souradip Chakraborty, Amrit Bedi, Alec Koppel, Huazheng Wang, Dinesh Manocha, Mengdi Wang, and Furong Huang. PARL: A unified framework for policy alignment reinforcement learning from human feedback. In The Twelfth International Conference Learning Representations, 2024.
Xiaoyu Chen, Han Zhong, Zhuoran Yang. Zhaoran Wang, and Liwei Wang. Human-in-the- Provably efficient preference based reinforcement learning with general function approximation. In Proceedings of the 39th International Conference Machine Learning, volume 162 of Pro- ceedings of Machine Learning Research, pp. 3773-3793. PMIR, 17-23 Jul 2022.
Paul Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.

---

Published as a conference paper at ICLR 2025
Edoardo Conti, Vashisht Madhavan, Felipe Petroski Such, Joel Lehman, Kenneth Stanley, and Jeff Clune. Improving exploration in evolution strategies for deep reinforcement learning via a popu- lation of sovelty-seeking agents. Advances in neural information processing systems, 31, 2018.
Hanze Dong, Wei Xiong, Bo Pang, Haoxiang Wang, Han Zhao, Yingbo Zhou, Nan Jiang, Doyen Sahoo, Caiming Xiong, and Tong Zhang. Rlhf workflow: From reward modeling to online rlhf. arXiv preprint arXiv:2405.077 078663 2024.
Yihan Du, Anna Winnicki, Gal Dalal, Shie Mannor, and R. Srikant. Exploration-driven policy op- timization in RLHF: Theoretical insights on efficient data utilization. In Forty-first International Conference on Machine Learning, 2024.
Kawin Ethayarajh, Winnie Xu, Niklas Muennighoff, Dan Jurafsky, and Douwe Kiela. Kto: Model alignment prospect theoretic optimization. arXiv preprint arXiv:2402.01306, 2024.
Xiang Gao, Bo Jiang, and Shuzhong Zhang. On the information-adappiie variants of the admm: iteration complexity perspective. Journal of Scientific Computing, 76:327-363, 2018.
Saced Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochas- tic programming, SIAM journal on optimization. 23(4):2341-2363 2013.
WH Greene. Modeling ordered choices: primer, 2010.
William H Greene. Econometric analysis 4th edition. International edition, New Jersey: Prentice Hall, pp. 201-215, 2000.
Shangmin Guo, Biao Zhang, Tianlin Liu, Tianqi Liu, Misha Khalman, Felipe Llinares, Alexandre Rame, Thomas Mesnard, Yao Zhao, Bilal Piot, et al. Direct language model alignment from online ai feedback. arXiv preprint 20t.:2402.0479... 2024.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- condition. In Paolo Frasconi, Niels Landwehr,
gradient methods under the Giuseppe Manco, and Jilles Vreeken (eds.), Machine Learning and Knowledge Discovery in Databases, pp. 795-811, 811, Cham, 2016. Springer International Publishing. ISBN 978-3-319- 46128-1.
Timo Kaufmmann Paul Weng, Viktor Bengs, and Eyke Hüllermeier. A survey of reinforcement learning from human feedback. arXiv preprint arXiv:2312.1492. 2023.
Chinmaya Kausik, Mirco Mutti, Aldo Pacchiano, and Ambuj Tewari. A framework for partially observed reward-states in rlhf. arXiv preprint arXiv:2402.03258 2024.
Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A. AI Sallab, Senthil Yo- gamani, and Patrick Pérez. Deep reinforcement learning for autonomous driving: sur- vey. IEEE Transactions on Intelligent Transportation Systems, 23(6):4909-499 4926, 2022. doi: 10. 1..10//TSS.222223355555 2021.305465..
Bradley Knox and Peter Stone. Tamer: Training an agent manually via evaluative reinforcement. In 2008 7th IEEE International Conference Development and Learning, pp. 292-297, 2008. doi:
Pushmeet Kohli, Mahyar Salek, and Greg Stoddard. fast bandit algorithm for recommendation to users with heterogenous tastes. Proceedings of the AAAI Conference on Artificial Intelligence, 27 11,1,, Jun. 2013, doi: 10.1609/aaai, 18463.
Dingwen Kong and Lin Yang. Provably feedback-efficice reinforcement learning via active reward learning. In Advances Neural Information Processing Systems, volume 35, pp. 11063-11078. Curran Associates, Inc., 2022.
Wataru Kumagai. Regret analysis for continuous dueling bandit. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Zihao Li, Zhuoran Yang, and Mengdi Wang. Reinforcement learning with human feedback: Learn- ing dynamic choices via pessimism. arXiv preprint arXiv:2305. 18438, 2023.
12

---

Published as a conference paper at ICLR 2025
Sijia Liu, Jie Chen, Pin- Yu Chen, and Alfred Hero. Zeroth-order online alternating direction method of multipliers: Convergence analysis and applications. In Proceedings of the Twenty-Fiin Interna- tional Conference Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pp. 287-297. PMLR, 09-11 Apr 2018a.
Sijia Liu, Bhavya Kailkhura, Pin- Yu Chen, Paishun Ting, Shiyu Chang, and Lisa Amini. Zeroth- order stochastic variance reduction for nonconvex optimization. Advances in Neural Informa- lion Processing Systems, volume 31. Curran Associates, Inc., 2018b.
Sijia Liu, Pin-Yo Yu Chen, Xiangyi Chen, and Mingyi Hong. signSGD via zeroth-order oracle. In International Conference on Learning Representations, 2019.
Zhaosong Lu and Lin Xiao. On the complexity analysis of randomized block-coordinate descent
methods. Mathematical Programming. 152:615 642, 2015.
Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason D Lee, Danqi Chen, and Sanjeev Arora. Fine-tuning language models with just forward passes. In Advances in Neural Information Processing Systems, volume 36, pp.
Curran Associates, Inc., 2023.
Reiichiro Nakano, Jacob Hilton, Suchir Balaji, Jeff Wu, Long Ouyang, Christina Kim, Christo- pher Hesse, Shantanu Jain, Vineet Kosaraju, William Saunders, et Webgpt: Browser-assisted with human feedback. arXiv preprint arXiv:2112.09332 2021.
Yu. Nesterov. Efficiency of coordinate descent methods huge-scale optimization problems. SIAM Journal on Optimization, 22(2):341-362, 2012. doi: 10. 10.1133/1108000001
Yurii Nesterov and Vladimir Spokoiny. Random gradient-free freee minimization of convex func- tions. Found. Comput. Math., 17(2):527-566, apr 2017. ISSN 1615-3375 doi: 10.1007/
110208-015-9296
Andrew Y. Ng and Stuart J. Russell. Algorithms for inverse reinforcement learning. In Proceedings of the Seventeenth International Conference on Machine Learning, ICMI '00, pp. 663-670, San Francisco, CA, USA, 2000. Morgan Kaufmann Publishers Inc. ISBN 1558607072.
Ellen Novoseller, Yibing Wei, Yanan Sui, Yisong Yue, and Joel Burdick. Dueling posterior sampling for preference-based reinforcement learning. In Proceedings of the 36th Conference on Uncer- tainty in Artificial Intelligence (UAI), volume 124 of Proceedings of Machine Learning Research, pp. 1029-1038. PMLR, 03-06 Aug 2020.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal. Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kel- ton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul F Christiano, Jan Leike, and Ryan Lowe. Training language models to follow instructions with human feedback. In Advances in Neural Information Processing Systems, volume 35, pp- 27730-27744. Curran As- sociates, Inc., 2022.
Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. In Ad- vances in Neural Information Processing Systems, volume 36, pp. 53728-53741. Curran Asso- ciates, Inc., 2023.
Rafael Rafailov, Yaswanth Chittepu, Ryan Park, Harshit Sikchi, Joey Hejna, Bradley Knox, Chelsea Finn, and Scott Niekum. Scaling laws for reward model overoptimization in direct alignment algorithms. arXiv preprint arXiv:2406.029900 2024a.
Rafael Rafailov, Joey Hejna, Ryan Park, and Chelsea Finn. From q": Your language model is secretly a q-function. In First Conference on Language Modeling, 2024b.
Ingo Rechenberg. Fxolutionsstrattegie. Optimierung technischer Systeme nach Prinzipien derbiolo- gischen Evolution, 1973.
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence adam and beyond. In International Conference Learning Representations, 2018.
13

---

Published as a conference paper at ICLR 2025
Aadirupa Saha, Aldo Pacchiano, and Jonathan Lee. Dueling rl: Reinforcement learning with tra- jectory preferences. In Proceedings of The 26th International Conference on Artificial Intelli- gence and Statistics, volume 206 of Proceedings of Machine Learning Research, pp. 6263-6289. PMIR, 25-27 Apr 2023.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies scalable alternative to reinforcement learning. arXiv preprint arXiv:/703.03880 2017.
Mare Schoenauer, Riad Akrour, Michele Sebag, and Jean-Christophe Souplet. Programming by feedback. In Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pp. 1503-1511, Bejing, China, 22-24 Jun 2014. PMLR.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano. Learning to summarize with human feedback. In Advances in Neural Information Processing Systems, volume 33, pp. 3008-3021. Curran Associates, Inc., 2020.
Yunhao Tang, Zhaohan Daniel Guo, Zeyu Zheng, Daniele Calandriello, Remi Munos, Mark Row- land, Pierre Harvey Richemond, Michal Valko, Bernardo Avila Pires, and Bilal Piot. Generalized preference optimization: unified approach offline alignment. In Forty-first International Conference Machine Learning, 2024a.
Zhiwei Tang, Dmitry Rybin, and Tsung-Hut Chang. Zeroth-order optimization meets human feed- back: Provable learning via ranking oracles. In The Twelfth International Conference on Learning Representations, 2024b.
LL Thurstone. A law of comparative judgment. Psychological Review, 34(4):273, 1927.
Kenneth E Train. Discrete choice methods with simulation. Cambridge university press, 2009.
Yuanhao Wang, Qinghua Liu, and Chi Jin. Is rlhf more difficult than standard rI? arXiv preprint arXiv:2306. 14111, 2023.
Garrett Warnell, Nicholas Waytowich, Vernon Lawhern, and Peter Stone. Deep tamer: Interactive agent shaping in high-dimensional state spaces. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1), Apr. 2018. doi: 10. v32il. 11485.
Aaron Wilson, Alan Fern, and Prasad Tadepalli. bayesian approach for policy learning from trajectory preference queries. In Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012.
Christian Wirth, Johannes Fürnkranz, and Gerhard Neumann. Model-free preference-based rein- forcement learning. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1), Mar. 2016. doi: 10. (tt.9//aai.v3001.10222.....
Christian Wirth, Riad Akrour, Gerhard Neumann, and Johannes Fürnkranz. A survey of preference- based reinforcement learning methods. Journal of Machine Learning Research, 18(136):1-46, 2017.
Jeff Wu, Long Ouyang, Daniel Ziegler, Nisan Stiennon, Ryan Lowe, Jan Leike, and Paul Christiano. Recursively summarizing books with human feedback. arXiv preprint arXiv:2109.108 2021.
Runzhe Wu and Wen Sun. Making RL with preference-based feedback efficient via randomization. In The Twelfth International Conference on Learning Representationss 2024.
Tengyang Xie, Dylan J Foster, Akshay Krishnamurthy, Corby Rosset, Ahmed Awadallah, and Alexander Rakhlin. Exploratory preference optimization: Harnessing implicit ga-appooxnnation for sample-efficient rlhf. arXiv preprint arXiv 2024.
14

---

Published as a conference paper at ICLR 2025
Wei Xiong, Hanze Dong. Chenlu Ye, Ziqi Wang, Han Zhong, Heng Ji, Nan Jiang, and Tong Zhang. Iterative preference learning from human feedback: Bridging theory and practice for RLHF under KL-constraint. In Forty-first first International Conference on Machine Learning. 2024.
Yichong Xu, Ruosong Wang, Lin Yang, Aarti Singh, and Artur Dubrawski. Preference-based inforcement learning with finite-time guarantees. In Advances in Neural Information Processing Systems, volume 33, pp. 18784-18794. Curran Associates, Inc., 2020.
Yisong Yue and Thorsten Joachims. Interactively optimizing information retrieval systems as a dueling bandits problem. In Proceedings of the 26th Annual International Conference on Machine Learning, ICML '09, pp. 1201-1208, New York, NY, USA, 2009. Association for Computing Machinery. ISBN 978 9781605585161.
doi: 041114//1553344155555555
Chunqiu Zeng, Qing Wang. Shekoofeh Mokhtari, and Tao Li. Online context-aware recommen- dation with time varying multi-armed bandit. In Proceedings of the 22nd ACM SIGKDD In- ternational Conference Knowledge Discovery and Data Mining, KDD '16, pp. 2025-2034, New York. NY. USA. 2016. Association for Computing Machinery. ISBN 9781450342322. doi: 10.11457939672.299987..
Wenhao Zhan, Masatoshi Uehara, Nathan Kallus, Jason D. Lee, and Wen Sun. Provable offline preference-based reinforcement learning. In The Twelfth International Conference on Learning Representations, 2024a.
Wenhao Zhan, Masatoshi Uehara, Wen Sun, and Jason D. Lee. Provable reward-agnostic preference- based reinforcement learning. In The Twelfth International Conference on Learning Representa- lions, 2024b.
Qining Zhang, Honghao Wei, and Lei Ying. Reinforcement learning from human feedback without reward inference: Model-free algorithm and Instance-dependen analysis. Reinforcement Learn- ing Journal, 1251, 2024a.
Yihua Zhang, Pingzhi Li, Junyuan Hong, Jiaxiang Li, Yimeng Zhang, Wenqing Zheng, Pin-Y Yu Chen, Jason D. Lee, Wotao Yin, Mingyi Hong. Zhangyang Wang. Sijia Liu, and Tianlong Chen. Revisiting zeroth-order optimization for memory-efficient LLM fine-tuning: A benchmark. In Forty-first International Conference on Machine Learning, 2024b.
Yao Zhao, Rishabh Joshi, Tianqi Liu, Misha Khalman, Mohammad Salch, and Peter J Liu. Slic-hf: Sequence likelihood calibration with human feedback. arXiv preprint arXiv:2305.10425 2023.
Banghua Zhu, Michael Jordan, and Jiantao Jiao. Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. In Proceedings of the 40th International Con- ference on Machine Learning. volume 202 of Proceedings of Machine Learning Research, pp. 43037-43067. PMLR, 23-29 Jul 2023.
Banghua Zhu, Michael Jordan, and Jiantao Jiao. Iterative data smoothing: Mitigating reward overfit- ting and overoptimization RLHF. In Forty-first International Conference on Machine Learning, 2024.
Daniel Ziegler. Nisan Stiennon, Jeffrey Wu, Tom Brown, Alec Radford, Dario Amodei, Paul Chris- tiano, and Geoffrey Irving. Fine-tuning language models from human preferences. arXiv preprint arXiv: /90p:/999.0999 2019.
15


Reviews:
[{"review_id": "lbOqTyBmyr", "reviewer": "Reviewer_6Mwn", "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.", "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.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "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.\n\nI am open to improving my score if the authors can give an argument as to why their work improves upon the cited work.\n\n\n\nReferences:\n\n\nTengyang Xie, Dylan J. Foster, Akshay Krishnamurthy, Corby Rosset, Ahmed Awadallah, and Alexander Rakhlin. Exploratory preference \n optimization: Harnessing implicit q*-approximation for sample-efficient rlhf, 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vSDgxjRX4N", "reviewer": "Reviewer_HH3A", "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.", "questions": "### === Zero-order method in deep RL ===\n\nThe 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.\n\n[1] Salisman et al, 2017, Evolution Strategies as a Scalable Alternative to Reinforcement Learning\n\n### === Relevance to RLHF ===\n\nIt'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.\n\n### === Empirical ===\n\nThere 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.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dPbNbob4KW", "reviewer": "Reviewer_BWEU", "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.", "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?\n- 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.\n\n-- After Author Response --\nThank you for adding the additional numerical experiments and non-BT explanations. I have increased my score.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The methods ZPG and ZBCPG work for a general class of link functions (beyond the BT-model) and stochastic dynamics as well.\n- 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.\n- Zero-th order methods may be slower than gradient-based methods, especially for very large models like LLMs.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zwTV9mSvZF", "reviewer": "Reviewer_9HsE", "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.", "questions": "## Lack of discussion \n* 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?\n* 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)?\n* 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)?\n* 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?\n\n## No empirical study\n* 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?\n\n## Aspects to clarify and/or correct \n* 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)?\n* 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?\n* There is a typo l. 305 (as written, the gradient is always zero, issue in the second value index)\n* 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)?\n* 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).\n* Corollary 1 doesn’t seem to be proven, even in the appendix, can you provide a proof?\n* l. 435, how does $\\theta^*$ appear with a telescoping argument (plus, the corresponding equation in the appendix involves $\\theta_T$, which seems more logical)?\n* 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)\n* l. 977, typo (parenthesis)\n* l. 1014, is it the same $L$ as in Assm 3?\n* 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?\n* l. 1214, there is a missing term (or the line should be removed) * l. 1230-1241, why the 3 factor? (not wrong, but why)", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The proposed algorithms are interesting, at least from a theoretical viewpoint\n* The paper is overall clearly and well written\n* There is a nice discussion of the technical difficulties for proving their results, which is quite helpful\n* 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.\n*  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.\n* There are parts of the paper and of the proofs that are not totally clear, see questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)