On the Rate of Convergence of Payoff-based Algorithms to Nash Equilibrium in Strongly Monotone Games
share
We derive the rate of convergence to Nash equilibria for the payoff-based algorithm proposed in <cit.>. 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(1/T) in the two-point function evaluating setting and O(1/√(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.
READ FULL TEXT