title: Accelerating Nash Learning from Human Feedback via Mirror Prox
summary: 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 (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+2beta)^{-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.
paper_authors._id: 683588a1650d51732cab05de
paper_authors.name: Daniil Tiapkin
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2025-05-27T10:03:29.430Z
paper_authors._id: 6262880c5eb4fa93219f0064
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/6262880c5eb4fa93219f0064/6yyBvRK4Oh7OhjaaweaVN.jpeg
paper_authors.fullname: Daniil Tiapkin
paper_authors.type: user
paper_authors.user: dtiapkin
paper_authors._id: 683588a1650d51732cab05df
paper_authors.name: Daniele Calandriello
paper_authors._id: 683588a1650d51732cab05e0
paper_authors.name: Denis Belomestny
paper_authors._id: 683588a1650d51732cab05e1
paper_authors.name: Eric Moulines
paper_authors._id: 683588a1650d51732cab05e2
paper_authors.name: Alexey Naumov
paper_authors._id: 683588a1650d51732cab05e3
paper_authors.name: Kashif Rasul
paper_authors.status: extracted_pending
paper_authors.statusLastChangedAt: 2025-05-27T09:40:50.326Z
paper_authors._id: 629f3b18ee05727ce328ccbe
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/1669189789447-629f3b18ee05727ce328ccbe.jpeg
paper_authors.fullname: Kashif Rasul
paper_authors.type: user
paper_authors.user: kashif
paper_authors._id: 683588a1650d51732cab05e4
paper_authors.name: Michal Valko
paper_authors.status: extracted_confirmed
paper_authors.statusLastChangedAt: 2025-05-27T10:00:09.731Z
paper_authors._id: 651e97156d92456bdf5ace6b
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/651e97156d92456bdf5ace6b/KKfdZGPAcWPdqycp9SulH.jpeg
paper_authors.fullname: Michal Valko
paper_authors.type: user
paper_authors.user: misovalko
paper_authors._id: 683588a1650d51732cab05e5
paper_authors.name: Pierre Menard
paper_title: Accelerating Nash Learning from Human Feedback via Mirror Prox
paper_summary: 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 (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+2beta)^{-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.
paper_ai_summary: Nash Mirror Prox is an online algorithm for Nash Learning from Human Feedback that achieves linear convergence to the Nash equilibrium and is applicable for fine-tuning language models.
paper_ai_keywords: Nash Learning from Human Feedback Nash Mirror Prox Mirror Prox KL-divergence Nash equilibrium exploitability gap span semi-norm log-probabilities stochastic policy gradients fine-tuning large language models