NashPG: A Policy Gradient Method with Iteratively Refined Regularization for Finding Nash Equilibria

1. Énoncé du problème

Le papier aborde le défi de la recherche d'équilibres de Nash (EN) dans les jeux à information imparfaite à deux joueurs et somme nulle (2p0s IIGs) en utilisant l'apprentissage par renforcement multi-agents (MARL).

• La difficulté centrale : Bien que l'apprentissage par renforcement profond (DRL) ait réussi dans les jeux à information parfaite, les 2p0s IIGs (comme le Poker) impliquent une observabilité partielle et des informations cachées.
• Limites des méthodes existantes :
  • Méthodes basées sur la population (ex. PSRO, NFSP) : Requiert souvent des calculs coûteux de meilleure réponse et ne garantit la convergence que vers une politique moyenne, et non vers la dernière itération. Extraire une politique finale dans des contextes DRL n'est pas trivial.
  • Minimisation du regret contrefactuel (CFR) : Nécessite l'énumération complète de l'arbre du jeu (basée sur un modèle), ce qui la rend ingérable pour les grands domaines.
  • Méthodes basées sur la régularisation (ex. R-NaD) : Les approches récentes utilisent la régularisation pour assurer la convergence de la dernière itération vers un équilibre régularisé. Cependant, ceux-ci ne sont pas nécessairement de vrais équilibres de Nash (ils restent exploitables). De plus, les implémentations pratiques existantes (comme R-NaD) reposent sur la Dynamique Réplicatrice Neurale (NeuRD), qui a montré des performances inférieures par rapport aux méthodes de gradient de politique standard dans les benchmarks.
• Le vide : Il manque un algorithme évolutif, sans modèle et basé sur le gradient de politique qui converge prouvablement vers un équilibre de Nash exact dans les grands IIGs.

2. Méthodologie

Les auteurs proposent une approche en deux étapes : un cadre théorique (IMMD) et un algorithme pratique (NASHPG).

A. Cadre théorique : MMD itératif (IMMD)

Les auteurs étendent la Descente de Miroir Magnétique (MMD), une méthode qui résout les inégalités variationnelles (VI) régularisées.

• VI régularisée : Les problèmes VI standards pour les équilibres de Nash sont monotones mais pas fortement monotones, ce qui les rend difficiles à résoudre directement. La MMD ajoute un régulariseur fortement convexe (basé sur la divergence de Bregman) pour créer un opérateur fortement monotone, assurant une solution unique.
• Affinement itératif : Au lieu de résoudre un seul problème régularisé, l'IMMD résout une séquence de ceux-ci.
  1. Commencer avec un profil de stratégie initial $\rho$.
  2. Résoudre le problème VI régularisé $VI(Z, G_\rho)$ pour trouver une nouvelle stratégie $z = M(\rho)$.
  3. Utiliser cette nouvelle stratégie $z$ comme référence $\rho$ pour le tour suivant.
• Garantie théorique : Le papier prouve que ce processus itératif produit une réduction strictement monotone de la divergence de Bregman par rapport à tout équilibre de Nash. Par conséquent, la séquence de stratégies converge vers un véritable équilibre de Nash.

B. Algorithme pratique : Gradient de politique de Nash (NASHPG)

Pour rendre l'IMMD applicable aux jeux à grande échelle où l'énumération complète est impossible, les auteurs dérivent NASHPG :

• Des stratégies mixtes aux stratégies comportementales : Ils approximent la divergence de Bregman des stratégies mixtes (utilisée dans l'IMMD) par une divergence Kullback-Leibler (KL) entre les politiques comportementales (politiques stochastiques en RL).
• Fonction objectif : L'algorithme optimise un objectif de politique régularisé :
  $$\text{Objectif} = \mathbb{E}[R] - \alpha \cdot \mathbb{E}_{o} [ D_{KL}(\pi(\cdot|o) \parallel \rho(\cdot|o)) ]$$
  Où $\pi$ est la politique actuelle, $\rho$ est la politique de référence (de la boucle externe précédente), et $\alpha$ est la force de régularisation.
• Structure de l'algorithme :
  1. Boucle interne : Effectuer $K$ étapes de mises à jour standard de gradient de politique (par exemple, en utilisant PPO) pour optimiser l'objectif régularisé contre la référence actuelle $\rho$.
  2. Boucle externe : Après $K$ étapes, mettre à jour la politique de référence $\rho$ vers la politique actuelle $\pi$, et répéter.
• Modularité : NASHPG est agnostique quant à l'estimateur spécifique du gradient de politique. Il peut s'intégrer de manière transparente avec des algorithmes avancés de RL à agent unique comme PPO (Proximal Policy Optimization).

3. Contributions clés

1. Convergence théorique : Introduction de IMMD, un cadre de régularisation multi-tours qui garantit une réduction strictement monotone de la divergence de Bregman et une convergence vers un équilibre de Nash exact dans les jeux extensifs 2p0s.
2. Algorithme pratique (NASHPG) : Développement d'un algorithme évolutif et sans modèle qui implémente le cadre IMMD en utilisant des méthodes de gradient de politique standard (comme PPO) et une régularisation KL.
3. Validation de l'hypothèse : Fourniture de preuves empiriques que la mauvaise performance des méthodes de régularisation précédentes (comme R-NaD) était due à l'utilisation de NeuRD comme solveur interne, plutôt qu'au cadre de régularisation lui-même. Le remplacement de NeuRD par PPO dans un cadre similaire a considérablement amélioré les performances.
4. Évolutivité : Démonstration de la capacité à résoudre des domaines à grande échelle (par exemple, Battleship, Texas Hold'em sans limite à tête-à-tête) où l'énumération exacte est impossible.

4. Résultats expérimentaux

Les auteurs ont évalué NASHPG sur sept jeux allant de petits (Poker de Kuhn) à massifs (Texas Hold'em sans limite à tête-à-tête).

• Convergence et stabilité : NASHPG a montré une convergence stable sans divergence, même avec des forces de régularisation élevées, contrairement à certaines lignes de base.
• Performance par rapport aux lignes de base :
  • Petits jeux : NASHPG a atteint une exploitabilité comparable ou inférieure à NFSP, PSRO, MMD et R-NaD sur le Poker de Kuhn, le Poker Leduc, Dark Hex et le Tic-Tac-Toe fantôme.
  • Grands jeux : Dans Battleship et le Texas Hold'em sans limite à tête-à-tête (où l'exploitabilité exacte est ingérable), NASHPG a obtenu des gains moyens plus élevés dans des matchs directs contre toutes les lignes de base (NFSP, PSRO, R-NaD, MMD).
• Étude d'ablation (R-NaD vs PPO) : Une expérience contrôlée a remplacé NeuRD par PPO dans le cadre R-NaD (créant RNaD-PPO).
  • Dans les petits jeux, la règle de mise à jour importait moins.
  • Dans les grands jeux, RNaD-PPO a considérablement surpassé le R-NaD standard, réduisant l'écart avec NASHPG. Cela a confirmé que la règle d'optimisation interne (PPO vs NeuRD) est le principal goulot d'étranglement dans la régularisation multi-tours basée sur des échantillons.
• Efficacité : L'implémentation n'a nécessité que ~20 lignes de modifications de code par rapport au PPO indépendant standard, soulignant son accessibilité.

5. Signification

• Relier la théorie et la pratique : Le papier comble avec succès le fossé entre les garanties de convergence théoriques (souvent limitées aux petits jeux énumérés) et les algorithmes MARL pratiques et évolutifs.
• Nouveau paradigme pour le MARL : Il établit que l'affinement itératif d'une référence de régularisation combiné à des gradients de politique standard est une approche supérieure pour trouver des équilibres de Nash par rapport aux méthodes basées sur la population ou aux anciennes techniques de régularisation.
• Accessibilité : En s'appuyant sur PPO standard et une régularisation KL simple, NASHPG abaisse la barrière à l'entrée pour les praticiens, leur permettant d'appliquer des garanties de convergence théoriques avancées sans avoir besoin de solveurs personnalisés complexes ou d'une énumération complète de l'arbre du jeu.
• Performance de pointe : Il établit une nouvelle référence pour les méthodes sans modèle dans les jeux à information imparfaite, surpassant les lignes de base établies dans les petits et les grands domaines.