On the Rate of Convergence of Payoff-based Algorithms to Nash Equilibrium in Strongly Monotone Games

preprint2022arXivOpen access

Abstract

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(1T)O(\frac{1}{T}) in the two-point function evaluating setting and O(1T)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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.