论文标题
一种最佳分布式算法，具有随机聚合游戏的操作员外推外
An Optimal Distributed Algorithm with Operator Extrapolation for Stochastic Aggregative Games
论文作者
论文摘要
这项工作研究了NASH均衡，以寻求一类随机聚合游戏，在该游戏中，每个玩家都具有期望值的目标功能，具体取决于其本地策略和所有玩家策略的总体。我们提出了一种分布式算法，并通过运算符外推，在其中，每个玩家通过在随着时间的变化网络上与邻居交换此信息来维护此汇总的估计，并通过镜像下降方法更新其决策。应用搜索方向的操作员推断，以便将两个步骤的历史梯度样本用于加速收敛。在伪梯度映射的强烈单调假设下，我们证明所提出的算法可以实现NASH寻求随机游戏的NASH平衡的$ \ Mathcal {O} $的最佳收敛速率。最后，通过数值模拟证明了算法性能。
This work studies Nash equilibrium seeking for a class of stochastic aggregative games, where each player has an expectation-valued objective function depending on its local strategy and the aggregate of all players' strategies. We propose a distributed algorithm with operator extrapolation, in which each player maintains an estimate of this aggregate by exchanging this information with its neighbors over a time-varying network, and updates its decision through the mirror descent method. An operator extrapolation at the search direction is applied such that the two step historical gradient samples are utilized to accelerate the convergence. Under the strongly monotone assumption on the pseudo-gradient mapping, we prove that the proposed algorithm can achieve the optimal convergence rate of $\mathcal{O}(1/k)$ for Nash equilibrium seeking of stochastic games. Finally, the algorithm performance is demonstrated via numerical simulations.
