A Unified Perspective on Deep Equilibrium Finding

Xinrun Wang, Jakub Cerný, Shuxin Li, Chang Yang, Zhuyun Yin, Hau Chan, Bo AnarXiv 2022 · DOI · arXiv

Abstract

Solving extensive-form games with imperfect information remains a cornerstone of multi-agent reinforcement learning. Traditionally, the field has been divided between two dominant paradigms: Policy Space Response Oracles (PSRO) and Counterfactual Regret Minimization (CFR). This paper introduces Unified Deep Equilibrium Finding (UDEF), a modular framework that unifies these approaches. By parameterizing the transformation between estimated values and strategies, UDEF can recover existing algorithms as special cases and discover novel hybrid strategies that achieve superior performance in complex games like Poker.

Introduction

In multi-agent game theory, the goal is often to find a Nash Equilibrium, where no player can improve their outcome by unilaterally changing their strategy. For "Extensive-Form Games" (EFGs)—games involving sequential moves and hidden information—two dominant methodologies have emerged. PSRO focuses on iteratively adding "best responses" to a population of opponent strategies, while CFR focuses on minimizing "regret" over time.

Despite their individual successes, these methods are typically treated as entirely different tools. The UDEF framework addresses this dichotomy by asking whether a single architecture can encompass both, allowing for the automatic discovery of the most effective algorithmic components for a given environment.

The UDEF Framework

UDEF decomposes the equilibrium-finding process into four modular, differentiable components. This modularity allows the system to bridge the gap between PSRO and CFR through a shared mathematical representation.

Modular Components

  1. Response Oracle (RO): A neural network that estimates three critical values: Q-values (expected rewards), reaching probabilities (state likelihood), and baseline values.
  2. Transform Modules: These act as "translators." A pre-transform module maps RO outputs into a Latent Additive Space (LAS). A post-transform module then converts these latent values into action probabilities. By adjusting these transforms (e.g., using softmax for PSRO or mapping Q-values to regrets for CFR), the framework can emulate either paradigm.
  3. Average Oracles (AO): These manage how the agent learns from its history, either by averaging strategies locally for sampling or globally for final evaluation.
  4. Fictitious Play Optimization: A novel training method that optimizes the neural networks within the transform and average modules simultaneously.
The UDEF architecture unifies response oracles and transform modules into a cyclical learning process.

The Latent Bridge

The core insight of UDEF is the Latent Additive Space (LAS). By recognizing that both PSRO and CFR rely on additive operations on internal values, the authors created a mathematical "common ground." Using Parametric ReLUs (PReLU) in the transform modules allows the system to learn whether to behave more like CFR+, vanilla CFR, or an entirely new variant. This differentiable evolution allows the system to "search" the space of possible algorithms to find the most efficient one for a specific game.

Experimental Results

The researchers evaluated UDEF on Leduc Poker, a standard benchmark for imperfect information games. Leduc Poker provides a controlled environment to test algorithmic convergence while maintaining the strategic complexity of bluffing and betting.

Performance and Hybridization

UDEF consistently achieved lower "exploitability"—a measure of how close a strategy is to a perfect Nash Equilibrium—compared to Neural Fictitious Self-Play (NFSP) and Deep CFR. Notably, the most effective configurations were often hybrids that leveraged UDEF's unique transform modules rather than "pure" versions of the ancestor algorithms.

Convergence results for NFSP and CFR variants under the UDEF framework across different hyperparameter settings.

Discussion and Future Work

UDEF represents a significant step toward a unified theory of deep equilibrium finding. By making the transition between different algorithmic paradigms differentiable, it enables the use of optimization techniques to find the best algorithm for a specific game.

However, challenges remain. UDEF is sensitive to hyperparameters like learning rates and update steps, requiring more careful tuning than traditional methods. Furthermore, while successful in Leduc Poker, scaling the framework to massive environments like No-Limit Texas Hold'em remains an open area for research. Future work may involve integrating AutoML to automatically configure UDEF modules for new domains.

Reference: Wang, X., et al. (2022). A Unified Perspective on Deep Equilibrium Finding. arXiv:2204.04930v1 [cs.GT].

Summary updated

Abstract

Extensive-form games provide a versatile framework for modeling interactions of multiple agents subjected to imperfect observations and stochastic events. In recent years, two paradigms, policy space response oracles (PSRO) and counterfactual regret minimization (CFR), showed that extensive-form games may indeed be solved efficiently. Both of them are capable of leveraging deep neural networks to tackle the scalability issues inherent to extensive-form games and we refer to them as deep equilibrium-finding algorithms. Even though PSRO and CFR share some similarities, they are often regarded as distinct and the answer to the question of which is superior to the other remains ambiguous. Instead of answering this question directly, in this work we propose a unified perspective on deep equilibrium finding that generalizes both PSRO and CFR. Our four main contributions include: i) a novel response oracle (RO) which computes Q values as well as reaching probability values and baseline values; ii) two transform modules -- a pre-transform and a post-transform -- represented by neural networks transforming the outputs of RO to a latent additive space (LAS), and then the LAS to action probabilities for execution; iii) two average oracles -- local average oracle (LAO) and global average oracle (GAO) -- where LAO operates on LAS and GAO is used for evaluation only; and iv) a novel method inspired by fictitious play that optimizes the transform modules and average oracles, and automatically selects the optimal combination of components of the two frameworks. Experiments on Leduc poker game demonstrate that our approach can outperform both frameworks.
BibTeX
@misc{wang2022unified,
  author = {Xinrun Wang and Jakub Cerný and Shuxin Li and Chang Yang and Zhuyun Yin and Hau Chan and Bo An},
  title = {{A Unified Perspective on Deep Equilibrium Finding}},
  year = {2022},
  eprint = {2204.04930},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2204.04930},
}
Figure