Accelerating Nash Learning from Human Feedback via Mirror Prox
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.
683588a1650d51732cab05de
Daniil Tiapkin
claimed_verified
2025-05-27T10:03:29.430Z
6262880c5eb4fa93219f0064
https://cdn-avatars.huggingface.co/v1/production/uploads/6262880c5eb4fa93219f0064/6yyBvRK4Oh7OhjaaweaVN.jpeg
Daniil Tiapkin
user
dtiapkin
683588a1650d51732cab05df
Daniele Calandriello
683588a1650d51732cab05e0
Denis Belomestny
683588a1650d51732cab05e1
Eric Moulines
683588a1650d51732cab05e2
Alexey Naumov
683588a1650d51732cab05e3
Kashif Rasul
extracted_pending
2025-05-27T09:40:50.326Z
629f3b18ee05727ce328ccbe
https://cdn-avatars.huggingface.co/v1/production/uploads/1669189789447-629f3b18ee05727ce328ccbe.jpeg
Kashif Rasul
user
kashif
683588a1650d51732cab05e4
Michal Valko
extracted_confirmed
2025-05-27T10:00:09.731Z
651e97156d92456bdf5ace6b
https://cdn-avatars.huggingface.co/v1/production/uploads/651e97156d92456bdf5ace6b/KKfdZGPAcWPdqycp9SulH.jpeg
Michal Valko
user
misovalko
683588a1650d51732cab05e5
Pierre Menard
Accelerating Nash Learning from Human Feedback via Mirror Prox
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.
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.
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