Abstract
We consider generalized Nash equilibrium (GNE) problems in games with strongly monotone pseudo-gradients and jointly linear coupling constraints. We establish the convergence rate of a payoff-based approach intended to learn a variational GNE (v-GNE) in such games. While convergent algorithms have recently been proposed in this setting given full or partial information of the gradients, rate of convergence in the payoff-based information setting has been an open problem. Leveraging properties of a game extended from the original one by a dual player, we establish a convergence rate of $O(t^{-4/7})$ to a v-GNE of the game.
Introduction
In many real-world multi-agent systems—such as electricity markets, traffic routing, or sensor networks—agents seek to reach an equilibrium. However, two major hurdles often complicate this process: coupled constraints and information scarcity. In a Generalized Nash Equilibrium (GNE) problem, an agent's available actions depend on the actions of others (e.g., multiple companies sharing a limited power grid). Furthermore, agents often lack the mathematical formula for their cost functions or constraints, observing only their own "payoff" (zeroth-order information) after taking an action.
While previous research has developed algorithms that eventually converge in this payoff-based setting, the specific rate of convergence remained an open question. This work fills that gap for games characterized by strongly monotone pseudo-gradients and linear constraints.
The Payoff-Based Learning Algorithm
The proposed algorithm addresses the GNE problem through three primary mechanisms:
- Dual Player Formulation: To manage shared constraints, the GNE problem is transformed into an unconstrained "augmented game." A virtual $(N+1)$-th player (the dual player) is introduced to manage constraints via Lagrange multipliers.
- Tikhonov Regularization: Because the augmented game is monotone but not strongly monotone in the dual variables, proving convergence rates is traditionally difficult. The authors incorporate a time-varying regularization term ($\epsilon_t$) to enforce strong monotonicity.
- Two-Point Gradient Estimation: Lacking direct access to gradients, players use a randomized sampling technique. By perturbing their actions according to a Gaussian distribution and comparing payoffs at two nearby points, they can estimate the gradient direction.
Theoretical Convergence Rate
The core contribution of this paper is establishing the first-ever convergence rate for payoff-based GNE learning in non-potential games. By carefully balancing the step size ($\gamma_t$), the regularization parameter ($\epsilon_t$), and the sampling variance ($\sigma_t$), the authors prove an expected convergence rate of $O(t^{-4/7})$ to the unique variational GNE (v-GNE).
This rate represents a "mathematical tax" for the lack of gradient information and the presence of coupling constraints. In simpler games without these constraints, payoff-based methods can achieve $O(1/t)$, whereas gradient-based methods in GNE settings can reach $O(1/t^2)$ or linear rates.
Numerical Validation
The theoretical results were validated using a synthetic two-player game with quadratic cost functions and a shared linear inequality constraint ($a^1 + a^2 \geq 1$).
As shown in the simulation, the choice of sampling variance decay ($s$) is critical. If the sampling noise is reduced too quickly (e.g., $s=10$), the gradient estimates become too small, and the algorithm fails to make further progress toward the v-GNE. Conversely, the rate $s=4/7$ aligns with the theoretical findings for stable convergence.
Conclusion
This paper provides a foundational convergence rate for zeroth-order learning in constrained games. While the $O(t^{-4/7})$ rate is slower than gradient-based alternatives, it establishes a performance baseline for settings where only payoff information is available. Future work may explore optimizing hyperparameter tuning and extending these results to non-linear coupling constraints.
Summary updated