💻 computer science

Hierarchical Deep Counterfactual Regret Minimization

This paper introduces Hierarchical Deep Counterfactual Regret Minimization (HDCFR), a novel algorithm that integrates skill-based hierarchical strategy learning with Deep CFR to improve efficiency in solving large-scale imperfect information games by enabling the use of predefined expertise and transferable skills.

Original authors: Jiayu Chen, Xudong Wu, Zhekai Wang, Vaneet Aggarwal

Published 2026-10-05

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Jiayu Chen, Xudong Wu, Zhekai Wang, Vaneet Aggarwal

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of artificial intelligence, some of the most difficult challenges come from games where players cannot see the whole board. Think of a poker table: you know your own cards and the cards on the table, but you have no idea what your opponent is holding. This lack of complete information creates a landscape of uncertainty where every decision must be weighed against hidden possibilities. For decades, researchers have used a method called counterfactual regret minimization to teach computers how to play these games. The logic is straightforward: after a game ends, the computer looks back at every choice it made and asks, "What if I had done something else?" If changing that choice would have led to a better outcome, the computer feels a sense of "regret." Over millions of games, it learns to minimize this regret, eventually settling on a strategy so strong that no opponent can consistently beat it. This approach has produced some of the most formidable poker-playing AIs in history.

However, a major problem arises when the game becomes too complex. In simple poker variants, the computer can map out every possible path the game might take. But in more intricate versions with longer sequences of play, the number of possible paths explodes into the trillions. The traditional method, which requires checking every single path to calculate regret, becomes impossible because the computer would need to process more data than exists in the universe. To solve this, researchers have turned to deep learning, using neural networks to guess the right moves without checking every possibility. Yet, even these advanced systems struggle when the game stretches out over a long horizon, often getting lost in the sheer volume of random noise generated by sampling just a few paths. They lack a way to organize their thinking into manageable chunks, much like a human who tries to remember a thousand individual steps instead of recognizing a few familiar routines.

A team of researchers from the University of Hong Kong, Peking University, and Purdue University has introduced a new approach called Hierarchical Deep Counterfactual Regret Minimization, or HDCFR, designed to overcome these limitations. Their work, published in a research article, proposes that instead of forcing the AI to learn every tiny move from scratch, they should teach it to learn "skills" first. In this system, the AI learns low-level components that act as specific skills for solving small parts of the game, such as a particular betting pattern or a defensive maneuver. A higher-level component then acts as a manager, deciding which skill to use at any given moment and when to switch between them. This structure mimics how humans play: we do not think about every single muscle movement when driving a car; we think in terms of "turning left," "changing lanes," or "stopping," and we switch between these high-level goals as the situation changes.

The researchers built their algorithm to work in environments where the full game tree is too large to see, a setting known as model-free. In these scenarios, the AI cannot look ahead to see every possible future; it can only sample a few paths and learn from the results. To make this work without the learning process becoming unstable due to random fluctuations, the team introduced a variance-reduction technique. This acts like a stabilizer, helping the AI distinguish between a genuinely good strategy and a lucky break. They proved mathematically that this hierarchical method converges to an optimal strategy, meaning the AI will eventually learn to play perfectly, just like the older methods, but with the added ability to handle games that are far deeper and more complex.

When tested against the strongest existing algorithms in the field, HDCFR showed a clear advantage, particularly as the games became more difficult. The researchers evaluated their system on several versions of poker, ranging from a simple variant with a few cards to a complex version with a game tree containing over thirty trillion nodes. In the simpler games, the new method performed on par with the best existing tools. However, as the games grew longer and the decision horizons extended, the other methods began to falter, their performance becoming erratic or failing to improve. HDCFR, by contrast, continued to learn effectively, reaching a higher level of play. The team found that the hierarchical structure allowed the AI to maintain stability even when the game stretched out, a feat that previous deep learning methods could not achieve without becoming overwhelmed by the noise of the data.

A key finding of the study was the ability of the system to transfer knowledge from one task to another. The researchers trained the AI on a simpler version of the game and then asked it to apply what it had learned to a more complex version. They discovered that the low-level skills the AI had mastered—such as specific betting strategies—could be reused in the new, harder game. This transfer of skills significantly sped up the learning process. In some cases, the AI could focus entirely on learning the high-level management of these skills, skipping the need to relearn the basics. This suggests that the system is not just memorizing a specific game but is actually learning a flexible set of tools that can be adapted to new challenges. The researchers also observed that the AI learned to use these skills for extended periods, sometimes sticking with a single strategy for ten or more moves before switching, which mirrors the way human experts think in terms of phases rather than isolated actions.

The study also included a detailed look at what happens when certain parts of the system are removed. When the researchers took away the mechanism that allows the AI to extend skills over time, the system struggled to converge, much like the older methods. Similarly, when they removed the variance-reduction stabilizer, the learning performance dropped significantly, especially in the longer games. These tests confirmed that both the hierarchical structure and the noise-reduction techniques are essential for the system to work in deep, complex environments. The researchers noted that while the system requires substantial computing power to train, taking about a week on a standard server for the largest games, the results demonstrate a viable path forward for artificial intelligence in games with massive state spaces.

Ultimately, this work represents a shift in how machines approach complex decision-making under uncertainty. By organizing learning into a hierarchy of skills and managers, the researchers have created a system that can navigate the vast, hidden landscapes of imperfect information games more effectively than ever before. The findings suggest that for AI to master the most complex strategic challenges, it may need to stop trying to calculate every possibility and start learning to think in terms of structured, reusable skills. This approach not only improves performance in games but offers a blueprint for how intelligent agents might learn to operate in the real world, where information is often incomplete and the future is too vast to map out in full detail.

Technical Summary: Hierarchical Deep Counterfactual Regret Minimization (HDCFR)

Problem Statement

Imperfect Information Games (IIGs), such as poker, model decision-making under uncertainty where agents lack complete state information. While Counterfactual Regret Minimization (CFR) is a dominant algorithm for solving IIGs, standard tabular CFR requires traversing the entire game tree in every iteration, rendering it infeasible for games with extensive state spaces and deep decision horizons. Deep learning extensions (Deep CFR) have improved scalability but often rely on explicit game models for backtracking or suffer from high variance in model-free settings (where only outcome sampling is possible). Furthermore, existing deep methods typically learn flat strategies, lacking the ability to incorporate domain-specific skills or hierarchical decision-making structures that mirror human-like planning and facilitate knowledge transfer between similar tasks.

Methodology

The paper proposes Hierarchical Deep Counterfactual Regret Minimization (HDCFR), the first hierarchical extension of Deep CFR designed for model-free, large-scale IIGs. The methodology is developed in three progressive stages:

1. Theoretical Foundation: Hierarchical CFR (HCFR)

The authors extend the standard IIG definition to include a hierarchical strategy. An agent's decision at each step consists of a hierarchical action $(z_t, a_t)$ , comprising an option (skill) $z_t$ and a primitive action $a_t$ .

Strategy Decomposition: The strategy $\sigma_i$ is factored into a high-level policy $\sigma^H_i(z|I)$ (selecting options) and a low-level policy $\sigma^L_i(a|I, z)$ (executing actions within an option).
Regret Decomposition: Instead of minimizing a single global regret, HCFR minimizes the sum of high-level counterfactual regrets ( $R^{H}$ ) and low-level counterfactual regrets ( $R^{L}$ ).
Convergence: The authors prove that minimizing these decomposed regrets independently leads to a Nash Equilibrium (NE) with the same convergence rate ( $O(T^{-0.5})$ ) as standard tabular CFR.

2. Model-Free Extension: Low-Variance Monte Carlo Sampling

To handle deep game trees where full traversal is impossible, the authors adapt HCFR to a model-free Outcome Sampling (OS) setting.

Unbiased Estimators: They derive unbiased Monte Carlo estimators for the hierarchical counterfactual regrets.
Variance Reduction: Recognizing that long-horizon sampling introduces high variance, they introduce a baseline function $b_t$ . Theoretical analysis (Theorem 5) demonstrates that setting the baseline equal to the expected value of the state minimizes the variance of the regret estimators. This is critical for stabilizing learning in deep games.

3. Deep Approximation: HDCFR

Finally, the tabular functions are approximated using Neural Networks (NNs) to handle infinite state spaces.

Network Architecture: The system trains three types of networks:
1. Regret Networks: Approximate the cumulative counterfactual regrets ( $R^H, R^L$ ).
2. Strategy Networks: Approximate the average strategies ( $\sigma^H, \sigma^L$ ).
3. Baseline Network: Approximates the value function for variance reduction.
Training Objectives: The networks are trained to minimize objectives that match the tabular targets under exact fitting. Specifically, regret networks minimize the squared error between predicted and sampled immediate regrets, while strategy networks minimize the error between predicted and sampled average strategies.
One-Step Option Framework: The high-level policy utilizes a Multi-Head Attention (MHA) mechanism to dynamically determine whether to continue the current option or switch to a new one, effectively learning temporal abstraction without explicit termination conditions.

Key Contributions

First Hierarchical CFR: The paper introduces the first hierarchical version of Deep CFR, establishing theoretical convergence guarantees for learning hierarchical strategies in IIGs.
Model-Free Variance Reduction: It proposes a sample-based, model-free extension of hierarchical CFR that includes unbiased Monte Carlo estimators and a theoretically grounded baseline function to control variance in long-horizon tasks.
Scalable Deep Learning Integration: HDCFR successfully integrates these theoretical components with neural networks, allowing for learning in extensive state spaces while preserving the convergence properties of the tabular setting.
Skill Transferability: The framework enables the use of pre-learned skills (options) from similar tasks, facilitating faster learning and transfer in new IIGs.

Experimental Results

The authors evaluated HDCFR on a suite of poker benchmarks, including standard Leduc Hold'em and Heads-Up Flop Hold'em (FHP), with variations increasing the decision horizon (stack size and number of raises).

Performance vs. State-of-the-Art: HDCFR was benchmarked against DREAM, OSSDCFR, NFSP, and ESCHER.
- In Leduc variants with extended horizons (Leduc 15, 20), HDCFR achieved significantly lower exploitability (closer to NE) compared to baselines. While DREAM struggled to converge in these deep-horizon settings, HDCFR maintained stability.
- In FHP benchmarks (game trees exceeding $10^{12}$ nodes), HDCFR demonstrated superior performance in head-to-head matchups, achieving positive average payoffs against DREAM, OSSDCFR, and NFSP.
Ablation Studies:
- Removing the Multi-Head Attention (MHA) component caused the agent to fail to converge in deep games, confirming the necessity of temporal abstraction.
- Removing the baseline function led to a significant performance drop due to high variance, validating the variance reduction mechanism.
- Increasing the exploration rate ( $\epsilon$ ) in the traverser's sampling strategy improved learning performance.
Skill Transfer: Experiments transferring skills from smaller Leduc games to Leduc 20 showed that pre-learned skills could accelerate convergence. Fixing these skills allowed the agent to focus on high-level strategy selection, while dynamically adjusting them allowed for further optimization. Analysis of skill-switch frequencies confirmed that the high-level policy learned to extend skills temporally (average duration ~10 steps) rather than switching at every primitive action.

Significance and Claims

The paper claims that HDCFR provides a novel framework for learning in competitive multi-agent systems by amalgamating the option framework with Counterfactual Regret Minimization. Its primary significance lies in:

Scalability: It addresses the limitations of backtracking in deep game trees by utilizing model-free outcome sampling with variance reduction.
Human-Like Decision Making: By learning hierarchical strategies, the algorithm mirrors human decision-making processes that rely on skills and subgoals, offering better interpretability than flat policies.
Transfer Learning: It demonstrates that skills learned in one imperfect information game can be effectively transferred to similar, more complex tasks, reducing the data requirements for new domains.

The authors conclude that HDCFR outperforms leading model-free algorithms, particularly as the decision horizon increases, establishing a new baseline for solving complex, deep-horizon imperfect information games.