Score-Based Equilibrium Learning in Multi-Player Finite Games with Imperfect Information

Runyu Lu, Yuanheng Zhu, Dongbin ZhaoarXiv 2023 · DOI · arXiv

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.
Theoretical framework of IESL connecting Nash Distributions to Approximate Nash Equilibria.

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).

Comparison of NashConv values across different poker variants for IESL and baseline algorithms.

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

Abstract

Real-world games, which concern imperfect information, multiple players, and simultaneous moves, are less frequently discussed in the existing literature of game theory. While reinforcement learning (RL) provides a general framework to extend the game theoretical algorithms, the assumptions that guarantee their convergence towards Nash equilibria may no longer hold in real-world games. Starting from the definition of the Nash distribution, we construct a continuous-time dynamic named imperfect-information exponential-decay score-based learning (IESL) to find approximate Nash equilibria in games with the above-mentioned features. Theoretical analysis demonstrates that IESL yields equilibrium-approaching policies in imperfect information simultaneous games with the basic assumption of concavity. Experimental results show that IESL manages to find approximate Nash equilibria in four canonical poker scenarios and significantly outperforms three other representative algorithms in 3-player Leduc poker, manifesting its equilibrium-finding ability even in practical sequential games. Furthermore, related to the concept of game hypomonotonicity, a trade-off between the convergence of the IESL dynamic and the ultimate NashConv of the convergent policies is observed from the perspectives of both theory and experiment.
BibTeX
@misc{lu2023score,
  author = {Runyu Lu and Yuanheng Zhu and Dongbin Zhao},
  title = {{Score-Based Equilibrium Learning in Multi-Player Finite Games with Imperfect Information}},
  year = {2023},
  eprint = {2306.00350},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2306.00350},
}
Figure