Nash Policy Gradient: A Policy Gradient Method with Iteratively Refined Regularization for Finding Nash Equilibria
This addresses the problem of unstable learning in multi-agent reinforcement learning for game theory applications, offering a more robust approach to finding Nash equilibria, though it is incremental as it builds on regularization-based methods.
The paper tackles the challenge of finding Nash equilibria in imperfect-information games by proposing a method that fixes regularization strength for robustness and iteratively refines the reference policy, achieving convergence to exact Nash equilibria in two-player zero-sum games with theoretical guarantees. Empirically, NashPG shows comparable or lower exploitability on benchmarks and scales to large domains like Battleship and No-Limit Texas Hold'em, attaining higher Elo ratings.
Finding Nash equilibria in imperfect-information games remains a central challenge in multi-agent reinforcement learning. While regularization-based methods have recently achieved last-iteration convergence to a regularized equilibrium, they require the regularization strength to shrink toward zero to approximate a Nash equilibrium, often leading to unstable learning in practice. Instead, we fix the regularization strength at a large value for robustness and achieve convergence by iteratively refining the reference policy. Our main theoretical result shows that this procedure guarantees strictly monotonic improvement and convergence to an exact Nash equilibrium in two-player zero-sum games, without requiring a uniqueness assumption. Building on this framework, we develop a practical algorithm, Nash Policy Gradient (NashPG), which preserves the generalizability of policy gradient methods while relying solely on the current and reference policies. Empirically, NashPG achieves comparable or lower exploitability than prior model-free methods on classic benchmark games and scales to large domains such as Battleship and No-Limit Texas Hold'em, where NashPG consistently attains higher Elo ratings.