TL;DR
This paper introduces Anytime Double Oracle (ADO) and Anytime PSRO (APSRO), novel algorithms for finding Nash equilibria in large two-player zero-sum games. Unlike existing methods that can increase "exploitability" (how much an opponent can exploit a strategy) during training, ADO and APSRO guarantee monotonic decrease in exploitability, leading to more stable and robust learning.
What Problem Does This Paper Address?
Finding Nash equilibria (NE) in complex games, especially those with a vast number of possible strategies (like poker or strategy games), is a significant challenge in game theory and AI. Policy Space Response Oracles (PSRO) is a powerful algorithm that has achieved state-of-the-art results in such games. However, PSRO is built upon the Double Oracle (DO) method, which, while guaranteed to converge to an NE, has a critical flaw: its "exploitability" can actually increase during the learning process. This means that if PSRO is stopped early (which is common in large, computationally expensive games), the resulting strategy might be more exploitable than the initial one, undermining the goal of finding a robust equilibrium. This paper addresses this instability by proposing methods that guarantee a monotonic decrease in exploitability throughout the learning process.
Methods
The core innovation lies in modifying the Double Oracle (DO) framework.
- Anytime Double Oracle (ADO): This is an exact version of the proposed method. Instead of creating a single restricted game for both players (as in DO), ADO creates two separate restricted games, one for each player. In each player's restricted game, their strategies are limited to their current population, but the opponent can still play any strategy from the full game. This ensures that the restricted Nash equilibrium found for each player is the least exploitable against the opponent's full strategy space. ADO guarantees convergence to a Nash equilibrium and, crucially, monotonically non-increasing exploitability.
- Regret-Minimizing against a Best Response Double Oracle (RM-BR DO): To efficiently compute the least exploitable restricted distribution within ADO, this method uses a no-regret algorithm (specifically, regret minimization against a best response, RM-BR) instead of solving the full restricted game. This avoids the computational bottleneck of solving large restricted games.
- Anytime PSRO (APSRO): This is the reinforcement learning (RL) version of ADO, designed to scale to very large games where exact computation is infeasible. APSRO approximates the best responses using RL policies. Instead of training a full best response in each iteration, it uses an RL policy that is continually updated against the opponent's current strategy. This allows it to handle the vast strategy spaces encountered in modern games.
Datasets
The paper evaluates its methods on:
- Random Normal Form Games: These are games where payoffs are sampled from a uniform distribution. This serves as a general benchmark for tabular methods.
- Leduc Poker: A well-known imperfect-information game used to test the performance of reinforcement learning-based methods.
- Goofspiel: A larger card game with simultaneous moves, used to test scalability.
- 2D Continuous-Action Hill-Climbing Game: A continuous-action game benchmark where previous methods like PSRO have struggled.
Key Insights and Ideas
- Restricted Games for Stability: The key insight is that by defining restricted games where one player is restricted to their current strategy population but the opponent is unrestricted, we can find a least-exploitable strategy for the restricted player. This contrasts with DO, which restricts both players, potentially leading to exploitable outcomes.
- Monotonic Exploitability Decrease: The guarantee of non-increasing exploitability is a significant improvement over DO and PSRO, making the learning process more stable and predictable, especially when training is interrupted.
- No-Regret for Efficiency: Using no-regret algorithms like RM-BR to find the restricted distribution avoids the computational cost of solving large restricted games, making the approach more practical.
- RL for Scalability: APSRO's use of RL for best responses is crucial for tackling the massive state and action spaces of modern games, where exact methods are intractable.
Key Results
- ADO and RM-BR DO: In tabular experiments on random normal form games and Leduc poker, ADO and RM-BR DO significantly outperform DO in terms of lower exploitability and monotonic decrease.
- APSRO: APSRO, the RL version, shows competitive performance with PSRO on Leduc poker and Goofspiel, often exhibiting smoother exploitability curves. It also performs much better than PSRO on the continuous-action hill-climbing game, where PSRO previously struggled.
- DO's Exploitability Issue: The paper demonstrates with a specific game example (and a generalization) that DO can indeed arbitrarily increase exploitability over iterations, highlighting the problem ADO aims to solve.
Limitations and Future Work
- Convergence Time: Like DO, ADO's convergence time can be long in games with complex subgame structures. The paper suggests that reducing the size of these worst-case sequences is an open question.
- Novel Best Responses: ADO requires finding novel best responses to avoid getting stuck. In APSRO, finding novel best responses with RL can be challenging. The authors suggest incorporating a "diversity reward" for best responses as a potential solution.
- Approximation Errors: While RM-BR DO and APSRO offer practical advantages, they rely on approximations (from no-regret algorithms or RL). The paper notes that these approximations can introduce errors, and the theoretical guarantees might be affected.
The authors also mention that their code will be made available, which is a positive step for reproducibility and further research.
Summary updated