Purified Policy Space Response Oracles for Symmetric Zero-Sum Games

Area of Science:

• Game Theory
• Artificial Intelligence
• Computational Game Theory

Background:

• Policy Space Response Oracles (PSRO) are used to find approximate Nash equilibria (NE) in two-player zero-sum games.
• Existing PSRO methods suffer from slow strategy population diversity growth, leading to poor exploration and convergence.
• High correlation among best responses in traditional PSRO limits exploration efficiency.

Purpose of the Study:

• To introduce Purified PSRO, a novel algorithm for enhanced exploration and faster convergence in finding Nash equilibria.
• To address the limitations of existing PSRO variants regarding strategy population diversity.
• To improve the efficiency of finding approximate Nash equilibria in complex games.

Main Methods:

• Purified PSRO maintains a pure strategy population derived from approximate best responses.
• Introduces a Non-Best Response Suppression (NBRS) module for calculating orthogonal pure strategy bases.
• Incorporates an early stop module to optimize computation cost and provides exploitability bounds.

Main Results:

• Purified PSRO significantly increases strategy population diversity, enhancing exploration efficiency.
• The algorithm demonstrates faster convergence rates compared to existing state-of-the-art methods.
• Experiments show superior performance on random games of skill and real-world meta-games.

Conclusions:

• Purified PSRO offers a more efficient and effective approach to finding approximate Nash equilibria.
• The NBRS module and pure strategy population are key to improved exploration and convergence.
• The proposed method consistently outperforms existing techniques, offering a significant advancement in computational game theory.