Magnetic Preference Optimization: Achieving Last-iterate Convergence for Language Model Alignment

W1&Q1: The convergence rate to the original NE is not studied. What will the convergence result be if the approximation error is taken into consideration?

Thank you for your insightful suggestion to improve our paper. We have provided the convergence results when only the approximate NE are learned in Theorem F.4 of the Appendix F. Specifically, let $\pi_r^{\tau}$ denote the approximation of NE of the regularized game $\pi_{r}^{*,n}$, with the approximation error measured using the duality gap. Theorem F.4 demonstrates that duality gap converges at a rate of $O(1/\sqrt{K})$, where $1 \leq n \leq K$. We hope this reults adequately addresses your concern.

Q2: Can Nash-MD be adapted to the approach in Section 3.2 and achieve a last-iterate convergence to the original NE?

Thank you for your question. Yes, Nash-MD can indeed be adapted to achieve last-iterate convergence to the original NE following our approach in Section 3.2. The core insight of our theoretical analysis is that any algorithm capable of achieving last-iterate convergence can be used to solve the regularized game and the sequence of NE of the regularized games will eventually converge to the NE of the original game, regardless of which algorithm is used as long as it achieves last-iterate convergence. Since Nash-MD guarantees last-iterate convergence to the NE of the regularized game, it can be naturally incorporated into our framework.

Thank you so much for your appreciation and constructive feedback. Sincerely, we would like to address your concerns as follows.

W1.1: The connection between theoretical contribution and the empirical implementation is not clear.

Thank you for your question. We apologize for any confusion caused by a typo in our original manuscript. Specifically, in the first term on the right-hand side of eq (6), $y_1$is actually sampled from the current policy. We have corrected this typo in the revised version for clarity. To elaborate, the first term of the MMD objective in eq (4) corresponds to the first-order approximation of the objective function ((for more details, please refer to Chapter 6 of [1])). Our empirical implementation follows the common approach in prior work (please see eq (4) of [2] and Appendix L of [3]) and is effective in our setting (Figure 1). We hope this clarification helps establish a clearer connection between the theoretical derivations and the practical algorithms used in our work. We sincerely apologize for any misunderstanding caused by the original typo and appreciate your understanding.

W1.2: Could the authors provide more insight into selecting between MDSPO and MDSPO-RT?

Thank you for raising this question. To simplify terminology, we have renamed our algorithm to MPO. The key distinction between MPO and MPO-RT lies in how they handle KL regularization. Specifically, MPO employs a soft constraint on KL divergence through a KL loss, while MPO-RT enforces a hard constraint by directly modifying the reward function, aligning closely with standard RLHF methods.

Empirically, the choice between MPO and MPO-RT depends on the quality of the preference model and the reference model. If the preference model is less reliable but the reference model is relatively robust, MPO-RT’s stricter KL constraints can help mitigate the negative effects of the imperfect preference model by keeping the policy closer to the reference. Conversely, if a high-quality preference model is available, MPO typically performs better as its relaxed KL constraints allow the model greater flexibility to explore and optimize within the high-preference regions.

We hope this explanation provides clarity on how to select between the two variants depending on specific application needs and model conditions.

W1.3: Empirical observation about the average-iterate convergence phenomenon and comparisons with SPO.

Thank you for your suggestion. Regarding the empirical observation about the phenomenon and the motivation, please refer to our response to W1 from Reviewer wd8o, where we provide detailed explanations. As for SPO, it is not well-suited for RLHF scenarios due to the absence of KL regularization with respect to the reference policy. This lack of regularization causes the policy to deviate rapidly from the reference, ultimately leading to training instability and failure. As a result, SPO is more of a theoretical algorithm rather than a practical solution. Notably, the original SPO paper [4] does not include RLHF experiments, further highlighting its limitations in this context. To demonstrate the practical effectiveness of our proposed algorithm, we have incorporated PPO and Iterative DPO as baselines for comparison. These results are detailed in Appendix D.1. For further discussion on this point, please also refer to our response to W2 from Reviewer wd8o. We hope these additions could address your concern.

W2.1&2.2: Citation and proofs of theorems.

Thank you for pointing out these issues. We have carefully revised our manuscript to ensure proper citation. For the proofs, we have conducted a thorough review and made revisions to improve their clarity and correctness. In particular, we have corrected notational inconsistencies and typos, provided more detailed explanations for critical steps, and enhanced the logical flow of the arguments to ensure they are easier for readers to understand and follow. Furthermore, we have extended the theoretical contributions by including new results on the convergence rate of our algorithm in Theorem F.2 (please see the reponses to reviewer wd8o), which offers a deeper understanding of its performance and aligns well with the overall theoretical framework. Thank you for your valuable feedback, which has been instrumental in improving the quality of our work.

Thank you very much for your appreciation and thoughtful feedback! We are delighted to further address your concerns.

For the KL divergence term in Eq.(6), as proved in [1][2], the Nash equilibrium (NE) strategies for both players are unique and identical in our context, i.e., $\pi_1^* = \pi_2^* = \pi^*$. This property allows us to use $\pi^*$ to denote the NE strategies for both players. Thus, for simplicity, we can write the KL divergence terms in Eq. (6) as $D_{KL}(\pi_1 || \pi_r^{*,n-1})$ . And we have included the proof of this property in Lemma E.1 for completeness.

Regarding your concern about Lemma 3.3, we confirm that N = 2, as our context involves only two players. To ensure rigor in the proof, we explicitly wrote the expressions for each player in our previous revisions.

In response to the your valuable suggestions, we conducted a thorough review to further improve the clarity of our work and identified a few notational inconsistencies that might cause confusion for readers. Specifically:

1. In the preliminaries section, we denoted $\pi^* = (\pi_1^*, \pi_2^*)$ as the NE strategy profile, whereas later, $\pi^*$ was used to denote the NE strategy for a single player.

2. We used $N$ to denote the maximum number of players but later used $n$ to refer to the $n$-th regularized game.

Recognizing that these inconsistencies might mislead the readers, we have made further revisions to the manuscript to refine the notations and proofs. We now use $\mathcal{I}=${1,2} to denote the set of players, $N$ to denote the number of regularized games and consistently use $\pi^*$ to represent the NE strategy for a single player to improve clarity. For your convenience, we have highlighted these changes in blue in the preliminaries section.

We sincerely hope these improvements address your concerns and enhance the overall clarity and readability of our work. Thank you again for your appreciation and valuable feedback. Please let us know if you have any further questions or concerns !

References

[1] Munos, R., Valko, M., Calandriello, D., Azar, M. G., Rowland, M., Guo, Z. D., ... & Piot, B. (2023). Nash learning from human feedback. arXiv preprint arXiv:2312.00886.

[2] Xiong, W., Dong, H., Ye, C., Wang, Z., Zhong, H., Ji, H., ... & Zhang, T. (2024). Iterative preference learning from human feedback: Bridging theory and practice for rlhf under kl-constraint. In Forty-first International Conference on Machine Learning.

Thank you so much for your appreciation and constructive feedback. Sincerely, we would like to address your concerns as follows.

W1:The motivation for introducing the magnetic term in MMD is currently unclear. It would be helpful to discuss the technique challenge to achieve last-iteration convergence when using mirror descent.

Thanks for your valuable feedback. We acknowledge that the motivation for introducing the magnetic term[1] in Magnetic Mirror Descent (MMD) could be clarified further. To be straightforward and concise, the magnetic term in MMD facilitates a more stable convergence of a single strategy towards NE. This signifies that we can achieve preference alignment with just a single model, which is of crucial significance for improving the training stability for large models and mitigating the inference costs. Then we will elaborate on this in detail. We have incorporated additional explanations and figures (Figure 1 and Figure 3) in our manuscript to help readers better understand our approach. For your convenience, we have highlighted these changes in the revised manuscript in blue.

As demonstrated in Figure 3, which shows the trajectories of MD and MMD in solving a simple game (e.g., $f(x, y) = (x-1)(y-1)$), the traditional Mirror Descent (MD) algorithm achieves average-iterate convergence to the NE. However, the last-iterate policy of MD (depicted by the outer blue curve in the figure) oscillates around the NE (marked as the red star at the center). This oscillatory behavior makes it challenging to directly apply MD to practical RLHF scenarios, as the final policy often deviates significantly from the NE. To approximate the NE, additional mechanisms like averaging are required, which increase storage and computational overhead.

To overcome this challenge, the magnetic term in MMD introduces a regularization force that attracts policy updates toward a reference policy while maintaining progress toward the NE. This magnetic attraction stabilizes the updates, reducing oscillations and enabling linear last-iterate convergence to the NE of the regularized game. When the reference policy is a uniform policy, this term reduces to entropy regularization. Our experiments on Kuhn Poker (shown in Figure 1) further demonstrate the limitations of MD-based deep RL methods, such as PPO and SAC (as suggested in SPO [2]). The duality gap in the figure measures the distance to the NE, with lower values indicating closer to the NE. MD-based methods exhibit poor performance in achieving last-iterate convergence to the NE, underscoring the necessity of regularization.

However, as shown in Figure 3, MMD only achieves last-iterate convergence only to the NE of the regularized game, rather than the original game, which is the ultimate alignment objective (this corresponds to the Minmax Winner solution concept in social choice theory [3]). Furthermore, larger regularization strengths (larger $\alpha$) cause the converged policy to deviate further from the original alignment objective. To address this limitation, our results demonstrate that we can update the reference policy periodically to guide the policy to converge to the original NE. We provide detailed theoretical analysis of this approach, which ensures that our method achieves last-iterate convergence to the original NE while balancing stability and computational efficiency.

W2: For the experiment part, this work uses the SFT method as the baseline. It would be better to add additional experiments such as the RLHF with PPO to do a more comprehensive comparsion.

Thank you for your valuable suggestion. To address your concern, we have extended our experimental evaluation by including both PPO and Iterative DPO[2] as additional baselines for comparison. The updated results and discussion can be found in Appendix D.1, where we detail the experimental setups and methodologies to ensure a fair comparison. The results in Figure 7 demonstrate that MPO (we renamed our proposed algorithm as MPO for simplicity) outperforms both PPO and Iterative DPO. We appreciate your suggestion and we are looking forward to your further feedback.

We sincerely appreciate your suggestion and hope that these responses adequately address your concerns.

References

[1] Samuel Sokota, Ryan D’Orazio, J Zico Kolter, Nicolas Loizou, Marc Lanctot, Ioannis Mitliagkas, Noam Brown, and Christian Kroer. A unified approach to reinforcement learning, quantal response equilibria, and two-player zero-sum games.

[2] Swamy, G., Dann, C., Kidambi, R., Wu, Z. S., & Agarwal, A. (2024). A minimaximalist approach to reinforcement learning from human feedback. arXiv preprint arXiv:2401.04056.

[3] Dong, H., Xiong, W., Pang, B., Wang, H., Zhao, H., Zhou, Y., ... & Zhang, T. (2024). Rlhf workflow: From reward modeling to online rlhf. arXiv preprint arXiv:2405.07863.

Thank you so much for your appreciation and constructive feedback. Sincerely, we would like to address your concerns as follows.

W1:Presentation of paper has space of improvement, especially in the technical/mathematical part.

Thank you for your valuable suggestion. We have thoroughly revised the paper to enhance its readability and overall presentation. For your convenience, we have highlighted significant changes in the revised manuscript in blue.

To improve clarity, we refined the expressions throughout the paper and simplified the notation to make it more accessible. Additionally, we incorporated extra figures (Figure 1 and Figure 3 in our revised manuscript) to provide an intuitive understanding of our motivation and key concepts. To complement the main text, we expanded the appendix with additional results and details of our algorithms and experimental setups, ensuring that readers can gain a comprehensive understanding of our methods.

For the technical part, we introduced additional explanations around the key theorems to provide high-level insights, making the results easier for readers to understand. Furthermore, we carefully revised the proofs, adding necessary clarifications at critical steps to improve their transparency and logical flow.

These improvements aim to make the paper more accessible, easier to read, and more engaging. We sincerely hope these revisions address your concerns and enhance your overall experience with the work.

Q1: Do similar results hold without having the uniqueness assumption? In what exact point in the proofs the uniqueness of the Nash equilibrium is needed?

We appreciate your careful reading and thoughtful questions. We want to clarify that our theoretical results do not rely on the uniqueness assumption due to the key condition required in our proof is the mild monotonicity (where the “<=” holds in the following formula) on the gradient of payoff functions, rather than strict monotonicity (where the “<” strictly hold): $\sum_{i=1}^N \langle \nabla_{\pi_{i}} f(\pi_i, \pi_{-i})-\nabla_{\pi_{i}} f(\pi_i^{\prime}, \pi_{-i}^{\prime}), \pi_i - \pi_i^{\prime}\rangle \leq 0, \forall \pi, \pi^{\prime} \in \Pi$. This mild monotonicity condition does not require the uniqueness of Nash equilibrium, which is sufficient for our convergence analysis, while the uniqueness of Nash equilibrium implies strict monotonicity (strict inequality).

This conditional is mainly used to derive Lemma E.3 (line 1346), which is necessary for deriving Lemma 3.3 and Theorem 3.4. And we don't need strict monotonicity here. Therefore, as long as the mild monotonicity condition is satisfied, our theoretical framework naturally extends to cases with multiple Nash equilibriums. It is just that, in our specific scenario, the Nash equilibrium is unique as proved in[1][2], and we have included the proof in Lemma E.1 for completeness.

Thank you again for helping us improve our theoretical clarity. Please let us know if you have any other suggestions.

References

[1] Munos, R., Valko, M., Calandriello, D., Azar, M. G., Rowland, M., Guo, Z. D., ... & Piot, B. (2023). Nash learning from human feedback. arXiv preprint arXiv:2312.00886.

[2] Xiong, W., Dong, H., Ye, C., Wang, Z., Zhong, H., Ji, H., ... & Zhang, T. (2024). Iterative preference learning from human feedback: Bridging theory and practice for rlhf under kl-constraint. In Forty-first International Conference on Machine Learning.