Computing Approximate Nash Equilibrium in Two-Team Zero-Sum Games by NashConv Descent
摘要
Artificial intelligence algorithms have achieved superhuman performances in two-player zero-sum (2p0s) games by approximating Nash equilibrium. However, many real-world competitive scenarios are modeled as two-team zero-sum (2t0s) games, where a team of multiple players cooperatively competes against the other team. Despite the ubiquity, existing methods can only approximate Nash equilibrium in limited settings of 2t0s games. In this paper, we present an iterative algorithm to approximate Nash equilibrium in extensive-form general 2t0s games. To this end, we extend the concept of NashConv from 2p0s games to 2t0s games, which represents the total potential improvement if each player individually switched to its best response. NashConv provides a metric to measure the distance of a policy profile from a Nash equilibrium. The proposed algorithm, NashConv Descent, implements direct policy optimization based on NashConv. Utilizing tabular policy and iteratively performing policy gradient descent on NashConv for each player, our algorithm locally minimizes NashConv, thereby approximating Nash equilibrium. We evaluate our method on imperfect information benchmarks, such as multi-player Kuhn Poker and Leduc Poker. To the best of our knowledge, NashConv Descent is the first algorithm that empirically achieves approximate Nash equilibrium in extensive-form 2t0s games. Furthermore, our method attains the lowest NashConv compared to adaptations of existing equilibrium-computing algorithms tailored for extensive-form 2t0s games.