论文标题
在强烈单调游戏中，基于回报的算法与NASH平衡的收敛速度
On the Rate of Convergence of Payoff-based Algorithms to Nash Equilibrium in Strongly Monotone Games
论文作者
论文摘要
对于\ cite {tat_kam_tac}提出的基于回报的算法，我们将收敛速率与NASH平衡的速率得出。这些速率是在游戏凸的标准假设下实现的，伪级的强烈单调性和可不同的性能。特别是，我们在两点函数评估设置中显示了算法达到$ o（\ frac {1} {t}）$，在单点函数的lipschitz Contricement of Pseudo-gradien的额外要求下，在单点功能中评估$ O（\ frac {1} {\ frac {\ frac {\ sqrt {t}}）$。据我们所知，这些速率是相应问题类别的最著名费率。
We derive the rate of convergence to Nash equilibria for the payoff-based algorithm proposed in \cite{tat_kam_TAC}. These rates are achieved under the standard assumption of convexity of the game, strong monotonicity and differentiability of the pseudo-gradient. In particular, we show the algorithm achieves $O(\frac{1}{T})$ in the two-point function evaluating setting and $O(\frac{1}{\sqrt{T}})$ in the one-point function evaluation under additional requirement of Lipschitz continuity of the pseudo-gradient. These rates are to our knowledge the best known rates for the corresponding problem classes.
