Convergence Rate of Payoff-based Generalized Nash Equilibrium Learning

Tatiana Tatarenko, Maryam Kamgarpour

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:

  1. 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.
  2. 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.
  3. 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$).

Distance to the v-GNE over time for different sampling variance decay rates (s).

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

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(\frac{1}{t^{4/7}})$ to a v-GNE of the game.
BibTeX
@article{tatarenko2025convergence,
  author = {Tatiana Tatarenko and Maryam Kamgarpour},
  title = {{Convergence Rate of Payoff-based Generalized Nash Equilibrium Learning}},
  journal = {European Journal of Control},
  year = {2025},
  url = {https://openreview.net/forum?id=xJ8sKpg7bM},
}
Figure