- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies online iterative NLHF. It first shows that INPO-style iterative updates can need samples on a three-response instance. It then proposes ENPO, which adds an SFT-style likelihood term on the learner's own samples to the INPO squared loss and selects an explorer policy through a ratio-type maximization. Under realizability and bounded log-ratio assumptions, ENPO obtains a best-iterate bound without dependence. BENPO, a variant built on minimax oracles, obtains cumulative gap. A practical surrogate, DENPO, is evaluated on Llama-3-8B-Instruct against INPO and XPO.
Critical strengths
The question of whether iterative NLHF can achieve sample efficiency without minimax oracles is relevant.
The lower bound construction for INPO is explicit and checkable, and the mirror descent target and residual formulation in Eqs. (3), (10), and (16) are internally consistent.
Critical weaknesses
-
Theorem B.10, which supports the regret bound and the uniform mixture output, relies on Assumption B.4. For a finite containing , B.4 requires the mirror descent orbit to reach exactly in finitely many steps. The relaxed Assumption B.7 with ties the policy class to the horizon and yields only a best-iterate bound, , whose selection requires evaluating the duality gap and hence knowledge of .
-
The explorer step in Eq. (5) is a joint maximization over , and the paper does not show it to be easier to implement than the minimax oracles it replaces. Re-estimating on historical atoms costs queries per round, so the rate in terms of preference queries is far slower than . The algorithm draws prompt-independent opponents, whereas the proof assumes prompt-conditional ones.
-
The theory requires , while the experiments use between and with no stated correspondence to the theoretical parameters. DENPO replaces the explorer step with an unanalyzed surrogate, runs for only , and compares only with INPO and XPO.
Questions for authors
- Does the regret bound for the uniform mixture output hold under Assumption B.7 alone?
- How is selected without access to ?
- In Lemma B.9, the INPO loss vanishes for every when only is sampled. Does the lower bound then rely on choosing among the minimizers?
- Can the main text explain why a forward KL term toward complements the reverse KL proximal term in Eq. (2)?
- How do the experimental and correspond to the theoretical stepsize ?
5 comments
Author Rebuttals
In Lemma B.9, the INPO loss vanishes for every when only is sampled. Does the lower bound then rely on choosing among the minimizers?
Thank you for this question.
Yes, we agree that it would make the argument more robust if the lower bound did not depend on a special tie-breaking rule. We have replaced the earlier example with a new instance satisfying our updated assumptions, in which every empirical update has a unique minimizer on the event establishing the lower bound. Thus, the revised proposition is independent of how ties are resolved.
The same instance works for every batch size, including a batch size of one. INPO still requires exponentially many preference queries in even to achieve a constant duality gap. We have updated Proposition 3.2 and provided the corresponding proof in the paper.
Can the team explain why a forward KL term toward complements the reverse KL proximal term in Eq. (2)?
Thank you for the question. This is a very interesting question.
The SFT term acts as a forward KL penalty toward the current policy, and it discourages the learner from dropping probability on responses covered by the current data, while the reverse KL proximal term controls movement away from the previous policy. The two terms therefore provide complementary control of the policy update.
This additional control is useful when learning an equilibrium, where we must compare the learner against opponents that may be poorly covered by the data. We think this is a very interesting observation and might have broader implications in RL and learning in games. We added an explanation for this complementary control interpretation in Appendix C.1 of the revised paper.
The theory requires , while the experiments use between and with no stated correspondence to the theoretical parameters.
How do the experimental and correspond to the theoretical stepsize ?
Thank you for raising this good point.
The theoretical stepsizes are conservative sufficient choices for controlling accumulated optimization and statistical errors over a long training horizon. In practice, the LLM post-training typically is implemented in a much smaller time horizon, e.g., three iterations. We therefore use more aggressive stepsizes to obtain substantial improvements within this short horizon.
We comment that, even in the classic tabular experiment settings, it is common that the gradient-based algorithms are implemented with a much more aggressive stepsize instead of the theoretical conservative stepsize. In our paper, the polynomial preference-query guarantee is itself a significant theoretical contribution: to the best of our knowledge, it is the first such guarantee for online iterative NLHF. We regard extending this guarantee to larger stepsizes as an interesting open problem.
DENPO replaces the explorer step with an unanalyzed surrogate, runs for only , and compares only with INPO and XPO.
Thank you for these helpful comments.
We added theoretical support for the explorer surrogate in Appendix C.1.1 of the revised paper. Under a coverage condition, we connect population DPO improvement to a lower bound on the theoretical exploration objective. This provides a mathematical justification for the explorer surrogate used in DENPO. We think this justification is an interesting and meaningful addition to the paper, since most practical algorithms only employ heuristic surrogates without any theoretical justification.
We agree that the three-iteration horizon is a small number compared to the usual gradient-based algorithm. Even so, it is a setup that is commonly used in the LLM post-training, partly due to its high cost, and we adapt that setup for the comparisons between our methods and previous baselines.
As per our response to Reviewer CF4g, we are implementing additional experiments to compare DENPO with more baselines. We will follow up with additional results once we collect a full set of results.
Thank you again for your detailed review. We sincerely appreciate your comments and suggestions.
We would like to follow up on our rebuttal. We have substantially revised the paper to address the valuable points you raised. We have invested significant effort in this revision, and we would greatly appreciate it if you could take a look at our responses and let us know whether they have adequately addressed your concerns.
Author Rebuttals
We thank the reviewer for their thoughtful comments and constructive suggestions. We appreciate them. We respond to each point to address the questions and concerns raised.
Thank you for these helpful comments and questions.
We agree that to choose a best iterate we have to store all checkpoints and evaluate them with various benchmarks in practice, which is not ideal. To avoid that, we revised the paper to adapt to another approximate realizability assumption: for each mirror descent target, there exists a policy in the policy class that is close enough to it. This approximation condition allows a finite policy class and yields a uniform-mixture regret bound. We presented this new assumption and the revised regret bound in Section 3 of the revised paper.
We also note that, with an exact realizability condition and a potentially infinite policy class, we can still derive a similar regret bound by using a standard covering-number argument. By doing so, we are able to make the policy class and realizability condition independent of the time horizon. We included these guarantees in Section D.2.
Thank you for pointing out this point. We appreciate it.
We agree that the computational advantage of the explorer should be explained more clearly. The distinction lies in the optimization structure. The max-max problem can still be seen as a maximization problem over a joint policy class, in which both policy variables share a common scalar objective function. In contrast, the max-min problem is a saddle-point problem, where the two decision variables are optimizing the opposite objectives.
This distinction particularly matters in the gradient-based training. It is known that opposing gradient updates in games can exhibit rotational or cycling dynamics even in bilinear zero-sum examples [Balduzzi et al. (2018)]. In contrast, gradient descent does not incur such issues. More generally, computing a Nash equilibrium in a general finite game is PPAD-complete [Daskalakis et al. (2009)].
We have added a paragraph in the revised paper to explain this distinction.
Thank you for these helpful comments. We appreciate it.
We improved the per-iteration query cost by switching to an alternative empirical loss function in the first oracle, which is the loss function used in IPO and INPO. By doing so, we reduce the query cost from O(t3) to O(t). This change significantly saves on the per-iteration preference query and sampling cost: in round t, we only draw 2t+2 new responses and query 2t preference labels.
We also updated Algorithm 1 to make it be consistent with the proof. The algorithm now explicitly draws each new pair's prompt x∼ρ and both responses conditionally on that shared prompt to construct the dataset D2t. The dataset D1t uses fresh independent prompts from ρ. To compute the first loss function, we sample ct,s∼πt−1(⋅∣xs) at each stored pair's prompt. Thus, the sampling rule agrees with the prompt conditioning used in the proof.