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

2022/02/22 by Tatiana Tatarenko, Tatarenko, Tatiana, Maryam Kamgarpour +1
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Distributed Control Multi-Agent Systems #FOS: Computer and information sciences #FOS: Mathematics #Multiagent Systems (cs.MA) #Optimization and Control (math.OC) #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2202.11147

openalex publication_date 2022/02/22 · openalex created_date 2022/04/03 · openalex updated_date 2026/07/28

Abstract

We derive the rate of convergence to Nash equilibria for the payoff-based algorithm proposed in \citetat_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((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.

Related

• Convergence Rate of Payoff-based Generalized Nash Equilibrium Learning
• Convergence Rate of Generalized Nash Equilibrium Learning in Strongly Monotone Games with Linear Constraints
• Convergence Rate of Learning a Strongly Variationally Stable Equilibrium
• Bandit Learning in Convex Non-Strictly Monotone Games
• Fast Distributed Nash Equilibrium Seeking in Monotone Games