💻 computer science

Hierarchical Deep Counterfactual Regret Minimization

Cet article introduit l'HDCFR (Hierarchical Deep Counterfactual Regret Minimization), un nouvel algorithme qui intègre l'apprentissage de stratégies hiérarchiques basées sur des compétences avec le Deep CFR pour améliorer l'efficacité de la résolution de jeux à information imparfaite à grande échelle en permettant l'utilisation d'expertises prédéfinies et de compétences transférables.

Auteurs originaux : Jiayu Chen, Xudong Wu, Zhekai Wang, Vaneet Aggarwal

Publié 2026-10-05

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Jiayu Chen, Xudong Wu, Zhekai Wang, Vaneet Aggarwal

Article original sous licence CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Dans le monde de l'intelligence artificielle, certains des défis les plus difficiles proviennent de jeux où les joueurs ne peuvent pas voir l'ensemble du plateau. Pensez à une table de poker : vous connaissez vos propres cartes et les cartes sur la table, mais vous n'avez aucune idée de ce que votre adversaire détient. Ce manque d'information complète crée un paysage d'incertitude où chaque décision doit être pesée face aux possibilités cachées. Pendant des décennies, des chercheurs ont utilisé une méthode appelée minimisation du regret contre-factuel pour apprendre aux ordinateurs à jouer à ces jeux. La logique est simple : après la fin d'une partie, l'ordinateur examine chaque choix qu'il a fait et se demande : « Et si j'avais fait autre chose ? » Si changer ce choix avait conduit à un meilleur résultat, l'ordinateur ressent un sentiment de « regret ». Au fil de millions de parties, il apprend à minimiser ce regret, finissant par établir une stratégie si forte qu'aucun adversaire ne peut la battre de manière constante. Cette approche a produit certaines des IA de poker les plus redoutables de l'histoire.

Cependant, un problème majeur surgit lorsque le jeu devient trop complexe. Dans les variantes simples du poker, l'ordinateur peut cartographier chaque chemin possible que le jeu pourrait prendre. Mais dans des versions plus complexes avec des séquences de jeu plus longues, le nombre de chemins possibles explose pour atteindre les trillions. La méthode traditionnelle, qui nécessite de vérifier chaque chemin pour calculer le regret, devient impossible car l'ordinateur devrait traiter plus de données qu'il n'en existe dans l'univers. Pour résoudre cela, les chercheurs se sont tournés vers l'apprentissage profond (deep learning), utilisant des réseaux de neurones pour deviner les bons mouvements sans vérifier toutes les possibilités. Pourtant, même ces systèmes avancés peinent lorsque le jeu s'étire sur un long horizon, se perdant souvent dans le volume massif de bruit aléatoire généré par l'échantillonnage de quelques sentiers seulement. Ils manquent d'un moyen d'organiser leur pensée en blocs gérables, tout comme un humain qui essaierait de se souvenir de mille étapes individuelles au lieu de reconnaître quelques routines familières.

Une équipe de chercheurs de l'Université de Hong Kong, de l'Université de Pékin et de l'Université Purdue a introduit une nouvelle approche appelée Minimisation du Regret Contre-factuel Profond Hiérarchique, ou HDCFR, conçue pour surmonter ces limites. Leurs travaux, publiés dans un article de recherche, proposent qu'au lieu de forcer l'IA à apprendre chaque petit mouvement à partir de zéro, ils devraient lui apprendre à apprendre des « compétences » d'abord. Dans ce système, l'IA apprend des composants de bas niveau qui agissent comme des compétences spécifiques pour résoudre de petites parties du jeu, telles qu'un schéma de mise particulier ou une manœuvre défensive. Un composant de haut niveau agit ensuite comme un gestionnaire, décidant quelle compétence utiliser à un moment donné et quand passer de l'une à l'autre. Cette structure imite la façon dont les humains jouent : nous ne pensons pas à chaque mouvement musculaire lorsque nous conduisons une voiture ; nous pensons en termes de « tourner à gauche », « changer de voie » ou « s'arrêter », et nous passons entre ces objectifs de haut niveau à mesure que la situation change.

Les chercheurs ont construit leur algorithme pour fonctionner dans des environnements où l'arbre complet du jeu est trop vaste pour être vu, un cadre dit « sans modèle » (model-free). Dans ces scénarios, l'IA ne peut pas regarder vers l'avant pour voir tous les futurs possibles ; elle ne peut qu'échantillonner quelques chemins et apprendre de leurs résultats. Pour que cela fonctionne sans que le processus d'apprentissage ne devienne instable à cause des fluctuations aléatoires, l'équipe a introduit une technique de réduction de la variance. Cela agit comme un stabilisateur, aidant l'IA à distinguer une stratégie réellement bonne d'un coup de chance. Ils ont prouvé mathématiquement que cette méthode hiérarchique converge vers une stratégie optimale, ce qui signifie que l'IA finira par apprendre à jouer parfaitement, tout comme les anciennes méthodes, mais avec la capacité supplémentaire de gérer des jeux beaucoup plus profonds et complexes.

Lorsqu'elle a été testée contre les algorithmes les plus puissants du domaine, l'HDCFR a montré un avantage clair, particulièrement à mesure que les jeux devenaient plus difficiles. Les chercheurs ont évalué leur système sur plusieurs versions de poker, allant d'une variante simple avec quelques cartes à une version complexe contenant un arbre de jeu de plus de trente mille milliards de nœuds. Dans les jeux plus simples, la nouvelle méthode était au niveau des meilleurs outils existants. Cependant, à mesure que les jeux s'allongeaient et que les horizons de décision s'étendaient, les autres méthodes commençaient à faiblir, leur performance devenant erratique ou cessant de s'améliorer. L'HDCFR, en revanche, a continué à apprendre efficacement, atteignant un niveau de jeu supérieur. L'équipe a constaté que la structure hiérarchique permettait à l'IA de maintenir la stabilité même lorsque le jeu s'étirait, un exploit que les méthodes d'apprentissage profond précédentes ne pouvaient atteindre sans être submergées par le bruit des données.

Une découverte clé de l'étude a été la capacité du système à transférer des connaissances d'une tâche à une autre. Les chercheurs ont entraîné l'IA sur une version plus simple du jeu, puis lui ont demandé d'appliquer ce qu'elle avait appris à une version plus complexe. Ils ont découvert que les compétences de bas niveau maîtrisées par l'IA — telles que des stratégies de mise spécifiques — pouvaient être réutilisées dans le nouveau jeu, plus difficile. Ce transfert de compétences a considérablement accéléré le processus d'apprentissage. Dans certains cas, l'IA pouvait se concentrer entièrement sur l'apprentissage de la gestion de haut niveau de ces compétences, évitant ainsi de devoir réapprendre les bases. Cela suggère que le système ne fait pas que mémoriser un jeu spécifique, mais apprend réellement un ensemble flexible d'outils qui peuvent être adaptés à de nouveaux défis. Les chercheurs ont également observé que l'IA apprenait à utiliser ces compétences pendant des périodes prolongées, restant parfois sur une seule stratégie pendant dix mouvements ou plus avant de changer, ce qui reflète la façon dont les experts humains pensent en termes de phases plutôt qu'en actions isolées.

L'étude comprenait également un examen détaillé de ce qui se passe lorsque certaines parties du système sont retirées. Lorsque les chercheurs ont supprimé le mécanisme permettant à l'IA d'étendre les compétences dans le temps, le système a eu du mal à converger, tout comme les anciennes méthodes. De même, lorsqu'ils ont retiré le stabilisateur de réduction de la variance, les performances d'apprentissage ont chuté de manière significative, surtout dans les jeux longs. Ces tests ont confirmé que la structure hiérarchique et les techniques de réduction du bruit sont essentielles au fonctionnement du système dans des environnements profonds et complexes. Les chercheurs ont noté que, bien que le système nécessite une puissance de calcul substantielle pour l'entraînement, prenant environ une semaine sur un serveur standard pour les jeux les plus vastes, les résultats démontrent une voie viable pour l'intelligence artificielle dans les jeux dotés d'espaces d'états massifs.

En fin de compte, ce travail représente un changement dans la manière dont les machines abordent la prise de décision complexe sous incertitude. En organisant l'apprentissage en une hiérarchie de compétences et de gestionnaires, les chercheurs ont créé un système capable de naviguer dans les vastes paysages cachés des jeux à information imparfaite plus efficacement que jamais. Les conclusions suggèrent que pour que l'IA maîtrise les défis stratégiques les plus complexes, elle devra peut-être cesser de tenter de calculer chaque possibilité et commencer à apprendre à penser en termes de compétences structurées et réutilisables. Cette approche améliore non seulement les performances dans les jeux, mais offre également un modèle de la façon dont les agents intelligents pourraient apprendre à opérer dans le monde réel, où l'information est souvent incomplète et où le futur est trop vaste pour être cartographié dans ses moindres détails.

Résumé Technique : HDCFR (Hierarchical Deep Counterfactual Regret Minimization)

Énoncé du Problème

Les jeux à information imparfaite (IIG - Imperfect Information Games), tels que le poker, modélisent la prise de décision en situation d'incertitude où les agents manquent d'informations complètes sur l'état. Bien que le Counterfactual Regret Minimization (CFR) soit un algorithme dominant pour résoudre les IIG, le CFR tabulaire standard nécessite de parcourir l'intégralité de l'arbre de jeu à chaque itération, ce qui s'avère irréalisable pour les jeux possédant des espaces d'états étendus et des horizons de décision profonds. Les extensions de Deep Learning (Deep CFR) ont amélioré la scalabilité, mais reposent souvent sur des modèles de jeu explicites pour le backtracking ou souffrent d'une variance élevée dans les contextes sans modèle (où seul l'échantillonnage des résultats est possible). De plus, les méthodes de Deep Learning existantes apprennent généralement des stratégies plates, manquant de la capacité d'incorporer des compétences spécifiques au domaine ou des structures de prise de décision hiérarchiques qui reflètent la planification humaine et facilitent le transfert de connaissances entre des tâches similaires.

Méthodologie

Le papier propose l'HDCFR (Hierarchical Deep Counterfactual Regret Minimization), la première extension hiérarchique de Deep CFR conçue pour les IIG à grande échelle et sans modèle. La méthodologie est développée en trois étapes progressives :

1. Fondement Théorique : HCFR (Hierarchical CFR)

Les auteurs étendent la définition standard des IIG pour inclure une stratégie hiérarchique. La décision d'un agent à chaque étape consiste en une action hiérarchique $(z_t, a_t)$ , composée d'une option (compétence/skill) $z_t$ et d'une action primitive $a_t$ .

Décomposition de la stratégie : La stratégie $\sigma_i$ est décomposée en une politique de haut niveau $\sigma^H_i(z|I)$ (sélection des options) et une politique de bas niveau $\sigma^L_i(a|I, z)$ (exécution des actions au sein d'une option).
Décomposition du regret : Au lieu de minimiser un regret global unique, le HCFR minimise la somme des regrets contrefactuels de haut niveau ( $R^{H}$ ) et de bas niveau ( $R^{L}$ ).
Convergence : Les auteurs prouvent que la minimisation indépendante de ces regrets décomposés mène à un Équilibre de Nash (NE) avec le même taux de convergence ( $O(T^{-0.5})$ ) que le CFR tabulaire standard.

2. Extension Sans Modèle (Model-Free) : Échantillonnage de Monte Carlo à Faible Variance

Pour gérer les arbres de jeu profonds où le parcours complet est impossible, les auteurs adaptent le HCFR à un contexte d'échantillonnage de résultats (Outcome Sampling - OS) sans modèle.

Estimateurs non biaisés : Ils dérivent des estimateurs de Monte Carlo non biaisés pour les regrets contrefactuels hiérarchiques.
Réduction de la variance : Reconnaissant que l'échantillonnage à long horizon introduit une variance élevée, ils introduisent une fonction de base (baseline function) $b_t$ . L'analyse théorique (Théorème 5) démontre que fixer la base égale à la valeur attendue de l'état minimise la variance des estimateurs de regret. Ceci est crucial pour stabiliser l'apprentissage dans les jeux profonds.

3. Approximation Profonde : HDCFR

Enfin, les fonctions tabulaires sont approximées par des réseaux de neurones (NN) pour gérer les espaces d'états infinis.

Architecture de Réseau : Le système entraîne trois types de réseaux :
1. Réseaux de Regret : Approximant les regrets contrefactuels cumulés ( $R^H, R^L$ ).
2. Réseaux de Stratégie : Approximant les stratégies moyennes ( $\sigma^H, \sigma^L$ ).
3. Réseau de Base (Baseline) : Approximant la fonction de valeur pour la réduction de la variance.
Objectifs d'Entraînement : Les réseaux sont entraînés pour minimiser des objectifs qui correspondent aux cibles tabulaires sous ajustement exact. Plus précisément, les réseaux de regret minimisent l'erreur quadratique entre les regrets immédiats prédits et échantillonnés, tandis que les réseaux de stratégie minimisent l'erreur entre les stratégies moyennes prédites et échantillonnées.
Cadre d'Option à Étape Unique (One-Step Option Framework) : La politique de haut niveau utilise un mécanisme d'Attention Multi-Têtes (MHA) pour déterminer dynamiquement si l'on continue l'option actuelle ou si l'on passe à une nouvelle, apprenant ainsi efficacement l'abstraction temporelle sans conditions de terminaison explicites.

Principales Contributions

Premier CFR Hiérarchique : Le papier introduit la première version hiérarchique de Deep CFR, établissant des garanties de convergence théorique pour l'apprentissage de stratégies hiérarchiques dans les IIG.
Réduction de la Variance sans Modèle : Il propose une extension de l'HCFR basée sur l'échantillonnage, sans modèle, qui inclut des estimateurs de Monte Carlo non biaisés et une fonction de base théoriquement fondée pour contrôler la variance dans les tâches à long horizon.
Intégration de l'Apprentissage Profond Scalable : L'HDCFR intègre avec succès ces composants théoriques avec des réseaux de neurones, permettant l'apprentissage dans des espaces d'états étendus tout en préservant les propriétés de convergence du cadre tabulaire.
Transférabilité des Compétences : Le cadre permet l'utilisation de compétences pré-apprises (options) issues de tâches similaires, facilitant un apprentissage plus rapide et le transfert vers de nouveaux IIG.

Résultats Expérimentaux

Les auteurs ont évalué l'HDCFR sur une suite de benchmarks de poker, incluant le Leduc Hold'em standard et le Heads-Up Flop Hold'em (FHP), avec des variations augmentant l'horizon de décision (taille de pile et nombre de relances).

Performance par rapport à l'État de l'Art : L'HDCFR a été comparé à DREAM, OSSDCFR, NFSP et ESCHER.
- Dans les variantes de Leduc avec des horizons étendus (Leduc 15, 20), l'HDCFR a atteint une exploitabilité nettement plus faible (plus proche du NE) par rapport aux bases de référence. Alors que DREAM peinait à converger dans ces configurations à horizon profond, l'HDCFR a maintenu sa stabilité.
- Dans les benchmarks FHP (arbres de jeu dépassant $10^{12}$ nœuds), l'HDCFR a démontré une performance supérieure lors des confrontations directes, obtenant des gains moyens positifs contre DREAM, OSSDCFR et NFSP.
Études d'Ablation :
- La suppression du composant Attention Multi-Têtes (MHA) a empêché l'agent de converger dans les jeux profonds, confirmant la nécessité de l'abstraction temporelle.
- La suppression de la fonction de base a entraîné une chute significative des performances due à la variance élevée, validant le mécanisme de réduction de la variance.
- L'augmentation du taux d'exploration ( $\epsilon$ ) dans la stratégie d'échantillonnage du traversant a amélioré les performances d'apprentissage.
Transfert de Compétences : Les expériences de transfert de compétences de petits jeux Leduc vers Leduc 20 ont montré que les compétences pré-apprises pouvaient accélérer la convergence. Fixer ces compétences permettait à l'agent de se concentrer sur la sélection de stratégie de haut niveau, tandis qu'un ajustement dynamique permettait une optimisation supplémentaire. L'analyse de la fréquence de changement de compétence a confirmé que la politique de haut niveau a appris à étendre les compétences temporellement (durée moyenne ~10 étapes) plutôt que de changer à chaque action primitive.

Signification et Revendications

Le papier affirme que l'HDCFR fournit un nouveau cadre pour l'apprentissage dans les systèmes multi-agents compétitifs en amalgamant le cadre des options avec le Counterfactual Regret Minimization. Sa principale importance réside dans :

Scalabilité : Il répond aux limites du backtracking dans les arbres de jeu profonds en utilisant l'échantillonnage de résultats sans modèle avec réduction de la variance.
Prise de Décision Similaire à l'Humain : En apprenant des stratégies hiérarchiques, l'algorithme reflète les processus de décision humains qui reposent sur des compétences et des sous-objectifs, offrant une meilleure interprétabilité que les politiques plates.
Apprentissage par Transfert : Il démontre que les compétences apprises dans un jeu à information imparfaite peuvent être transférées efficacement vers des tâches similaires et plus complexes, réduisant ainsi les besoins en données pour de nouveaux domaines.

Les auteurs concluent que l'HDCFR surpasse les principaux algorithmes sans modèle, particulièrement lorsque l'horizon de décision augmente, établissant une nouvelle référence pour la résolution de jeux à information imparfaite complexes à horizon profond.