提出分步更新策略，大幅降低多玩家博弈中的通信开销。
Decoupled SGDA for Games with Intermittent Strategy Communication
- 玩家基于过时对手策略独立更新，定期同步对齐
- 在强凸-强凹博弈中通信复杂度接近最优
- 适合通信受限或噪声不均的多玩家场景
针对多玩家博弈中频繁交换策略不可行、策略存在噪声或延迟的问题，提出分步随机梯度下降上升（Decoupled SGDA）。玩家基于过时对手策略独立更新，周期性同步以对齐策略。在强凸-强凹（SCSC）博弈中，该方法实现近最优通信复杂度，与最佳已知GDA速率相当。对于弱耦合博弈（玩家间交互较弱于非交互部分），相比标准SGDA显著降低通信成本。研究扩展至多玩家场景，并通过二次极小极大问题深入分析通信频率与收敛性关系。在玩家噪声不平衡的设置下，该方法显著优于联邦极小极大方法。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。