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

We derive the rate of convergence to Nash equilibria for the payoff-based algorithm proposed in citetatkamTAC. 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(frac1T) in the two-point function evaluating setting and O(frac1√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.