acceptodds
Under review as a conference paper at ICLR 2027

Zeroth-Order Momentum and Adaptive Methods for Nonsmooth Policy Optimization from Human Preferences

Abstract

Reinforcement learning from human feedback (RLHF) commonly relies on reward models to convert human preferences into optimization signals, but reward inference introduces an additional modeling step and may suffer from reward misspecification. To avoid reward inference, direct policy optimization methods learn policies directly from human preferences without explicitly fitting a reward model, for which zeroth-order optimization provides a natural optimization framework. Existing zeroth-order policy methods such as zhang2025zeroth rely on smooth policy objectives, leaving the nonsmooth setting less understood. Meanwhile, momentum has shown favorable theoretical and empirical properties, motivating its study in preference-based zeroth-order policy optimization. In this work, we study zeroth-order policy optimization from human preferences for general objectives that may be nonsmooth and nonconvex. We establish a refined characterization of the preference oracle induced by pairwise human feedback for reward-model-free RLHF. We further establish a unified convergence framework for momentum-based and adaptive-gradient zeroth-order nonsmooth policy optimization methods, called ZOPGM and ZOPGAM. Both methods achieve a -expected stationarity (a natural relaxation of -Goldstein stationarity) outer-loop complexity of . This rate matches the parameter dependence obtained by translating the best-known zeroth-order Goldstein-stationarity bound to expected stationarity. Accounting for preference-oracle sampling yields a total human preference query complexity of . Experiments in controlled preference-based policy optimization environments demonstrate consistent improvements in preference-query efficiency over zeroth-order baselines across different preference-feedback budgets, supporting the view that momentum helps exploit information accumulated from historical preference-induced updates.

Primary area:
optimization
Keywords:
Optimization, RLHF, Zeroth-order methods, Momentum

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_eUyZOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The authors study policy optimization from trajectory preferences without a reward model, in the setting where the policy objective may be nonsmooth and nonconvex. Following the previous ZO framework of Zhang & Ying (2025), they first bound the bias and second moment of this estimator and show that each term of the bounds is sharp. Then, they analyze a momentum method ZOPGM and its variant ZOPGAM driven by this biased oracle under an expected stationarity criterion. Finally, they apply this guarantee to Goldstein stationarity of the original objective and derive the total number of preference labels required. Experiments on GridWorld, Risky Bandit, and Acrobot compare the methods against ZO, DPO, and reward-based baselines.

Critical strengths

The paper is well written, and the authors state their position and theoretical motivation clearly. The notation largely follows standard conventions, and despite the technical density, each new concept is introduced together with sentences that explain why it is needed. For example, the role of expected stationarity in analyzing momentum and its relation to Goldstein stationarity are explained before they are used, and Remark 1 makes clear where the dimension dependence of the final rate comes from. As a result, I believe the authors have well-polished this theory-heavy paper to make it easy to follow.

Also,the theoretical results are solid and useful. This refinement alone improves the dimension dependence of the label complexity over Zhang & Ying (2025). Theorem 2 makes the optimization dynamics independent of the dimension, so that under the same Goldstein criterion and the same oracle, the momentum method reduces the outer iteration complexity of plain ZO method by a factor of d1/2ϵ−1/2d^{1/2}\epsilon^{-1/2} without any additional algorithmic modification.

Critical weaknesses
  1. The authors report their improvements over prior work, but it is hard to see where the theoretical novelty of the analysis lies. For example, Definition 2 appears to relax the (c,ϵ)(c,\epsilon)-stationarity of Zhang & Cutkosky (2024) by removing the condition E[X]=x\mathbb{E}[X]=x. The authors cite that work but do not discuss this relation. A short summary of how two definitions differ and what the change brings would convey the theoretical contribution more accurately.

  2. The abstract states that the rate "matches the parameter dependence obtained by translating the best-known zeroth-order Goldstein-stationarity bound to expected stationarity", while Remark 2 states that "the resulting Goldstein complexity does not match the best known rate". Since Proposition 6 shows that the two notions can be converted into each other, these two statements read as conflicting. The difference comes from the two directions of Proposition 6 requiring different values of μ\mu, but the paper does not explain why the rate is the best known under expected stationarity yet not under Goldstein stationarity. I may have missed or misunderstood something here, so I would appreciate it if the authors could clarify this point in their response.

  3. The experiments are run on simple toy environments, yet the GridWorld and Risky Bandit results use only five seeds. Since such environments are cheap to simulate, more seeds (30~50) would be needed for the comparisons to be reliable. Also, the paper does not clarify why and how the proposed ZO methods successfully escape suboptimality. So, it is hard to tell whether this advantage generalizes beyond the tested environments (see Questions 1 and 2). Although the paper is mainly theoretical, this is my main concern and I would be willing to raise my score depending on the authors' explanation of this point.

Questions for authors
  1. In Risky Bandit, all methods other than the zeroth-order ones remain suboptimal. Could the authors explain why the zeroth-order methods recover the optimal action, and elaborate on the statement "inversion before averaging preserves expected-return differences rather than majority preference"?

  2. Could the authors report Risky Bandit variants in which the risky action has a lower expected return than the safe action, for example a reward of 2.5 with probability 0.2 or a reward of 10 with probability 0.05, and show whether the proposed methods then converge to the safe action?

Minor comments

  • Line 027, 086: the acronyms ZPG, ZOPGM, and ZOPGAM are never expanded.
  • Line 415: ZO-SGD and ZO-Adam are mentioned without citations.
  • Table 1 reports the preference labels per iteration (NMNM), while Eq. 14 also reports the number of trajectories (2NT2NT). Presenting both costs in Table 1 would improve consistency.
  • Table 1 reports ZOPGM and ZOPGAM only under the Goldstein criterion, while ZO-AdaMM and ZPG are reported under the gradient norm criterion for smooth objectives. Adding the rates of ZOPGM and ZOPGAM in the smooth case, which follow from Proposition 7(b), would make the comparison with ZPG direct.

Rebuttal update

Since the author's response have resolved my concerns, I raise my score from 3 to 4.

5 comments

We greatly appreciate the reviewer for the careful reading and insightful suggestions. We have carefully addressed the concerns raised and revised the manuscript accordingly. We hope these clarifications and revisions help better convey our contributions.

Weakness 1. Clarification of the theoretical novelty

We agree that Definition 2 relaxes the stationarity criterion of Zhang and Cutkosky (2024), and we appreciate the opportunity to clarify its motivation and theoretical role. Specifically, our definition removes the centering constraint E[X]=x\mathbb E[X]=x, uses the squared norm of the averaged subgradient, and accommodates Clarke subgradients for nonsmooth objectives. This relaxation allows us to use actual policy iterates as outputs while constructing stationarity witnesses from the exponentially weighted historical iterates underlying momentum, without requiring their mean to equal the output. More importantly, the squared formulation enables our analysis to separate persistent preference-oracle bias from stochastic noise, leading to the unified convergence guarantee in Theorem 2 for both momentum and adaptive updates. Unlike Zhang and Cutkosky (2024), our analysis accommodates biased preference-based zeroth-order estimators without randomized update scaling. Furthermore, Propositions 6–7 establish quantitative connections to Goldstein stationarity and gradient stationarity, ensuring that the relaxed criterion retains meaningful optimization guarantees. We have added an explicit comparison and explanation of these distinctions in the revised manuscript (Line 240-246).

Moreover, the very recent smooth stochastic zeroth-order lower bound established by [1] directly extends to our expected-stationarity criterion, since gradient stationarity and our criterion are equivalent up to constant factors for smooth objectives when H=Θ(μ)H=\Theta(\sqrt{\mu}). Consequently, our O(dμϵ−4)O(d\sqrt{\mu}\epsilon^{-4}) convergence rate matches the dimension–accuracy dependence of this lower bound, further demonstrating the theoretical significance of our stationarity criterion.

Weakness 2. Clarification of expected versus Goldstein stationarity rates

The apparent discrepancy arises because the two conversion directions in Proposition 6 require different choices of μ\mu. Specifically, converting Goldstein stationarity to our expected stationarity with μ=Θ(ϵ2/δ2)\mu=\Theta(\epsilon^2/\delta^2) incurs no additional complexity factor, yielding the rate O(dμϵ−4)O(d\sqrt{\mu}\epsilon^{-4}). In contrast, converting our expected-stationarity guarantee back to Goldstein stationarity requires μ=Θ(Gϵ/δ2)\mu=\Theta(G\epsilon/\delta^2), which introduces an additional factor of ϵ−1/2\epsilon^{-1/2}, resulting in O(dδ−1ϵ−7/2)O(d\delta^{-1}\epsilon^{-7/2}) rather than the best-known O(dδ−1ϵ−3)O(d\delta^{-1}\epsilon^{-3}) rate. Thus, the two statements are consistent: our result matches the rate obtained by translating the best-known Goldstein guarantee into expected stationarity, while the reverse conversion incurs an additional cost.

Weakness 3 and Question 1. Clarification of why ZO methods recover the optimal action

As explained in Lines 162–177, our methods apply the inverse preference link to each trajectory pair before averaging, thereby recovering expected-return differences rather than majority preferences. This distinction is crucial in Risky Bandit, where the risky action has a higher expected return despite losing most pairwise comparisons. Preference-based first-order baselines such as DPO optimize surrogate objectives based on preference likelihoods, which need not align with expected-return maximization, while RM+PPO additionally relies on the accuracy of its learned reward model. In contrast, our ZO estimator directly targets expected-return differences, with finite-sample estimation errors controlled by Theorem 1 and stochastic variability further reduced through momentum. This explains the observed advantage under misleading majority preferences.

Weakness 3 and Question 2. Experimental reliability and generalizability

We have updated main experiments to use 50 random seeds, and the main conclusions remain unchanged. To further examine the generalizability of our findings, we have also added Risky Bandit experiments in which the safe action has a higher expected return than the risky action (Lines 1806–1830). The results show that our methods consistently identify the action with the higher expected return, regardless of whether it is safe or risky, further supporting the robustness of our findings.

We have revised the relevant sections accordingly and hope these improvements enhance clarity, reduce the burden on readers, and make our contributions easier to understand and assess. We are more than willing to clarify any confusion arising from insufficiently clear explanations in our manuscript.

[1] Xia, Yuxuan, and Xiao-Tong Yuan. "On global joint lower bounds in zeroth-order nonconvex optimization." arXiv preprint arXiv:2610.19652 (2026).

Thank you for your detailed response and for the additional experiments. My main concern regarding W3 has been fully addressed.

I have one remaining question regarding W2. If I understand correctly, the asymmetry between the two directions of Proposition 6 arises because expected stationarity only penalizes the mean squared distance of the witness. Could you provide more intuition on why this makes converting back to Goldstein stationarity require a larger μ\mu? Is the additional ϵ−1/2\epsilon^{-1/2} factor intrinsic to the criterion, or could a sharper analysis remove it?

We are very pleased that our revisions have addressed the reviewer's concerns regarding the experimental validation and the ability of our methods to identify actions with higher expected returns. We sincerely appreciate the reviewer's careful follow-up question.

The key distinction lies in the localization of the stationarity witness. Goldstein stationarity requires all contributing subgradients to come from within a δ\delta-neighborhood of the current point, whereas expected stationarity only controls the mean squared distance of the witness. Consequently, expected stationarity allows a small probability mass at distant points to cancel the gradients near the current point, even when the latter do not satisfy Goldstein stationarity.

To convert expected stationarity back to Goldstein stationarity, these distant contributions must be removed. Specifically, when Sμh(x)≤ϵS_\mu^h(x)\leq\epsilon, Markov's inequality gives

$ \mathbb P(|X-x|>\delta) \leq \frac{\epsilon^2}{\mu\delta^2}. $

Since the subgradients are bounded by GG, removing these contributions introduces an error of at most 2Gϵ2/(μδ2)2G\epsilon^2/(\mu\delta^2). Controlling this error at the O(ϵ)O(\epsilon) level requires μ=Ω(Gϵ/δ2)\mu=\Omega(G\epsilon/\delta^2), compared with μ=Θ(ϵ2/δ2)\mu=\Theta(\epsilon^2/\delta^2) in the opposite direction. This difference leads to the additional ϵ−1/2\epsilon^{-1/2} factor in our complexity bound through its dependence on μ\sqrt{\mu}.

Intuitively, expected stationarity allows a small probability mass at distant witness points to cancel nearby gradients while incurring only a small expected squared-distance penalty. A larger μ\mu is therefore necessary to penalize such distant contributions more strongly and ensure that the resulting stationarity guarantee is sufficiently localized for Goldstein stationarity.

Importantly, this scaling reflects a genuine limitation of the general conversion between the two criteria, rather than an inherent limitation of our optimization method. Even under the Goldstein stationarity criterion, our methods improve the dependence on ϵ\epsilon from O(ϵ−4)O(\epsilon^{-4}) for existing vanilla ZO-SGD-type methods to O(ϵ−7/2)O(\epsilon^{-7/2}), yielding an improvement by a factor of ϵ−1/2\epsilon^{-1/2}. Furthermore, the matching lower bounds cited in our manuscript establish the optimality of our result under the expected-stationarity criterion. Therefore, the remaining gap only arises from the conversion to Goldstein stationarity. A sharper, algorithm-specific analysis may potentially avoid this conversion loss.

We have added this explanation and a supporting example to the revised manuscript (Lines 770–796). We thank the reviewer again for the valuable question and hope this clarification addresses the reviewer's concern.

Reviewer_67J9OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

This paper studies the zeroth order optimization of nonsmooth preference learning problems. Previous works study either smooth optimization of preference learning or nonsmooth optimization with an unbiased stochastic first-order oracle. This paper combines these techniques and design two algorithms to solve the nonsmooth preference learning problem. The main idea is to control the bias induced by the mapping from preference to reward and use momentum to solve the nonsmooth problem while including the gradient bias into analysis. They conduct some small-scale experiments to show that their proposed algorithms are better than previous zeroth order methods.

Critical strengths
  • I think this paper is a comprehensive theoretical work on zeroth order optimization of nonsmooth preference learning models, extending the results of [1] to nonsmooth objectives (requiring Lipschitz though) and extending [2] to preference learning.
  • The experiments show consistent improvements over existing zeroth-order baselines, though the contribution of proposed components are unclear (see weakness section).

[1] Zeroth-order policy gradient for reinforcement learning from human feedback without reward inference. ICLR 2025.

[2] Random scaling and momentum for non-smooth non-convex optimization. ICML 2024.

Critical weaknesses
  • This paper is densely written and very hard to follow. The authors put too much technical details in the main content while the intuitive understandings are severely lacked. It would be better to manually polish the paper writing, such as listing some intuitions before presenting the whole theorem, to make the paper more friendly to readers.
  • Aside from the proposed momentum method, the proposed methods use a symmetric two-point estimator, while the ZPG/ZBCPG baselines use forward finite differences. It's unclear whether the symmetric two-point estimator is necessary. It would be better to provide some theoretical or intuitive explanations. And in experiments, an additional baseline using the symmetric estimator without momentum would be important to include. Otherwise, the advantages shown in Figure 1 are unconvincing.
Questions for authors

Corollary 4 requires ϵad=R\epsilon_{ad}=R, while in experiments, ϵad\epsilon_{ad} is set super small (10−810^{-8}). Can you explain this misalignment?

5 comments

We sincerely appreciate the reviewer's careful evaluation and constructive feedback. The comments have been valuable in helping us clarify our contributions and improve the presentation of our work. We address each concern in detail below.

Weakness 1. Clarity and accessibility of presentation

We have revised the main text to improve the logical flow between sections and provide clearer intuitions and motivations behind our key results, particularly explaining why each technical step is necessary. We hope these revisions improve readability and help the reviewer better appreciate and assess our contributions.

Weakness 2. Clarification of the symmetric estimator's role

From a theoretical perspective, both forward and symmetric two-point estimators are applicable within our framework. We adopt the symmetric estimator primarily for its balanced formulation and analytical convenience, rather than theoretical necessity, as the relevant oracle bounds retain the same order up to constant factors. To disentangle the contributions of the estimator and momentum, we have added ablation experiments (Lines 1836–1859), including a symmetric estimator without momentum. The results suggest that symmetric estimation improves empirical stability, while the benefits of momentum remain evident, particularly under the asymmetric Weibull preference link. These findings further support that the observed improvements cannot be attributed solely to the choice of estimator.

Question. Discrepancy between theoretical and experimental parameter settings

Corollary 4 adopts the conservative theoretical choice ϵad=R\epsilon_{\mathrm{ad}}=R to ensure the required effective stepsize bounds, whereas our original experiments used the commonly adopted small stabilizer ϵad=10−8\epsilon_{\mathrm{ad}}=10^{-8}. To reduce this discrepancy, we have updated most experiments to use ϵad=1\epsilon_{\mathrm{ad}}=1, and the main empirical conclusions remain unchanged. We also note that the theoretical requirement may be relaxed, although doing so under our current analysis would worsen the convergence guarantees.

We thank the reviewer again for the thoughtful comments and suggestions. We have carefully revised the manuscript to address the concerns raised and hope that our responses and additional results provide a clearer understanding of the theoretical contributions and empirical findings of our work.

Thank you for your rebuttal. Could you mark the changes in the revised paper using a different color?

We thank the reviewer for this helpful suggestion. We have revised the manuscript and highlighted the major changes made in response to all reviewers' comments in blue for ease of reference.

Reviewer_paQHOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies policy optimization from pairwise trajectory preferences without fitting a reward model. It assumes a known preference link and estimates return differences by inverting repeated comparisons for each trajectory pair. The authors separate the estimator's bias and sampling error, and analyze momentum and a scalar adaptive variant for nonsmooth objectives. They establish expected-stationarity guarantees for the smoothed objective and transfer them to expected Goldstein stationarity for the original objective, with explicit trajectory and preference-label costs. Experiments on GridWorld, Risky Bandit, and Acrobot support improved optimization efficiency over the tested zeroth-order baselines.

Critical strengths
  1. I found the oracle analysis useful. Theorem 1 separates finite-label bias from sampling noise, and Appendix D gives examples that attain the leading terms. This explains which errors momentum can average out and which remain even with more trajectory pairs. It also makes the preference-query cost easier to assess.

  2. The experiments include more than the large-batch setting in the main text. Appendix I compares methods at a fixed label budget and tests Acrobot with one comparison per update over 20 held-out seeds. Together with the same-oracle SGD comparison in Appendix H, these results give some support for the benefit of momentum.

Critical weaknesses
  1. I do not find the comparison with DPO and RM+PPO convincing as presented. The proposed methods use the correct preference link, while all three non-ZO baselines use a Bradley–Terry loss even under Weibull feedback (Appendix I). RM+PPO also keeps its initially fitted reward model fixed. These choices make it hard to tell how much of the gap comes from the optimizer. The main GridWorld and Risky Bandit runs use one million labels per ZO update, which further limits their practical relevance. The low-budget Acrobot experiment helps, but it only compares the ZO methods.

  2. The factor-d^5 improvement needs a more informative comparison. The bounds being compared use different assumptions, stationarity criteria, and sample allocations. How much of the improvement would remain if the authors applied their sharper oracle bounds to the earlier ZPG method? Appendix H answers a related question for nonsmooth SGD, but not this one. Since the algorithm adds standard momentum and scalar adaptation, this distinction matters to my assessment of the contribution. The matching examples establish sharpness of the estimator bounds, not optimality of the full method.

Questions for authors
  1. In the headline expected-stationarity claim, is the target F or its smoothed version F_nu? Please give the corresponding choice of nu as a function of both mu and epsilon when claiming expected stationarity for F. Appendix B identifies the additional smoothing term, but the main claim is easy to read more broadly.

  2. What bound results if the refined preference-oracle analysis is applied to the original smooth ZPG update under a matched stationarity criterion? This would separate improved oracle accounting from the benefit of momentum.

  3. Do the conclusions against reward-model-based methods persist when those methods use the correct feedback link and a comparable online data budget? A result on the existing controlled environments would address this question; a new large-scale application is not necessary.

2 comments

We thank the reviewer for the thorough assessment and valuable suggestions. We appreciate the opportunity to clarify our key contributions and address the questions raised. Our detailed responses are provided below.

Weakness 1 and Question 3. Unfair baseline comparisons and excessive preference-label budgets

Our experiments largely follow [1], which acknowledges the preference-link mismatch and reports that it does not affect the qualitative conclusions. Nevertheless, to ensure fairness, we have revised all non-ZO baselines to use matched preference likelihoods. The original budget of one million labels per update also follows [1]. To address concerns about practicality, we additionally provide low-budget experiments (Lines 1782–1804) and non-ZO comparisons on Acrobot (Lines 1674–1687). These additional results confirm that our main conclusions remain unchanged.

Weakness 2 and Question 2. Clarification of the d5d^{5} improvement and its sources

We acknowledge that our sharp preference-oracle analysis can also be applied to [1], yielding a potential d5d^{5} improvement in its dimension dependence. However, our main contribution goes beyond this oracle refinement. In particular, the recent smooth stochastic zeroth-order lower bound established by [2] directly implies an Ω(dμϵ−4)\Omega(d\sqrt{\mu}\epsilon^{-4}) lower bound for expected stationarity by considering smooth objectives with H=Θ(μ)H=\Theta(\sqrt{\mu}), matching the dimension–accuracy dependence of our result. For Goldstein stationarity, our method improves the ϵ\epsilon-dependence of vanilla ZO-SGD and ZO-AdaMM by a factor of ϵ−1/2\epsilon^{-1/2} using only standard momentum, while in the smooth setting, our gradient-stationarity rate also matches the corresponding lower-bound scaling. We have clarified these distinctions in Table 1 and Section 6 (Comparisons). Importantly, our work also fills a gap in the theoretical understanding of nonsmooth RLHF, which was not covered by previous preference-based zeroth-order methods.

Question 1. Clarification of the expected-stationarity guarantee

Yes, our intended expected-stationarity guarantee concerns the original nonsmooth objective FF, obtained by transferring the guarantee from its smoothed version FνF_\nu. As established in Appendix B,

$\mathbb E S_\mu^F(x_s)^2 \le \mathbb E S_\mu^{F_\nu}(x_s)^2 +\frac{\mu\nu^2d}{d+2}.$

By choosing ν=O(ϵμ−1/2)\nu=O(\epsilon\mu^{-1/2}) and controlling the smoothed expected-stationarity error, we obtain the desired guarantee for FF. We have clarified this distinction and the corresponding smoothing choice in the revised abstract.

We are grateful for the reviewer's constructive feedback, which has helped us strengthen both the clarity and presentation of our work. We hope that our explanations and revisions satisfactorily address the concerns and provide a more comprehensive understanding of our contributions.

[1] Qining Zhang and Lei Ying. Zeroth-Order Policy Gradient for Reinforcement Learning from Human Feedback without Reward Inference. International Conference on Learning Representations (ICLR), 2025.

[2] Xia, Yuxuan, and Xiao-Tong Yuan. "On global joint lower bounds in zeroth-order nonconvex optimization." arXiv preprint arXiv:2610.19652 (2026).

Dear Reviewer paQH,

We sincerely appreciate your careful evaluation of our work. We have addressed all your concerns and revised the manuscript accordingly. Please feel free to reach out if you have any remaining questions; we are happy to provide further clarifications.

Best regards,

The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.