Résumé Technique : Oracles de Réponse à l'Espace des Politiques Globales pour les Jeux à Deux Joueurs à Somme Nulle

1. Énoncé du Problème

Le calcul des équilibres de Nash dans les jeux à deux joueurs à somme nulle à grande échelle est computationnellement intraitable en raison des espaces de stratégies énormes. Le cadre des Oracles de Réponse à l'Espace des Politiques (PSRO) y remédie en étendant itérativement un ensemble de stratégies restreint (population) et en résolvant le « méta-jeu » induit pour trouver une méta-stratégie, généralement en utilisant l'Apprentissage par Renforcement Profond (DRL) pour générer des Meilleures Réponses (BR).

Un défi central dans PSRO est la construction de la population de stratégies : comment assembler un petit ensemble de stratégies sous des budgets computationnels limités de telle sorte que le jeu restreint induit approxime fidèlement le jeu complet. Les variantes existantes de PSRO reposent sur des Solveurs de Méta-Stratégies Basés sur le Jeu Restreint (RGB-MSS), qui calculent les méta-stratégies en utilisant uniquement la matrice de gains du jeu restreint actuel. Les auteurs soutiennent que cette approche conduit à des expansions inefficaces. Parce que les RGB-MSS ignorent les stratégies en dehors de la population actuelle, les BR résultantes peuvent être localement fortes mais contribuent peu à réduire l'exploitabilité globale (la distance vers un équilibre du jeu complet). Dans les scénarios les plus défavorables, les RGB-MSS peuvent nécessiter l'intégration de l'ensemble de l'espace des stratégies pour converger, même lorsqu'un support d'équilibre beaucoup plus petit existe.

2. Méthodologie : PSRO Global

Les auteurs proposent le PSRO Global, un cadre qui guide l'expansion de la population en optimisant explicitement la qualité de la population après l'ajout d'une stratégie candidate. La métrique centrale pour cette qualité est l'Exploitabilité de la Population (PE), définie comme l'exploitabilité minimale réalisable par n'importe quelle stratégie mixte supportée sur la population restreinte face à des adversaires du jeu complet.

La méthodologie consiste en un cadre d'Exploration–Sélection en deux phases :

Phase I : Exploration

Au lieu d'entraîner une seule BR contre une seule méta-stratégie, le PSRO Global génère un pool diversifié de réponses candidates.

• Pool de Mélanges : Un ensemble de méta-stratégies $S_t = \{\sigma_k\}_{k=1}^K$ est construit. Cela inclut une méta-stratégie de base (par exemple, issue d'un RGB-MSS standard comme l'Équilibre de Nash du Jeu Restreint) et $K-1$ mélanges supplémentaires échantillonnés uniformément à partir du simplexe de probabilité (par exemple, via une distribution de Dirichlet).
• Entraînement Conditionnel : Pour rendre l'entraînement multi-candidats réalisable, un seul réseau de politique conditionnel $\pi_\theta(a|s, \sigma)$ est entraîné via DRL (PPO) pour produire des réponses adaptées à chaque $\sigma_k \in S_t$. Cela génère un ensemble de stratégies candidates $\{\pi_k\}$.

Phase II : Sélection

Le cadre évalue quel candidat, s'il est ajouté à la population, entraînerait la PE la plus basse.

• Estimation de la PE : Pour chaque expansion candidate $\Pi_r \cup \{\pi_k\}$, l'algorithme estime la PE. Cela se fait en utilisant une procédure Minimisation des Regrets (RM) – Meilleure Réponse. Un réseau évaluateur conditionnel $\beta_\psi(a|s, \sigma)$ est utilisé pour suivre la meilleure réponse contre le mélange minimisant les regrets $\rho_k$ pour chaque candidat.
• Notation Régularisée : Pour assurer la robustesse face aux erreurs d'estimation (où un candidat pourrait apparaître bon simplement parce qu'il est rarement joué dans le mélange d'estimation), un score régularisé est utilisé :
  $$\widehat{PE}^{reg}_k = (1 - \hat{p}_k)(\widehat{PE}(\Pi_r; G) - U(\beta_k, \rho_r)) + \widehat{PE}_k$$
  où $\hat{p}_k$ est la masse attribuée à la nouvelle stratégie dans le mélange.
• Expansion : Le candidat $k^*$ minimisant la PE régularisée est sélectionné. La population est étendue en ajoutant à la fois le candidat sélectionné $\pi_{k^*}$ et la BR d'évaluation correspondante $\beta_{k^*}$ (une expansion de style Anytime-PSRO).

3. Contributions Clés

1. Analyse Théorique des Limites des RGB-MSS : Les auteurs prouvent que se fier uniquement aux gains du jeu restreint (RGB-MSS) peut conduire à une expansion de population hautement inefficace. Ils démontrent via le Théorème 3.2 que pour tout RGB-MSS, il existe des jeux où la convergence nécessite d'ajouter toutes les $N$ stratégies pures, alors qu'un solveur spécifique à l'instance pourrait atteindre l'équilibre en $O(S)$ itérations (où $S$ est la taille du support de l'équilibre).
2. Formulation d'Optimisation : Ils formulent la construction de la population de stratégies comme un problème d'optimisation explicite : minimiser la PE post-expansion. Cela aligne le processus d'expansion directement avec l'objectif principal d'approximation de l'équilibre du jeu complet.
3. Algorithme PSRO Global : Ils implémentent ce cadre comme un algorithme évolutif basé sur le DRL. Les innovations techniques clés incluent :
   • Partage de Paramètres : Utilisation de réseaux de neurones conditionnels pour générer plusieurs candidats et estimer la PE simultanément, amortissant ainsi le coût computationnel.
   • Sélection Régularisée : Un mécanisme de notation qui empêche la sélection de candidats qui semblent bénéfiques uniquement en raison du bruit d'estimation.
4. Garanties de Convergence : Sous l'hypothèse d'un oracle exact, le cadre préserve les garanties de convergence en itérations finies du PSRO standard tout en offrant une complexité d'itération améliorée dans les familles de jeux adversariaux (Théorème 4.3).

4. Résultats Expérimentaux

Des expériences ont été menées sur des jeux standards à deux joueurs à somme nulle sous forme extensive : Kuhn Poker, Liar's Dice, Leduc Poker et Goofspiel (5 et 13 cartes).

• Comparaison avec les Variantes de PSRO : Sous des budgets d'interaction environnementale appariés, le PSRO Global a constamment atteint une Exploitabilité de Population (PE) inférieure à celle des variantes PSRO standard utilisant les solveurs Nash, AlphaRank, PRD, Uniforme et Anytime PSRO. L'amélioration a été la plus significative dans les jeux plus grands (Leduc Poker, Goofspiel).
• Comparaison avec les Méthodes Pilotées par la Diversité : Le PSRO Global a surpassé le PSD-PSRO (une variante pilotée par la diversité), indiquant que simplement encourager des ajouts diversifiés est moins efficace que de sélectionner explicitement pour réduire la PE. L'ajout d'un objectif de diversité à la phase d'exploration du PSRO Global a fourni des gains marginaux supplémentaires dans certains jeux.
• Comparaison avec les Méthodes de Population Conditionnelle : Le PSRO Global a surpassé NeuPL (Neural Population Learning), qui utilise également un partage de paramètres conditionnel. Cela isole le gain de performance au mécanisme de sélection (minimisation de la PE post-expansion) plutôt qu'à l'architecture de partage de paramètres elle-même.
• Études d'Ablation : La suppression de n'importe quel composant (par exemple, utiliser uniquement l'exploitation, une sélection aléatoire, ou supprimer la régularisation de la PE) a dégradé les performances, confirmant que la combinaison de l'exploration d'informations globales et de la sélection basée sur la PE est critique.

5. Signification et Revendications

L'article revendique que la source dominante d'amélioration dans le PSRO Global est l'utilisation explicite d'informations globales pour sélectionner les expansions de population. En évaluant les candidats sur la base de leur capacité à réduire l'exploitabilité de l'ensemble de la population face au jeu complet (plutôt que de simplement répondre à une seule méta-stratégie de jeu restreint), la méthode évite les inefficacités inhérentes aux approches basées uniquement sur le jeu restreint.

Les auteurs positionnent le PSRO Global comme une solution pratique et évolutive pour les jeux à somme nulle à grande échelle, qui atteint une approximation d'équilibre supérieure avec moins d'itérations de politiques. Ils notent que leur discussion se limite aux jeux à deux joueurs à somme nulle, car l'extension de la métrique PE aux settings généraux à plusieurs joueurs est non triviale en raison de la perte de la structure de point selle. Un travail futur est suggéré pour étendre le cadre à des classes de jeux plus larges et développer des approximations de PE évolutives pour ces settings.