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

We consider a distributed learning problem in a two-network zero-sum game with finite action sets, where the agents within each network is connected through time-varying directed graphs and the agents from distinct networks are connected by time-varying bipartite graphs. Each agent in a network has its own cost function and can receive information from its neighbors, while the networks have no global decision-making capability. We propose a distributed multiplicative weights algorithm to compute a mixed-strategy Nash equilibrium. We first establish a sublinear regret bound on the sequence of iterates for each agent. Additionally, we study the time-averaged sequence of iterates and prove its convergence to the set of mixed-strategy Nash equilibria with suitably selected diminishing step-sizes.