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:
- Low-level Strategy (Skills): These encode specific subgame-solving behaviors, such as managing a specific hand type or betting pattern.
- 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