Decoupled SGDA for Games with Intermittent Strategy Communication
This addresses communication inefficiencies in distributed game theory for scenarios with intermittent or noisy strategy exchanges, offering an incremental improvement over existing methods.
The paper tackles the problem of high communication overhead in multiplayer games by introducing Decoupled SGDA, which reduces communication costs by allowing players to update strategies independently with periodic synchronization, achieving near-optimal communication complexity for SCSC games and significant reductions in weakly coupled games.
We focus on reducing communication overhead in multiplayer games, where frequently exchanging strategies between players is not feasible and players have noisy or outdated strategies of the other players. We introduce Decoupled SGDA, a novel adaptation of Stochastic Gradient Descent Ascent (SGDA). In this approach, players independently update their strategies based on outdated opponent strategies, with periodic synchronization to align strategies. For Strongly-Convex-Strongly-Concave (SCSC) games, we demonstrate that Decoupled SGDA achieves near-optimal communication complexity comparable to the best-known GDA rates. For weakly coupled games where the interaction between players is lower relative to the non-interactive part of the game, Decoupled SGDA significantly reduces communication costs compared to standard SGDA. Our findings extend to multi-player games. To provide insights into the effect of communication frequency and convergence, we extensively study the convergence of Decoupled SGDA for quadratic minimax problems. Lastly, in settings where the noise over the players is imbalanced, Decoupled SGDA significantly outperforms federated minimax methods.