Learning Nash Equilibria in Rank-1 Games

Learning Nash equilibria (NE) in games has garnered significant attention, particularly in the context of training Generative Adversarial Networks (GANs) and multi-agent Reinforcement Learning. The current state-of-the-art in efficiently learning NE in games focuses on landscapes that meet the (weak) minty property or games characterized by a unique function, often referred to as potential games. A significant challenge in this domain is that computing Nash equilibria is a computationally intractable task Daskalakis et al. (2009) . In this paper we focus on bimatrix games (A, B) called rank-1. These are games in which the sum of the payoff matrices A + B is a rank 1 matrix; note that standard zero-sum games are rank-0. We show that a modification of optimistic mirror descent converges to an ϵ-approximate NE after O 1 ϵ 2 log( 1 ϵ ) iterates in rank-1 games. We achieve this by leveraging structural results about the NE landscape of rank-1 games Adsul et al. ( 2021 ). Notably, our approach bypasses the fact that these games do not satisfy the MVI property.