Hierarchical Deep Counterfactual Regret Minimization

Jiayu Chen, Tian Lan, Vaneet Aggarwal

Abstract

This paper introduces Hierarchical Deep Counterfactual Regret Minimization (HDCFR), the first hierarchical extension of Deep CFR designed for complex imperfect information games (IIGs). By integrating the reinforcement learning "options" framework, HDCFR decomposes strategies into high-level skill selection and low-level skill execution. This approach addresses the scalability and horizon sensitivity issues inherent in traditional Counterfactual Regret Minimization (CFR). Experimental results on large-scale poker benchmarks, including variants with up to $3.17 \times 10^{13}$ nodes, demonstrate that HDCFR achieves superior convergence, sample efficiency, and transferability compared to existing state-of-the-art methods.

Introduction

Imperfect Information Games (IIGs)—such as poker, cybersecurity simulations, and auctions—present a significant challenge for artificial intelligence due to the necessity of decision-making under uncertainty. The gold standard for solving these games is Counterfactual Regret Minimization (CFR), an iterative algorithm that minimizes the "regret" of not having taken specific actions.

However, standard CFR faces two primary limitations: scalability and horizon sensitivity. Traditional CFR requires traversing the entire game tree, which is computationally infeasible for complex games. Furthermore, even modern "Deep" versions of CFR struggle as the game tree depth increases, as they lack the mechanism to group sequences of actions into meaningful temporal abstractions. This makes learning in deep-horizon games inefficient, akin to learning a language by memorizing individual characters rather than words or phrases.

Methodology

HDCFR addresses these challenges by decomposing a player's strategy into a two-level hierarchy:

  1. Low-level Strategy (Skills): These encode specific subgame-solving behaviors, such as managing a specific hand type or betting pattern.
  2. High-level Strategy (Skill Selection): This level manages the transition between learned skills based on the current state of the game.

Technical Innovations

The authors introduce several key innovations to make this hierarchical approach viable:

  • Hierarchical CFR (HCFR) Rules: The researchers derived new tabular updating rules for hierarchical regrets. They mathematically proved that these rules maintain the standard CFR convergence rate of $O(T^{-0.5})$.
  • Low-Variance Outcome Sampling: To enable model-free learning without requiring the exact game tree, HDCFR utilizes Monte Carlo sampling. A novel hierarchical baseline function was introduced to mitigate the high variance typically associated with deep-horizon sampling, stabilizing the learning process.
  • Neural Approximation: The system employs neural networks to approximate regrets and strategies. Specifically, Multi-Head Attention is used for the high-level policy, allowing the agent to generalize across vast state spaces.

Experimental Evaluation

The performance of HDCFR was evaluated on several poker benchmarks with increasing decision horizons:

  • Leduc Poker Variants: Including Leduc_10, _15, and _20. The Leduc_20 variant features a game tree with over 113,000 nodes.
  • Heads-up Flop Hold’em (FHP): A significantly larger challenge. The researchers tested on FHP and FHP_10, the latter of which contains a staggering $3.17 \times 10^{13}$ nodes.

Key Results

HDCFR demonstrated superior performance across all metrics:

  • Convergence: In Leduc_20, HDCFR achieved significantly lower exploitability (moving closer to a Nash Equilibrium) than state-of-the-art baselines like DREAM and OSSDCFR.
  • Head-to-Head Performance: In direct competition, HDCFR's advantage scaled with task difficulty. In FHP_10, it outperformed the DREAM agent by a wide margin of 282.42 ± 14.20 mbb/g.
  • Sample Efficiency: HDCFR proved more efficient than reinforcement learning methods like NFSP; while NFSP required $10^8$ game state visits, HDCFR achieved superior results with only $10^7$ visits.

Discussion and Insights

The success of HDCFR highlights the power of abstraction in IIGs. By treating sequences of actions as single "options," the agent effectively shrinks the game tree, making deep-horizon problems manageable.

Furthermore, the study revealed the potential for skill transferability. Skills learned in simpler environments (e.g., Leduc_15) could be "injected" into more complex ones (e.g., Leduc_20) as a warm-start, leading to faster convergence. Beyond performance, the hierarchical structure improves interpretability; researchers can observe which high-level "skill" the AI is employing, providing insight into the agent's decision-making process that black-box models lack.

Conclusion

While HDCFR represents a significant leap forward, challenges remain. Training on the largest FHP games is still computationally intensive, requiring approximately seven days on an 8-core setup. Additionally, while skills can be transferred, the automatic discovery of optimal skills (Unsupervised Option Discovery) remains an open problem. Future work may explore "interactive learning," where human experts provide initial skill sets that the AI refines through self-play.

Summary updated

Abstract

Imperfect Information Games (IIGs) offer robust models for scenarios where decision-makers face uncertainty or lack complete information. Counterfactual Regret Minimization (CFR) has been one of the most successful family of algorithms for tackling IIGs. The integration of skill-based strategy learning with CFR could potentially enhance learning performance for complex IIGs. For this, a hierarchical strategy needs to be learnt, wherein low-level components represent specific skills and the high-level component manages the transition between skills. This hierarchical approach also enhances interpretability, helping humans pinpoint scenarios where the agent is struggling and intervene with targeted expertise. This paper introduces the first hierarchical version of Deep CFR (HDCFR), an innovative method that boosts learning efficiency in tasks involving extensively large state spaces and deep game trees. A notable advantage of HDCFR over previous research in this field is its ability to facilitate learning with predefined (human) expertise and foster the acquisition of transferable skills that can be applied to similar tasks. To achieve this, we initially construct our algorithm on a tabular setting, encompassing hierarchical CFR updating rules and a variance-reduced Monte-Carlo sampling extension, and offer its essential theoretical guarantees. Then, to adapt our algorithm for large-scale applications, we employ neural networks as function approximators and suggest deep learning objectives that coincide with those in the tabular setting while maintaining the theoretical outcomes.
BibTeX
@misc{chen2023hierarchical,
  author = {Jiayu Chen and Tian Lan and Vaneet Aggarwal},
  title = {{Hierarchical Deep Counterfactual Regret Minimization}},
  year = {2023},
  eprint = {2305.17327},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2305.17327},
}
Figure