Résumé technique : Départs de jeu augmentés par les données pour accélérer l'exploration par auto-jeu dans les jeux à information imparfaite

Énoncé du problème

La recherche d'équilibres approximatifs dans des jeux compétitifs à grande échelle et à information imparfaite (par exemple, StarCraft, Dota, CounterStrike) reste computationnellement irréalisable pour la plupart des praticiens. Le goulot d'étranglement principal ne réside pas nécessairement dans la résolution des interactions stratégiques, mais dans la difficulté d'exploration inhérente aux environnements aux récompenses clairsemées, aux horizons de décision longs et aux dynamiques complexes d'états cachés. Les méthodes traditionnelles d'auto-jeu gaspillent souvent des ressources computationnelles en explorant à répétition de longues séquences d'actions coordonnées pour atteindre des sous-jeux stratégiquement pertinents, même si l'ensemble des choix stratégiques de haut niveau distincts est relativement restreint.

Bien que le clonage comportemental (BC) à partir de démonstrations humaines soit une approche courante pour amorcer la compétence, il nécessite d'importantes trajectoires état-action pour apprendre les compétences nécessaires. De plus, les benchmarks existants pour les jeux à information imparfaite manquent souvent des défis d'exploration (récompenses clairsemées, horizons longs) présents dans les domaines réels, ce qui rend difficile l'évaluation des méthodes conçues pour accélérer l'exploration.

Méthodologie : Départs de jeu augmentés par les données (DAGS)

Les auteurs proposent les Départs de jeu augmentés par les données (DAGS), une stratégie qui accélère l'exploration en ligne en initialisant les épisodes d'apprentissage par renforcement (RL) à des états intermédiaires échantillonnés à partir de données de jeu hors ligne, plutôt que de toujours redémarrer depuis l'état racine.

Mécanisme central

1. Jeu de données hors ligne : La méthode utilise un jeu de données hors ligne $D$ d'états globaux collectés à partir de parties jouées par des joueurs compétents (mais pas nécessairement optimaux). Ces états offrent une couverture large de situations de jeu stratégiquement distinctes.
2. Distribution de départ augmentée : DAGS définit une distribution de mélange $\tilde{d}^\beta_0 = (1 - \beta)d_0 + \beta d_D$, où $d_0$ est la distribution racine originale et $d_D$ est une distribution uniforme sur le jeu de données hors ligne. Le paramètre $\beta \in [0, 1]$ contrôle la fraction d'épisodes démarrant depuis des états hors ligne.
3. Intégration avec l'auto-jeu : Pendant l'entraînement, les épisodes sont échantillonnés à partir de $\tilde{d}^\beta_0$. Lorsqu'un épisode démarre depuis un état hors ligne, l'environnement continue d'évoluer selon les dynamiques de transition originales, préservant ainsi la structure d'information du jeu.
4. Atténuation du biais d'équilibre : Les auteurs identifient que la modification de la distribution des états de départ dans les jeux à information imparfaite peut déformer les croyances des agents sur les informations privées, conduisant à des équilibres biaisés. Pour atténuer cela, ils emploient un apprentissage multi-tâches avec un drapeau d'observation binaire ($f$) indiquant la source de l'épisode ($f=0$ pour un départ racine, $f=1$ pour un départ depuis le jeu de données). Cela permet à la politique d'apprendre une stratégie non biaisée pour le jeu original ($f=0$) tout en tirant parti de l'exploration augmentée des épisodes démarrés depuis le jeu de données ($f=1$) grâce à des paramètres de réseau partagés.

Construction du benchmark

Pour évaluer DAGS dans un cadre contrôlé avec une exploitabilité analytiquement traitable, les auteurs introduisent un nouvel ensemble d'environnements de benchmark basés sur des jeux OpenSpiel (Poker de Kuhn, Goofspiel). Ces benchmarks appliquent deux transformations :

1. Transformation d'abandon (FF) : Ajoute une action « abandon » strictement dominée à chaque nœud de décision pour modéliser l'échec à exécuter des tâches de contrôle.
2. Transformation du jeu de contrôle : Remplace chaque décision par une tâche de navigation en grille multi-étapes. Les agents doivent naviguer dans une grille pour atteindre des « cases d'action » spécifiques dans un délai imparti. S'ils échouent à atteindre la case correcte, l'action d'abandon est déclenchée.
   Ces transformations augmentent considérablement l'horizon et l'espace d'états tout en permettant de réduire analytiquement les politiques au jeu de base pour un calcul exact de l'exploitabilité.

Contributions clés

1. Nouvelle suite de benchmarks : Les auteurs fournissent un ensemble de jeux à somme nulle à deux joueurs (2p0s) avec des horizons longs et des défis d'exploration (navigation en grille) où l'exploitabilité peut être calculée analytiquement. Cela répond à l'absence de benchmarks combinant complexité stratégique et évaluation traitable.
2. Convergence accélérée via DAGS : L'article démontre que DAGS permet aux algorithmes de gradient de politique régularisés (spécifiquement PPO-Uniform et PPO-EMAg) d'atteindre une exploitabilité plus faible dans des jeux présentant des défis d'exploration significativement plus grands sous des budgets computationnels fixes.
3. Identification et atténuation du biais d'équilibre : Le travail démontre que l'augmentation des distributions d'états de départ peut biaiser les équilibres appris dans les jeux à information imparfaite. Il propose une stratégie d'atténuation simple utilisant des drapeaux d'observation multi-tâches pour récupérer un jeu non biaisé.

Résultats expérimentaux

Les auteurs ont évalué DAGS sur le Poker de Kuhn, le Goofspiel à 4 cartes, et un jeu contre-exemple personnalisé conçu pour révéler le biais d'équilibre.

• Échelle d'exploration : Dans les variantes « Contrôle Voyage » (où les agents doivent naviguer dans des grilles pour exécuter des actions), l'auto-jeu standard ($\beta=0$) a échoué à découvrir comment naviguer vers des cases d'action spécifiques dans les délais impartis, entraînant une exploitabilité élevée (abandon effectif). DAGS ($\beta > 0$) a initialisé avec succès les épisodes à des états intermédiaires, permettant aux agents de se concentrer sur la résolution des interactions stratégiques de haut niveau. Dans le Goofspiel avec une difficulté élevée (Voyage 20), l'auto-jeu standard a plafonné à une exploitabilité élevée, tandis que DAGS a continué à converger vers une faible exploitabilité.
• Biais d'équilibre : Dans le jeu contre-exemple, définir $\beta=1$ (toujours démarrer depuis des données hors ligne) a conduit les agents à converger vers un équilibre biaisé avec une exploitabilité élevée en raison de croyances déformées sur les informations cachées.
• Efficacité de l'atténuation : L'utilisation d'un $\beta$ intermédiaire (par exemple 0,5) combiné au drapeau d'observation identifiant la tâche a permis d'atténuer avec succès le biais. La branche $f=0$ a appris une politique non biaisée pour le jeu original, tandis que la branche $f=1$ a facilité l'exploration. Cette approche a permis une exploration efficace sans sacrifier la justesse de l'équilibre.

Importance et affirmations

L'article affirme que DAGS offre une voie pratique pour résoudre les jeux à grande échelle à information imparfaite en découplant le coût de l'exploration de longues séquences de contrôle du coût de l'apprentissage des interactions stratégiques. En exploitant les données hors ligne pour la couverture des états plutôt que pour l'initialisation de la politique, DAGS nécessite moins de données que le clonage comportemental et reste viable même lorsque les démonstrations sont incomplètes ou sous-optimales.

Les auteurs soulignent que leur contribution est modeste en termes de portée concernant les algorithmes spécifiques utilisés (PPO régularisé) mais significative quant à l'insight méthodologique concernant les réinitialisations d'états dans les contextes multi-agents. Ils mettent en évidence que, bien que la modification des distributions de départ soit une technique connue en RL mono-agent, son application aux jeux à information imparfaite introduit des risques uniques de biais d'équilibre qui doivent être traités. L'atténuation proposée via l'apprentissage multi-tâches fournit une solution robuste pour ce défi spécifique.

Le travail conclut que, bien que leurs benchmarks actuels utilisent des mécanismes simples pour préserver la traitabilité analytique, les principes de DAGS devraient être évolutifs vers des domaines complexes (par exemple, jeux de combat, FPS) où les démonstrations sont rares et où le clonage comportemental est inefficace en termes de données. Les auteurs positionnent DAGS comme une direction prometteuse pour les travaux futurs visant à appliquer ces techniques à des jeux où l'exploitabilité exacte n'est pas traitable.