Efficient Distributed Learning in Stochastic Non-cooperative Games without Information Exchange

Abstract

In this work, we study stochastic non-cooperative games, where only noisy black-box function evaluations are available to estimate the cost function for each player. Since each player's cost function depends on both its own decision variables and its rivals' decision variables, local information needs to be exchanged through a center/network in most existing work for seeking the Nash equilibrium. We propose a new stochastic distributed learning algorithm that does not require communications among players. The proposed algorithm uses simultaneous perturbation method to estimate the gradient of each cost function, and uses mirror descent method to search for the Nash equilibrium. We provide asymptotic analysis for the bias and variance of gradient estimates, and show the proposed algorithm converges to the Nash equilibrium in mean square for the class of strictly monotone games at a rate faster than the existing algorithms. The effectiveness of the proposed method is buttressed in a numerical experiment.

References in corpus (8)

• A Passivity-Based Approach to Nash Equilibrium Seeking over Networks
• Distributed Nash equilibrium seeking for aggregative games with coupled constraints
• A distributed primal-dual algorithm for computation of generalized Nash equilibria with shared affine coupling constraints via operator splitting methods
• Distributed GNE seeking under partial-decision information over networks via a doubly-augmented operator splitting approach
• Semi-decentralized generalized Nash equilibrium seeking in monotone aggregative games
• A Distributed Nash Equilibrium Seeking in Networked Graphical Games
• Extrapolation-based Prediction-Correction Methods for Time-varying Convex Optimization
• Monotone Lipschitz-Gradient Denoiser: Explainability of Operator Regularization Approaches Free From Lipschitz Constant Control