Résumé Technique : EMAgnet

Problématique

Les progrès récents dans la résolution de jeux à somme nulle à information imparfaite (IIG) à deux joueurs ont démontré que les méthodes de gradient de politique régularisées, telles que l'Optimisation de Politique Proximale (PPO), peuvent égaler ou surpasser les algorithmes spécialisés en théorie des jeux lorsqu'elles sont utilisées en auto-jeu (self-play). Une décision de conception critique dans ce cadre est le choix de la cible de régularisation. La distribution uniforme est apparue comme une cible standard, implémentée via un bonus d'entropie. Cependant, la cible uniforme est stratégiquement agnostique ; elle régularise la politique de manière égale vers toutes les actions, indépendamment de leur viabilité.

Dans les jeux possédant de grands espaces stratégiques contenant de nombreuses stratégies strictement dominées (options sous-optimales), la cible uniforme gaspille le budget de régularisation sur des stratégies non pertinentes. Cette limitation devient de plus en plus conséquente à mesure que la complexité du jeu croît et que la fraction de stratégies stratégiquement pertinentes diminue. De plus, les approches existantes utilisant une régularisation uniforme avec recul (annealed) font face à un dilemme : une régularisation forte au début force la politique à explorer des stratégies dominées, tandis qu'une régularisation faible en fin de parcours ne fournit pas une pression suffisante pour encourager le mélange stratégique, menant souvent à une convergence sur des stratégies pures plutôt que sur des équilibres de Nash.

Méthodologie

Les auteurs introduisent EMAgnet, une méthode qui étend le concept de cible de régularisation par « aimant mobile » (moving magnet) des contextes tabulaires au renforcement profond (deep RL). Au lieu de régulariser vers une distribution uniforme fixe, EMAgnet régularise vers une Moyenne Mobile Exponentielle (EMA) des propres paramètres du réseau de la politique.

Mécanisme Central

La méthode s'appuie sur PPO en auto-jeu symétrique. L'objectif standard de PPO est augmenté d'un terme de divergence de Kullback-Leibler (KL) qui attire les paramètres de la politique actuelle ($\theta$) vers une politique « aimant » ($\theta_{mag}$) :

$$L_{PPO-EMAg}(\theta) = L_{PPO}(\theta) + \lambda_{KL} \mathbb{E}_{z \sim \mathcal{T}} \left[ D_{KL}(\pi_{\theta_{mag}}(\cdot | z) \parallel \pi_{\theta}(\cdot | z)) \right]$$

Les paramètres de l'aimant sont mis à jour après chaque étape PPO en utilisant une moyenne arithmétique dans l'espace des paramètres :
$$\theta_{mag} \leftarrow (1 - \tau) \theta_{mag} + \tau \theta$$
où $\tau \in (0, 1]$ est le pas de progression. L'aimant est initialisé avec les mêmes poids aléatoires que la politique.

Propriétés Adaptatives

L'innovation clé réside dans la nature adaptative de la cible :

1. Oublier les mauvaises stratégies : À mesure que la politique apprend à éviter les stratégies strictement dominées, l'aimant EMA cesse progressivement de régulariser vers ces dernières car les poids de la politique ne soutiennent plus ces actions.
2. Se souvenir des bonnes stratégies : L'EMA accumule naturellement un mélange lissé sur les stratégies rencontrées lors des cycles d'auto-jeu. Cela encourage la politique à maintenir une couverture sur les options stratégiquement pertinentes.
3. Force Constante : Contrairement à la régularisation uniforme avec recul, la force de régularisation KL ($\lambda_{KL}$) reste constante, mais la cible évolue. Cela évite le « dilemme » où une régularisation forte force l'exploration de mauvaises stratégies ou une régularisation faible échoue à empêcher l'effondrement vers des stratégies pures.

Contributions Clés

1. Extension Algorithmique : Le papier étend le concept tabulaire de l'aimant mobile (précédemment exploré par Sokota et al.) au deep RL en implémentant une EMA de l'espace des paramètres des poids de la politique comme cible de régularisation.
2. Régularisation Adaptative : La méthode fournit une cible de régularisation adaptative qui évolue avec la stratégie améliorée de l'agent, se distinguant des cibles fixes comme la distribution uniforme.
3. Évaluation Empirique : Les auteurs évaluent PPO-EMAg par rapport à PPO en auto-jeu avec une régularisation par aimant uniforme (utilisant des calendriers de recul linéaire et de loi de puissance) à travers trois catégories de jeux :
   • Benchmarks standards (Biased RPS, Goofspiel-4, Kuhn Poker).
   • Benchmarks modifiés avec une action unique de « forfait » (forfeit) strictement dominée (variantes FF).
   • Benchmarks modifiés où la vaste majorité de l'espace stratégique est dominée via des tâches de navigation en gridworld (variantes Control).

Résultats

L'évaluation démontre que PPO-EMAg atteint une exploitabilité plus faible que les bases uniformes dans les environnements contenant des stratégies strictement dominées, tout en restant compétitif dans les benchmarks standards.

• Jeux Standards : Dans Biased RPS, Goofspiel-4 et Kuhn Poker, PPO-EMAg est compétitif avec les bases, la politique de l'aimant EMA atteignant souvent l'exploitabilité finale la plus basse.
• Jeux de Forfait (FF) : Dans les jeux augmentés d'une action de forfait strictement dominée, PPO-EMAg surpasse significativement les bases uniformes. L'aimant uniforme continue de régulariser vers l'action de forfait tout au long de l'entraînement, tandis que l'aimant EMA s'adapte pour réduire la régularisation vers celle-ci à mesure que la politique apprend à l'éviter.
• Jeux de Contrôle (Control) : Dans les environnements où la plupart des stratégies sont strictement dominées (en raison d'échecs de navigation), PPO-EMAg montre une performance supérieure et une convergence nettement plus rapide.
  • Dans Control Biased RPS, le recul linéaire uniforme échoue à apprendre pendant environ 7 millions d'étapes avant de chuter tardivement dans l'entraînement, tandis que PPO-EMAg converge en 2 millions d'étapes.
  • Dans Control Goofspiel, le recul linéaire uniforme s'améliore à peine après 6 millions d'étapes, alors que PPO-EMAg atteint une faible exploitabilité bien plus tôt.
• Analyse de Trajectoire : Les visualisations des trajectoires de politique dans le simplexe stratégique révèlent que le recul uniforme provoque des blocages sur des stratégies dominées tôt dans le processus ou un effondrement vers des stratégies pures plus tard. PPO-EMAg évite cela en réduisant progressivement la masse sur les actions dominées tout en maintenant la pression de mélange, permettant à la politique de cycler près de l'équilibre de Nash.

Signification et Revendications

Le papier affirme que EMAgnet offre un mécanisme simple mais efficace pour adapter les cibles de régularisation à l'évolution de la stratégie d'un agent dans des jeux de grande taille. En régularisant vers une EMA dans l'espace des paramètres des propres poids de la politique, la méthode évite les pièges de la régularisation uniforme dans les jeux comportant un grand nombre de stratégies strictement dominées.

Les auteurs postulent qu'à mesure que les jeux gagnent en complexité, la fraction de l'espace stratégique qui est pertinente tend à diminuer. Dans de tels scénarios, allouer un budget de régularisation à des options sous-optimales engendre un coût croissant. EMAgnet répond à cela en « oubliant » les mauvaises stratégies tout en « se souvenant » des bonnes, ne nécessant qu'une seule mise à jour EMA par étape d'entraînement au-delà de la boucle PPO standard. Le papier conclut que si PPO-EMAg est compétitif sur les benchmarks standards, son avantage principal réside dans les jeux à haute densité de stratégies dominées, où il permet une convergence plus rapide et une exploitabilité finale plus faible par rapport à la régularisation uniforme avec recul.