Accelerating Nash Learning from Human Feedback via Mirror Prox

• URL: http://arxiv.org/abs/2505.19731v1
• Date: Mon, 26 May 2025 09:17:32 GMT
• Title: Accelerating Nash Learning from Human Feedback via Mirror Prox
• Authors: Daniil Tiapkin, Daniele Calandriello, Denis Belomestny, Eric Moulines, Alexey Naumov, Kashif Rasul, Michal Valko, Pierre Menard,
• Abstract summary: We introduce Nash Mirror Prox ($mathtNash-MP$), an online NLHF algorithm that leverages the Mirror Prox optimization scheme to achieve fast and stable convergence to the Nash equilibrium.<n>Our theoretical analysis establishes that Nash-MP exhibits last-iterate linear convergence towards the $beta$-regularized Nash equilibrium.<n>We show that Nash-MP exhibits last-iterate linear convergence for the exploitability gap and uniformly for the span semi-norm of log-probabilities.
• Score: 36.04055906691423
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Traditional Reinforcement Learning from Human Feedback (RLHF) often relies on reward models, frequently assuming preference structures like the Bradley-Terry model, which may not accurately capture the complexities of real human preferences (e.g., intransitivity). Nash Learning from Human Feedback (NLHF) offers a more direct alternative by framing the problem as finding a Nash equilibrium of a game defined by these preferences. In this work, we introduce Nash Mirror Prox ($\mathtt{Nash-MP}$), an online NLHF algorithm that leverages the Mirror Prox optimization scheme to achieve fast and stable convergence to the Nash equilibrium. Our theoretical analysis establishes that Nash-MP exhibits last-iterate linear convergence towards the $\beta$-regularized Nash equilibrium. Specifically, we prove that the KL-divergence to the optimal policy decreases at a rate of order $(1+2\beta)^{-N/2}$, where $N$ is a number of preference queries. We further demonstrate last-iterate linear convergence for the exploitability gap and uniformly for the span semi-norm of log-probabilities, with all these rates being independent of the size of the action space. Furthermore, we propose and analyze an approximate version of Nash-MP where proximal steps are estimated using stochastic policy gradients, making the algorithm closer to applications. Finally, we detail a practical implementation strategy for fine-tuning large language models and present experiments that demonstrate its competitive performance and compatibility with existing methods.

Related papers

• Multi-Step Consistency Models: Fast Generation with Theoretical Guarantees [15.366598179769918]
  We provide a theoretical analysis of consistency models capable of mapping inputs at a given time to arbitrary points along the reverse trajectory.<n>We show that one can achieve a KL divergence of order $ O(varepsilon2) $ using only $ Oleft(logleft(fracdvarepsilonright) $ iterations with a constant step size.<n>We conclude that accurate learning is feasible using small discretization steps, both in smooth and non-smooth settings.
  arXiv  Detail & Related papers  (2025-05-02T06:50:46Z)
• Improving LLM General Preference Alignment via Optimistic Online Mirror Descent [57.622821649679786]
  Reinforcement learning from human feedback (RLHF) has demonstrated remarkable effectiveness in aligning large language models (LLMs) with human preferences.<n>In this paper, we drop the Bradley-Terry (BT) model assumption and study LLM alignment under general preferences, formulated as a two-player game.<n>We show that our approach achieves an $O(T-1)$ bound on the duality gap, improving upon the previous $O(T-1/2)$ result.
  arXiv  Detail & Related papers  (2025-02-24T05:24:52Z)
• Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learning [55.65738319966385]
  We propose a novel online algorithm, iterative Nash policy optimization (INPO)<n>Unlike previous methods, INPO bypasses the need for estimating the expected win rate for individual responses.<n>With an LLaMA-3-8B-based SFT model, INPO achieves a 42.6% length-controlled win rate on AlpacaEval 2.0 and a 37.8% win rate on Arena-Hard.
  arXiv  Detail & Related papers  (2024-06-30T08:00:34Z)
• Analysis of Kernel Mirror Prox for Measure Optimization [4.6080589718744305]
  We study in a unified framework a class of functional saddle-point optimization problems, which we term the Mixed Functional Nash Equilibrium (MFNE) We model the saddle-point optimization dynamics as an interacting Fisher-Rao-RKHS gradient flow. We provide a unified convergence analysis of KMP in an infinite-dimensional setting for this class of MFNE problems.
  arXiv  Detail & Related papers  (2024-02-29T21:55:17Z)
• Online Iterative Reinforcement Learning from Human Feedback with General Preference Model [20.81421550138371]
  We investigate Reinforcement Learning from Human Feedback (RLHF) in the context of a general preference oracle. We consider a standard mathematical formulation, the reverse-KL regularized minimax game between two LLMs for RLHF under general preference oracle. We show that this framework is strictly more general than the reward-based one, and propose sample-efficient algorithms for both the offline learning from a pre-collected preference dataset and online learning.
  arXiv  Detail & Related papers  (2024-02-11T21:44:21Z)
• Nash Learning from Human Feedback [86.09617990412941]
  We introduce an alternative pipeline for the fine-tuning of large language models using pairwise human feedback. We term this approach Nash learning from human feedback (NLHF) We present a novel algorithmic solution, Nash-MD, founded on the principles of mirror descent.
  arXiv  Detail & Related papers  (2023-12-01T19:26:23Z)
• Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
  Online gradient descent (OGD) is well known to be doubly optimal under strong convexity or monotonicity assumptions. In this paper, we design a fully adaptive OGD algorithm, textsfAdaOGD, that does not require a priori knowledge of these parameters.
  arXiv  Detail & Related papers  (2023-10-21T18:38:13Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  We show that model-based MARL achieves a sample complexity of $tilde O(|S||B|(gamma)-3epsilon-2)$ for finding the Nash equilibrium (NE) value up to some $epsilon$ error. We also show that such a sample bound is minimax-optimal (up to logarithmic factors) if the algorithm is reward-agnostic, where the algorithm queries state transition samples without reward knowledge.
  arXiv  Detail & Related papers  (2020-07-15T03:25:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.