- 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 without any additional algorithmic modification.
Critical weaknesses
-
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 -stationarity of Zhang & Cutkosky (2024) by removing the condition . 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.
-
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 , 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.
-
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
-
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"?
-
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 (), while Eq. 14 also reports the number of trajectories (). 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
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 ? Is the additional 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 -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 , Markov's inequality gives
$ \mathbb P(|X-x|>\delta) \leq \frac{\epsilon^2}{\mu\delta^2}. $
Since the subgradients are bounded by , removing these contributions introduces an error of at most . Controlling this error at the level requires , compared with in the opposite direction. This difference leads to the additional factor in our complexity bound through its dependence on .
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 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 from for existing vanilla ZO-SGD-type methods to , yielding an improvement by a factor of . 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.
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.
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, 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=Θ(μ). Consequently, our O(dμϵ−4) convergence rate matches the dimension–accuracy dependence of this lower bound, further demonstrating the theoretical significance of our stationarity criterion.
The apparent discrepancy arises because the two conversion directions in Proposition 6 require different choices of μ. Specifically, converting Goldstein stationarity to our expected stationarity with μ=Θ(ϵ2/δ2) incurs no additional complexity factor, yielding the rate O(dμϵ−4). In contrast, converting our expected-stationarity guarantee back to Goldstein stationarity requires μ=Θ(Gϵ/δ2), which introduces an additional factor of ϵ−1/2, resulting in O(dδ−1ϵ−7/2) rather than the best-known O(dδ−1ϵ−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.
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.
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).