Unregularized Linear Convergence in Zero-Sum Game from Preference Feedback
This addresses the challenge of bias in preference modeling for LLM alignment, offering a more robust solution for AI safety and performance, though it is incremental as it builds on existing game-theoretic frameworks.
The paper tackles the problem of aligning large language models with non-transitive human preferences by analyzing the Optimistic Multiplicative Weights Update algorithm in Nash learning from human feedback, showing it achieves last-iterate linear convergence to the Nash equilibrium without requiring uniqueness assumptions, with experiments validating its effectiveness in tabular and neural settings.
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 ($\mathtt{OMWU}$) 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 $\mathtt{OMWU}$ in both tabular and neural policy classes, demonstrating its potential for LLM applications.