Distributed Dynamic No-Regret Learning in Two-Network Zero-Sum Games

This paper considers the time-varying zero-sum game between two multi-agent networks with different topologies. The two networks are modeled as adversarial players, where agents within each network communicate with their local neighbors while simultaneously gathering information from the opposing network through a bipartite interaction framework. The payoffs of the agents can be quantified by time-varying cost functions, and the objective is to design an online distributed algorithm to optimize the payoff for each network in the game. We use dynamic Nash equilibrium regret and duality gap as performance metrics and propose a projection-free algorithm called Online Distributed Frank-Wolfe in Two-Network (ODFW-TN). We assess the convergence of Algorithm ODFW-TN through regret analysis, and establish sublinear bounds for dynamic Nash equilibrium regret and duality gap of Algorithm ODFW-TN with respect to T, where T is the total number of games. Moreover, we validate the effectiveness of Algorithm ODFW-TN via a numerical experiment of a time-varying bilinear matrix game.