mlsanityData to 14 Oct 2026

Unregularized Linear Convergence in Zero-Sum Game from Preference Feedback

arXiv 2512.24818 ↗First posted 31 Dec 2025cs.LGcited by 0

On the map: LLM alignment / RLHF / preference optimisation → Reward modeling and RLHF

Abstract (arXiv)

Aligning large language models (LLMs) with human preferences has proven effective for enhancing model capabilities, yet standard preference modeling using the Bradley-Terry model assumes transitivity, overlooking the inherent complexity of human population preferences. Nash learning from human feedback (NLHF) addresses this by framing non-transitive preferences as a two-player zero-sum game, where alignment reduces to finding the Nash equilibrium (NE). However, existing algorithms typically rely on regularization, incurring unavoidable bias when computing the duality gap in the original game. In this work, we provide the first convergence guarantee for Optimistic Multiplicative Weights Update (mathttOMWU) in NLHF, showing that it achieves last-iterate linear convergence after a burn-in phase whenever an NE with full support exists, with an instance-dependent linear convergence rate to the original NE, measured by duality gaps. Compared to prior results in Wei et al. (2020), we do not require the assumption of NE uniqueness. Our analysis identifies a novel marginal convergence behavior, where the probability of rarely played actions grows exponentially from exponentially small values, enabling exponentially better dependence on instance-dependent constants than prior results. Experiments corroborate the theoretical strengths of mathttOMWU in both tabular and neural policy classes, demonstrating its potential for LLM applications.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in Reward modeling and RLHF, one of 10 directions in LLM alignment / RLHF / preference optimisation. Builds on 18 of its 26 references that are in the map. First posted on arXiv 31 Dec 2025.

Builds on

18 of 26 references.

Closest ancestors · 11

Same direction, newest first

  1. 2025Extragradient Preference Optimization (EGPO): Beyond Last-Iterate Convergence for Nash Learning from Human Feedback11 Mar
  2. 2025Improving LLM General Preference Alignment via Optimistic Online Mirror Descent24 Feb
  3. 2024Magnetic Preference Optimization: Achieving Last-iterate Convergence for Language Model Alignment22 Oct
  4. 2024Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learning30 Jun
  5. 2024Multi-turn Reinforcement Learning from Preference Human Feedback23 May
  6. 2024Self-Play Preference Optimization for Language Model Alignment1 May
  7. 2024Direct Nash Optimization: Teaching Language Models to Self-Improve with General Preferences4 Apr
  8. 2024Online Iterative Reinforcement Learning from Human Feedback with General Preference Model11 Feb
  9. 2024A Minimaximalist Approach to Reinforcement Learning from Human Feedback8 Jan
  10. 2023Nash Learning from Human Feedback1 Dec
  11. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Model29 May

Other references · 7

  1. 2023A General Theoretical Paradigm to Understand Learning from Human Preferencescited by 912
  2. 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 98
  3. 2024Human Alignment of Large Language Models through Online Preference Optimisationcited by 91
  4. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  5. 2021Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Gamescited by 43
  6. 2021Last-iterate Convergence in Extensive-Form Gamescited by 28
  7. 2024Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithmscited by 14

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Efficient Exploration for Iterative Nash Preference Optimization
  2. 2024COMAL: A Convergent Meta-Algorithm for Aligning LLMs with General Preferences
  3. 2025Multiplayer Nash Preference Optimization
  4. 2025Fundamental Limits of Game-Theoretic LLM Alignment: Smith Consistency and Preference Matching
  5. 2025Proximal Point Nash Learning from Human Feedback
  6. 2025Stackelberg Learning from Human Feedback: Preference Optimization as a Sequential Game
  7. 2025Statistical Impossibility and Possibility of Aligning LLMs with Human Preferences: From Condorcet Paradox to Nash Equilibrium
  8. 2026Transitivity Meets Cyclicity: Explicit Preference Decomposition for Dynamic Large Language Model Alignment