论文标题
连续游戏混合纳什平衡的指数收敛的粒子方法
An Exponentially Converging Particle Method for the Mixed Nash Equilibrium of Continuous Games
论文作者
论文摘要
我们考虑了与连续的纯策略集合以及对收益功能的一阶访问，计算两人零和游戏的混合NASH平衡问题。例如，在游戏理论启发的机器学习应用程序中出现了这个问题，例如分布型学习。在这些应用程序中，策略集是高维的，因此基于离散化的方法不能易于返回高准确的解决方案。 在本文中，我们介绍并分析了一种基于粒子的方法，该方法享受了为此问题提供保证的局部收敛。该方法包括将混合策略作为原子测量和将近端更新应用于原子的权重和位置。它可以解释为“相互作用” Wasserstein-Fisher-Rao梯度流的时间无限离散化。 我们证明，在非分类假设下，该方法以指数速率收敛到确切的混合NASH平衡，从任何初始化满足最亲密的最亲密概念的初始化。我们通过数值实验说明了我们的结果，并使用两层神经网络讨论了对最大残余和分布分类分类的应用，在这些神经网络中，我们的方法具有自然的解释，作为对网络的权重和对抗性分布的同时培训。
We consider the problem of computing mixed Nash equilibria of two-player zero-sum games with continuous sets of pure strategies and with first-order access to the payoff function. This problem arises for example in game-theory-inspired machine learning applications, such as distributionally-robust learning. In those applications, the strategy sets are high-dimensional and thus methods based on discretisation cannot tractably return high-accuracy solutions. In this paper, we introduce and analyze a particle-based method that enjoys guaranteed local convergence for this problem. This method consists in parametrizing the mixed strategies as atomic measures and applying proximal point updates to both the atoms' weights and positions. It can be interpreted as a time-implicit discretization of the "interacting" Wasserstein-Fisher-Rao gradient flow. We prove that, under non-degeneracy assumptions, this method converges at an exponential rate to the exact mixed Nash equilibrium from any initialization satisfying a natural notion of closeness to optimality. We illustrate our results with numerical experiments and discuss applications to max-margin and distributionally-robust classification using two-layer neural networks, where our method has a natural interpretation as a simultaneous training of the network's weights and of the adversarial distribution.
