Unregularized Linear Convergence in Zero-Sum Game from Preference Feedback

📄 arXiv: 2512.24818v2 📥 PDF

作者: Shulun Chen, Runlong Zhou, Zihan Zhang, Maryam Fazel, Simon S. Du

分类: cs.LG

发布日期: 2025-12-31 (更新: 2026-01-02)

备注: 28 pages

💡 一句话要点

提出无正则化的OMWU算法，解决偏好反馈零和博弈中的线性收敛问题

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 偏好学习 零和博弈 纳什均衡 乐观乘性权重更新 线性收敛 大型语言模型 无正则化 人类反馈

📋 核心要点

  1. 现有基于Bradley-Terry模型的偏好学习方法假设传递性，无法有效处理人类偏好的复杂性。
  2. 论文提出使用无正则化的乐观乘性权重更新（OMWU）算法，在Nash学习框架下寻找纳什均衡。
  3. 实验结果表明，OMWU算法在表格和神经策略类中表现出理论优势，并具有应用于LLM的潜力。

📝 摘要（中文）

将大型语言模型（LLM）与人类偏好对齐已被证明能有效提升模型能力。然而，使用Bradley-Terry模型的标准偏好建模假设传递性，忽略了人类群体偏好的内在复杂性。Nash学习来自人类反馈（NLHF）通过将非传递偏好构建为双人零和博弈来解决这个问题，其中对齐简化为寻找纳什均衡（NE）。然而，现有算法通常依赖于正则化，在计算原始博弈中的对偶间隙时会产生不可避免的偏差。本文为NLHF中的乐观乘性权重更新（OMWU）提供了首个收敛保证，表明只要存在具有完全支持的NE，它就能在burn-in阶段后实现最后一次迭代的线性收敛，并具有实例相关的线性收敛速度到原始NE，通过对偶间隙衡量。与Wei et al. (2020)中的先前结果相比，我们不需要NE唯一性的假设。我们的分析确定了一种新的边际收敛行为，其中很少采取的行动的概率从指数小的值呈指数增长，从而实现了比先前结果更好的实例相关常数的指数依赖性。实验证实了OMWU在表格和神经策略类中的理论优势，证明了其在LLM应用中的潜力。

🔬 方法详解

问题定义：论文旨在解决在人类偏好学习中，由于人类偏好通常不满足传递性，导致传统偏好模型失效的问题。现有基于正则化的方法在计算对偶间隙时会引入偏差，影响算法的收敛性。因此，需要一种无正则化的方法来更准确地学习人类偏好。

核心思路：论文的核心思路是将人类偏好学习问题建模为一个双人零和博弈，并使用乐观乘性权重更新（OMWU）算法来寻找纳什均衡。OMWU算法通过迭代更新策略，使得两个玩家的策略最终收敛到纳什均衡点，从而实现对人类偏好的准确建模。关键在于避免使用正则化，以消除偏差。

技术框架：整体框架包括以下几个步骤：1）将人类偏好数据转化为零和博弈的形式；2）使用OMWU算法迭代更新两个玩家的策略；3）通过对偶间隙来衡量算法的收敛程度；4）验证算法在不同场景下的性能。该框架的核心是OMWU算法，它负责策略的更新和收敛。

关键创新：论文的关键创新在于提出了无正则化的OMWU算法，并证明了其在Nash学习框架下的线性收敛性。与现有方法相比，该算法不需要正则化，从而避免了偏差的引入。此外，论文还发现了一种新的边际收敛行为，即很少采取的行动的概率会呈指数增长，从而提高了算法的效率。

关键设计：OMWU算法的关键设计包括：1）使用乘性权重更新规则来更新策略；2）使用乐观估计来加速收敛；3）使用对偶间隙作为收敛的衡量标准。算法的具体参数设置需要根据具体的应用场景进行调整。此外，论文还针对表格和神经策略类进行了实验，验证了算法的有效性。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

论文证明了无正则化的OMWU算法在NLHF中实现了线性收敛，且不需要NE唯一性的假设。实验结果表明，OMWU算法在表格和神经策略类中表现出优异的性能，验证了其在LLM应用中的潜力。与现有方法相比，OMWU算法具有更快的收敛速度和更高的精度。

🎯 应用场景

该研究成果可应用于大型语言模型（LLM）的对齐，通过更准确地学习人类偏好，提升LLM的生成质量和安全性。此外，该方法还可应用于推荐系统、博弈论等领域，具有广泛的应用前景和实际价值。未来，可以进一步研究如何将该方法应用于更复杂的场景，并探索其在其他领域的应用。

📄 摘要（原文）

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.