Extragradient Preference Optimization (EGPO): Beyond Last-Iterate Convergence for Nash Learning from Human Feedback

Reasons To Reject:

[R1] Limited Scalability:Experiments use small models (gemma-2-2b-it) and a single dataset (PKU-SafeRLHF). No evidence is provided for scalability to state-of-the-art open source LLMs (e.g., LLaMA series, Qwen series) or diverse preference datasets.

[Reply] Thank you for pointing this out. Due to resource constraints, we were limited to using a 2B model with LoRA. However, our algorithm design and implementation are model/data-agnostic (only requiring generating responses, calculating log probabilities, and gradient backup and restoration), and our theoretical guarantees outperform those of all baselines. We believe that given the same base model and dataset, EGPO will outperform the baselines mentioned in our work.

[R2] Incomplete Baseline Comparison: In the experiment the Nash-MD-PG’s poor performance is a little weird, I think here we need more details to explain why the method is poor in this setting, and why it only converges when $\beta$ is large?

[Reply] We clarify this here. For benchmarks, we use the standard setting of $\beta=0.1$ and $\eta=5\times 10^{-7}$ from previous RLHF works. The Nash-MD-PG trainer is directly taken from the TRL library (trl.NashMDTrainer), so its slow convergence and poor behavior simply verify its theoretical guarantee of a constant gap of $\tilde{O} (\eta/\beta)$ (see Table 1). When running numerical simulations, the $\eta$ values reported in the titles of Figures 2 to 4 are those passed into the optimizer. If we denote $\eta_\textup{theory}$ as the $\eta$ in Theorem 1, they are actually $\frac{\eta_\textup{theory} \beta |\mathcal{Y}|}{4}$ according to Equations (4) and (5). Therefore, $\eta_\textup{theory}/\beta \propto \eta / \beta^2$. Hence, for $\beta = 0.001$ and $0.01$, Nash-MD-PG does not converge as well as the other algorithms.

[R3] Practical Relevance: No discussion of computational costs or sample efficiency compared to other RLHF methods. In particular the method is designed for non-transitive case, but I am also interesting for the transitive case the comparison of EGPO with PPO or GRPO. Also is it possible to provide the code for the LLM training?

[Reply] For computational costs, please refer to our reply to all reviewers.

We also clarify that beyond the capability to handle non-transitive preferences, NLHF differs from standard RLHF as a game-theoretic formulation with distinct objectives. NLHF algorithms optimize the worst-case win-rate against any policy, while standard RLHF algorithms optimize expected rewards. We will discuss the motivational differences between NLHF and RLHF more clearly in the paper.

When comparing algorithms by win-rates, EGPO policies achieve at least $50\\%$ (typically higher) win probability against PPO/DPO policies. However, when comparing by rewards, PPO/DPO policies are more likely to outperform EGPO policies.

[R4] Incremental Contribution: EGPO builds heavily on Cen et al. (2021)’s extragradient methods and Munos et al. (2023)’s NLHF framework. The online IPO formulation, while useful, is a technical extension rather than a conceptual breakthrough.

[Reply] Generalizing theoretical algorithms to LLM applications is non-trivial. While [1] initiated the study of NLHF, the theoretical algorithm Nash-MD is essentially a variant of mirror descent. MPO [2] is also an LLM implementation of a previous algorithm, MMD [3]. The value of NLHF studies lies in identifying the theory-practice gap and proposing better approximations and sampling schemes to reduce bias when theoretical algorithms are applied to LLMs. In this regard, the online IPO formulation significantly improves upon previous nested optimization paradigms by reducing both algorithm complexity and optimization bias. We therefore believe this formulation is significant to NLHF research, as it can be easily applied to previous algorithms.

Questions To Authors:

[Q1] Could you please provide more experiments on diverse datasets and models? In particular for recent open-source models. Also I think it's better to show the analysis of the time cost during training.

[Reply] Due to resource constraints, we may not provide results on other datasets and models before the stage 1 rebuttal deadline. We are currently training Qwen/Qwen2.5-1.5B-Instruct using a subset of OpenRLHF/prompt-collection-v0.1 (the same dataset as Appendix C.3 of [2]). As suggested by reviewer DDAh, we also aim to complete experiments under transitive preference settings before the camera-ready deadline if our work is accepted. Time cost analysis is provided in the reply to all reviewers.

[1] Nash learning from human feedback

[2] Magnetic preference optimization: Achieving last-iterate convergence for language model alignment

[3] A unified approach to reinforcement learning, quantal response equilibria, and two-player zero-sum games

Reasons To Reject:

[R1] In the online RLHF setting, this paper presented many experimental results in the appendix, while the main body lacks a good reasoning and summary of the performance impact. There are some remarks in Line 292 and beyond, however, it could be more interesting if the revealed good cases are explained with a why, and the limitation of the proposed method are also explicitly presented to readers.

[Reply] Thanks for the suggestion! We plan to revise Section 5.2 as follows: shorten the experiment setup descriptions by mentioning only the model and dataset, with all other details moved to Appendix E.3.1; add more discussion on approximating uniform sampling, including hyperparameter search for (temperature, top_k); in the remarks, discuss EGPO's efficiency (though it requires two iterations per update step, it can achieve even better results using half the number of iterations compared to baselines) and relate this to theoretical findings and numerical simulations.

Questions To Authors:

[Q1] Line 308 and beyond elaborated on some limitations of this work. They are future works that make things more efficient, but not 'limitations'. The limitations would be in the problem setting and data resources in Nash Learning from Human Feedback. Taking a step back, does this work have a better coverage or push the boundary of the original proposal of NLHF in terms of problem setting and data resources?

[Reply] Regarding the problem setting, directly learning a preference model may result in preference hacking, as any misspecifications or biases in the preference model may impact the policy model. In our work, we avoid this problem by assuming the preference model is the ground truth, but in practice, we need to query humans directly for the ground truth during evaluation. This work aims to deliver an algorithm with better theoretical guarantees and implementation accuracy, so we do not change the boundary of NLHF problems.

Reasons To Reject:

[R1] EGPO needs two forward/backward passes per update and relies on approximate uniform sampling of candidate responses, which can double the compute cost and introduce bias.

[Reply] These points are important. With two forward/backward passes per update, Tables 2 and 7 show that EGPO running for 5 epochs outperforms all other algorithms running for 10 epochs, suggesting that EGPO's iteration complexity can be reduced to half that of other algorithms. Regarding the approximation of uniform sampling, we acknowledge that it introduces bias. In practice, we searched over configurations of (temperature, top_k) and selected the optimal configuration of $(2, 10)$ for all algorithms.

[R2] The paper offers little analysis of $\beta/\eta$ sensitivity or wall-clock efficiency relative to single-step methods.

[Reply] We experimented with different values of $\beta$ and $\eta$ for the numerical simulations and found that when $\beta$ is small, the optimal $\eta$ is also small. In our numerical simulations, the $\eta$ values reported in the titles of Figures 2 to 4 are those passed into the optimizer. If we denote $\eta_\textup{theory}$ as the $\eta$ in Theorem 1, these values are actually $\frac{\eta_\textup{theory} \beta |\mathcal{Y}|}{4}$ according to Equations (4) and (5). Therefore, the sensitivity of $\eta$ to $\beta$ is expected. Due to computational resource constraints, we have not experimented with different $\beta$ and $\eta$ values for LLM benchmarks.

Regarding wall-clock efficiency, please refer to our reply to all reviewers.

Questions To Authors:

[Q1] Could the authors provide the sensitive analysis of $\beta/\eta$?

[Reply] Please see the response to [R2].

Questions To Authors:

[Q1] Could you elaborate on the computational overhead of EGPO compared to the baselines, particularly in the LLM alignment experiments (e.g., wall-clock time per epoch, memory usage)? The online IPO formulation relies on specific choices for $\rho$ and $\mu$ (e.g., Unif * Unif in Equation 4 and 5). Have you explored other choices for these distributions, and how might they affect performance or the equivalence to the theoretical EGPO updates?

[Reply] Regarding computational overhead, please refer to the reply to all reviewers.

We have not explored other configurations of $\rho$ and $\mu$ in the theoretical analysis, as the current choice is sufficient for deriving the equivalence. We hypothesize that $\rho$ cannot be changed, as $\Sigma(\rho)$ (see line 669) would be not identical to $I + C \cdot \mathbb{1}$ otherwise. In practice, as mentioned in previous replies, we tested several configurations of (temperature, top_k) to approximate $\rho$, and the combination of $(2, 10)$ performed best.

[Q2] Regarding the approximation for uniform sampling from the response space: How sensitive are the results to the specific top-k and temperature values used? Could this approximation introduce any systematic biases that might affect certain types of prompts or responses differently?

[Reply] We searched over a small space of (temperature, top_k), and the win-rates of Online IPO 1 (OMD) against $\pi_\textup{ref}$ varied between $65\%$ and $72\%$, with $72\%$ corresponding to $(2, 10)$. While the choice of parameters shows some sensitivity, it is not particularly high. We observed no extremely abnormal responses from these configurations. However, when temperature $=10$ and top_k $=20$, responses contained highly irrelevant sentences.

[Q3] In Table 1, EGPO is shown to converge to the regularized QRE at a rate of $\tilde{O} ((1-\eta\beta)^T)$. How does the choice of the regularization coefficient β practically impact the convergence speed and the quality of the final policy in the LLM experiments? The paper mentions $\beta=0.001$ is the most challenging case in simulations and $\beta=0.1$ is used in NLHF training.

[Reply] As $\beta$ increases, the convergence rate accelerates since $1 - \eta \beta$ decreases. However, this also means the final policy becomes more similar to the reference policy, achieving less human preference alignment. From the duality gap perspective, $(\textup{DualGap} - \textup{DualGap}_\beta) \propto \beta$; larger $\beta$ values make the QRE deviate further from the actual NE. In the extreme case where $\beta \to 0$, the regularized game closely approximates the original game (which may have multiple NEs), making it harder to solve. The choice of $\beta=0.1$ or larger is common in the RLHF/NLHF field.

[Q4] The paper notes that MPO, while having lower win-rates against the reference policy than Nash-MD, consistently beat Nash-MD in direct pairwise comparisons, indicating non-transitivity in the ground truth preference P. Does EGPO show similar robustness or advantages in highly non-transitive scenarios compared to methods that might implicitly favor transitivity?

[Reply] We have not observed this phenomenon in our Safe-RLHF experiments, as EGPO consistently achieves the highest win-rates against both $\pi_\textup{ref}$ and other policies. To verify this finding, we could replace the preference model with a reward model (following standard RLHF) and rerun the experiments. However, due to resource constraints, we will complete this analysis before the camera-ready deadline if our work is accepted.

Reasons To Reject:

[R1] While the online IPO formulation simplifies things, the overall practical implementation complexity across different LLM architectures and datasets might still be a concern. The paper uses gemma-2-2b-it; performance on significantly larger or different types of models would be interesting.

[Reply] The implementation is model-agnostic. Our code inherits the OnlineDPOTrainer class from the TRL library and only requires (1) generating responses, (2) calculating log probabilities, and (3) gradient backup and restoration. Since all these operations are high-level, no architecture- or dataset-specific handling is needed.

[R2] The paper acknowledges that directly sampling uniformly from the response space is impractical for auto-regressive models and uses an approximation by generating responses with top-k and temperature settings. The impact of this approximation on the theoretical guarantees and empirical performance could be further explored or discussed.

[Reply] This is worth investigating. A similar situation of sampling from a uniform distribution was encountered in previous work [2]. In that paper, the authors treat the uniform distribution as a posterior on the current policy $\pi_\theta$ and sample directly from $\pi_\theta$. However, neither our work nor theirs can provide theoretical justification for sampling from $\pi_\theta$.

We tested all combinations of temperature $\in \\{1,2,5\\}$ and top_k $\in \\{5, 10\\}$. The combination of $(2, 10)$ performed best in terms of win-rates against $\pi_\textup{ref}$.

[R3] The performance of EGPO, like many RL algorithms, might be sensitive to hyperparameter choices (e.g., $\beta$, $\eta$). While the paper presents results for specific settings, a more extensive ablation study on hyperparameter sensitivity could strengthen the practical claims.

[Reply] We agree that thorough hyperparameter investigations are important. For fair comparison with baselines, we adopt standard benchmark values of $\beta=0.1$ and $\eta=5\times 10^{-7}$. In numerical simulations (Appendix E.2.2, Figures 2 to 4), we use different $\beta$ settings, with $\eta$ values determined through hyperparameter search for each $\beta$.

[R4] The experiments use a fine-tuned language model as the "ground truth preference". While a common practice due to resource constraints, the characteristics of this surrogate (e.g., its own potential biases or non-transitivity) and how they might interact with EGPO's evaluation could be discussed. The paper does note this model can be replaced with human annotators or other LLMs.

[Reply] We clarify this point here. As stated in Section 4.1, our study does not involve "preference modeling" since our focus is on the optimization side -- specifically, how quickly we can achieve a specific NE. Consequently, we simply assume the preference model is accurate. In Section 8.1 of [2], the authors demonstrate that increasing preference model capacity improves accuracy, though the gain from 3B to 11B is minimal. We expect similar findings: if we incorporate preference modeling using a larger model to learn preferences, bias will decrease, but gains will be diminishing.

[R5] The paper motivates NLHF by the non-transitive nature of populational human preferences. It would be beneficial to discuss the extent or types of non-transitivity EGPO is particularly well-suited to handle, perhaps with more varied non-transitive scenarios in the numerical simulations. The paper mentions the ground truth preference $P$ demonstrates non-transitive behavior in one instance

[Reply] This question is central to the motivation of NLHF works. EGPO assumes no special structure on $\mathcal{P}$, enabling it to handle any extent or type of non-transitivity with theoretical guarantees. For detailed motivation on non-transitive preferences, see Section 3.2 of [2].

[1] The Crucial Role of Samplers in Online Direct Preference Optimization

[2] Nash Learning from Human Feedback