提出一种稳定求解双人零和博弈的随机动力学算法
On the Convergence of Min-Max Langevin Dynamics and Algorithm
- 基于熵正则化与光滑强凸-强凹交互函数设计平均场动力学
- 连续与离散时间下均实现指数收敛，粒子数不影响偏差项
- 适合研究博弈论、生成模型中的均衡计算问题
我们研究欧氏空间 ℝᵈ 上概率分布之间的零和博弈，采用熵正则化，在玩家间交互函数光滑且强凸-强凹的设定下，证明了平均场极小极大Langevin动力学可指数收敛至博弈均衡分布。进一步研究了该动力学在有限粒子数下的连续与离散时间近似，证明连续时间有限粒子系统以不随粒子数增长的显式偏差项收敛至平稳平均场均衡分布；离散时间有限粒子算法也具有额外依赖步长和粒子数的偏差项，给出了平均粒子逼近均衡分布的显式迭代复杂度。
原文摘要 · Abstract (English)
We study zero-sum games in the space of probability distributions over the Euclidean space $\mathbb{R}^d$ with entropy regularization, in the setting when the interaction function between the players is smooth and strongly convex-strongly concave. We prove an exponential convergence guarantee for the mean-field min-max Langevin dynamics to compute the equilibrium distribution of the zero-sum game. We also study the finite-particle approximation of the mean-field min-max Langevin dynamics, both in continuous and discrete times. We prove biased convergence guarantees for the continuous-time finite-particle min-max Langevin dynamics to the stationary mean-field equilibrium distribution with an explicit bias term which does not scale with the number of particles. We also prove biased convergence guarantees for the discrete-time finite-particle min-max Langevin algorithm to the stationary mean-field equilibrium distribution with an additional bias term which scales with the step size and the number of particles. This provides an explicit iteration complexity for the average particle along the finite-particle algorithm to approximately compute the equilibrium distribution of the zero-sum game.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。