Abstract
Finding Nash equilibria in multi-player games with imperfect information and simultaneous moves remains a significant challenge in game theory and reinforcement learning. This paper introduces IESL (Imperfect-information Exponential-decay Score-based Learning), a continuous-time algorithm that leverages exponential-decay scores and entropy regularization. We provide theoretical guarantees linking the algorithm's rest points to approximate Nash equilibria and demonstrate that IESL significantly outperforms established benchmarks like Counterfactual Regret Minimization (CFR) in complex 3-player poker environments.
Introduction
Most real-world strategic interactions—from high-stakes poker to autonomous drone coordination—involve three difficult elements: imperfect information (hidden knowledge), multiple players, and simultaneous moves. While Game Theory provides the "Nash Equilibrium" as a gold standard for optimal play, finding it in these settings is notoriously hard, technically classified as PPAD-complete.
Existing algorithms like Fictitious Play (FP) or Counterfactual Regret Minimization (CFR) are powerful but often rely on specific assumptions, such as two-player zero-sum structures, that do not hold up in multi-player or simultaneous-move environments. Furthermore, many Reinforcement Learning (RL) approaches suffer from "cycling," where policies chase each other in circles rather than settling on a stable equilibrium.
Methodology
The authors propose a new learning dynamic called IESL. The core idea is to move away from simply tracking average policies and instead use a score-based approach. Key components include:
- Exponential-Decay Scores: Instead of a simple running average of past performance, IESL uses a score function where older information is exponentially discounted. This prevents the algorithm's memory from being dominated by early, sub-optimal play.
- Entropy Regularization: The algorithm uses a "softmax" policy choice regularized by negative Gibbs entropy. This ensures the agent continues to explore and prevents the policy from becoming too brittle too early. Finding the optimal regularization parameter $\epsilon$ is crucial, as smaller values yield more precise equilibria but can lead to slower convergence.
- Theoretical Framework: By modeling the game as a Partially Observable Stochastic Game (POSG), the authors bridge the gap between RL and Game Theory. They prove that the "rest points" of IESL correspond to approximate Nash equilibria, provided the game's utility function is concave.
To prove that the algorithm actually reaches these rest points, the authors utilize the concept of "local hypomonotonicity," showing that IESL is naturally attracted to equilibrium regions.
Experimental Evaluation
The algorithm was evaluated on four canonical benchmark poker environments: 2-player and 3-player Kuhn Poker, and 2-player and 3-player Leduc Poker. These games capture the essence of bluffing and uncertainty while remaining computationally manageable for testing new theories.
Key Results
IESL demonstrated superior performance and stability, particularly in multi-player settings. In the 3-player Leduc poker test, IESL achieved a NashConv of 0.052, significantly outperforming CFR (0.466), Fictitious Play (0.198), and Replicator Dynamics (0.540).
While other algorithms like Replicator Dynamics (RD) performed well in 2-player games but failed in 3-player games, IESL remained stable across all tested scenarios. The authors also demonstrated that an optimal $\epsilon$ can be found efficiently using a simple binary search, making the algorithm practical to tune for different game complexities.
Conclusion and Future Work
IESL provides a robust theoretical and practical framework for finding strategic equilibria in complex multi-player games. The primary current limitation is that IESL is tabular, requiring the storage of values for every possible state in the game tree. The authors suggest that the next logical step is to combine IESL with Deep Reinforcement Learning (DRL). By using neural networks to approximate the score functions instead of giant tables, the IESL dynamic could potentially be scaled to solve massive, real-world strategic problems like No-Limit Texas Hold'em or large-scale autonomous coordination.
Summary updated