Résumé technique : Parallélisation de la minimisation du regret contrefactuel

Énoncé du problème

Bien que la parallélisation ait été un pilier de l'intelligence artificielle, réduisant considérablement les temps d'entraînement pour les grands modèles, son application à la résolution computationnelle de jeux reste relativement peu explorée. Malgré des succès marquants dans la résolution de grands jeux à information imparfaite (par exemple, Cepheus, Libratus, Pluribus) reposant sur une forme de parallélisme, les mécanismes spécifiques de la parallélisation des algorithmes de minimisation du regret contrefactuel (CFR) n'ont pas été généralisés. Les tentatives existantes, telles que celles de Reis et Rudolf, souffrent souvent de problèmes de reproductibilité, nécessitent un flux de contrôle complexe par thread, ou aboutissent à une complexité de travail quadratique sous-optimale. De plus, les approches antérieures spécifiques à un domaine (par exemple, dans Cepheus) manquent de généralité. Les auteurs identifient le besoin d'un cadre généralisé et indépendant du domaine capable d'accélérer le CFR et ses variantes tabulaires sans sacrifier les propriétés algorithmiques qui les rendent efficaces.

Méthodologie

Les auteurs proposent un cadre de parallélisation généralisé qui reformule la version en forme séquentielle du CFR comme une série d'opérations d'algèbre linéaire. Cette transformation permet d'appliquer des techniques standard et hautement optimisées pour la parallélisation de l'algèbre linéaire (spécifiquement sur les GPU) à la résolution de jeux.

Approche technique principale

1. Reformulation du CFR en algèbre linéaire :
   L'article convertit les étapes de parcours d'arbre inhérentes au CFR (de haut en bas pour les mises à jour de stratégie, de bas en haut pour l'observation de l'utilité) en opérations matrice-vecteur. Cela est réalisé à l'aide de matrices logiques (matrices dont les entrées appartiennent à $\{0, 1\}$) pour concilier différentes représentations de données :

   • Représentation séquentielle vs représentation par nœud : La matrice logique $A \in \mathbb{R}^{P \times \Sigma}$ convertit entre les vecteurs par nœud ($\mathbb{R}^P$) et les vecteurs par séquence ($\mathbb{R}^\Sigma$).
   • Représentation comportementale : La matrice logique $B$ gère la conversion vers la représentation comportementale ($\mathbb{R}^{\Sigma^+}$), qui exclut la séquence vide.
   • Agrégation des actions : La matrice logique $C$ agrège les valeurs à travers les actions disponibles aux points de décision, permettant la normalisation L1 et les calculs d'espérance via la multiplication matricielle.

2. Parallélisation du parcours d'arbre :
   Au lieu d'un parcours d'arbre récursif, l'algorithme décompose le processus de décision séquentiel en forme d'arbre (TFSDP) en structures de niveaux. Les matrices d'adjacence $L^{(d)}$ représentent les arêtes à chaque profondeur $d$.

   • Le parcours de haut en bas (pour la propagation de la stratégie) est effectué en appliquant séquentiellement $L^{(1)}, L^{(2)}, \dots, L^{(k)}$.
   • Le parcours de bas en haut (pour l'accumulation d'utilité) est effectué en appliquant ces matrices dans l'ordre inverse.
   • Ces opérations sont implémentées à l'aide de la multiplication matrice-vecteur à lignes compressées (CSR), qui est hautement efficace sur le matériel parallèle.

3. Adaptation algorithmique :
   Le cadre est conçu pour être modulaire. Les opérations parallélisées de base (NEXTSTRATEGY et OBSERVEUTILITY) sont définies, et des variantes spécifiques du CFR sont implémentées en ajoutant des opérations simples à ces fonctions de base :

   • CFR+ : Ajoute une opération de plancher aux regrets.
   • CFR à remises (DCFR) : Applique des facteurs d'échelle dépendants du temps aux regrets positifs et négatifs.
   • CFR prédictif (PCFR) : Intègre un vecteur de prédiction pour les regrets instantanés.

Contributions clés

• Cadre généralisé : L'article présente un cadre indépendant du domaine qui traite le CFR comme de l'algèbre linéaire, le rendant applicable à toute variante tabulaire du CFR (CFR, CFR+, DCFR, PCFR, PCFR+).
• Analyse théorique : En utilisant le modèle travail-profondeur, les auteurs prouvent que l'algorithme parallélisé maintient la même complexité de travail totale ($W = \Theta(|P|)$) que le CFR séquentiel en forme séquentielle, garantissant aucune perte d'efficacité en l'absence de parallélisme. La profondeur est montrée comme étant $D = \Theta(k \log B)$, où $k$ est la hauteur de l'arbre et $B$ le facteur de branchement.
• Implémentation open source : Contrairement aux tentatives antérieures sur GPU, ce travail fournit une implémentation open source compatible avec la bibliothèque OpenSpiel, facilitant la reproductibilité et l'intégration.
• Évolutivité : L'approche divise efficacement le jeu à chaque profondeur plutôt que seulement aux limites des sous-jeux, générant potentiellement un parallélisme supérieur par rapport aux architectures précédentes comme Cepheus.

Résultats expérimentaux

Les auteurs ont évalué leur implémentation accélérée par GPU par rapport aux implémentations d'OpenSpiel de Google DeepMind (Python et C++) s'exécutant sur CPU à travers sept jeux de référence de tailles variées (de Kuhn poker avec 58 nœuds à Large Battleship avec $5.2 \times 10^7$ nœuds).

• Petits jeux : Pour les petits jeux (par exemple, Kuhn poker, Leduc poker), la surcharge du GPU entraîne un ralentissement par rapport aux implémentations CPU.
• Grands jeux : À mesure que la taille du jeu augmente, l'implémentation parallélisée surpasse considérablement les références CPU.
  • Pour Small Battleship, l'accélération est d'environ $2.1 \times 10^2$ fois plus rapide que l'implémentation C++ d'OpenSpiel.
  • Pour Medium Battleship, l'accélération atteint $1.2 \times 10^3$.
  • Pour Large Battleship, l'accélération est de $4.1 \times 10^3$.
  • Dans l'ensemble, l'implémentation GPU est jusqu'à 18 889 fois plus rapide que l'implémentation Python d'OpenSpiel et 3 413 fois plus rapide que son implémentation C++.
• Convergence : Les expériences démontrent que l'implémentation parallélisée atteint la même réduction d'exploitabilité sur le temps réel, mais en une fraction du temps, l'accélération devenant plus prononcée à mesure que la taille du jeu augmente.

Importance et affirmations

L'article affirme que, bien que cette technique de parallélisation n'augmente pas nécessairement la taille du jeu pouvant être résolu (en termes de capacité mémoire), elle réduit considérablement le temps nécessaire pour trouver une solution optimale.

• Accélération de la recherche : La proposition de valeur principale est de permettre aux chercheurs de tester des hypothèses, de nouvelles variantes du CFR et des régimes d'hyperparamètres avec des délais de traitement beaucoup plus rapides.
• Paramètres répétitifs : Le cadre est particulièrement utile pour les jeux joués dans des contextes répétés (par exemple, le poker avec des tailles de stack variables) où les arbres de jeu individuels sont similaires, permettant une résolution rapide.
• Compatibilité : Les auteurs soulignent que leur méthode conserve une compatibilité totale avec OpenSpiel, permettant de l'utiliser comme un accélérateur plug-and-play pour la recherche existante en théorie des jeux sans nécessiter de réécriture des définitions de jeu.
• Modestie : Les auteurs déclarent explicitement que leur contribution n'est pas exclusive avec les architectures précédentes (comme la division de sous-jeux de Cepheus) ; plutôt, leur technique peut être augmentée par de telles architectures pour un parallélisme supplémentaire. Ils reconnaissent également que, bien qu'ils comparent le GPU au CPU, les résultats mettent en évidence le potentiel du parallélisme même dans des cas d'utilisation courants, bien qu'ils ne prétendent pas résoudre des jeux qui étaient auparavant insolubles en raison de contraintes de mémoire.