Résumé technique : Échantillonnage adaptatif centralisé pour l'entraînement coopératif fiable de politiques multi-agents indépendantes

Énoncé du problème

Les algorithmes de gradient de politique indépendants basés sur la politique (on-policy) constituent une approche standard pour l'apprentissage par renforcement multi-agents (MARL) dans les jeux coopératifs et sans conflit. Cependant, ces méthodes sont connues pour souffrir d'une convergence sous-optimale. Alors que la littérature antérieure attribue cet échec principalement à des cas où les gradients de politique individuels pointent à l'écart de l'équilibre joint optimal (problèmes de sélection d'équilibre), cet article identifie un nouveau mode de défaillance : l'erreur d'échantillonnage joint.

Les auteurs observent que même lorsque les gradients de politique individuels attendus de tous les agents pointent correctement vers la solution jointe optimale, une convergence sous-optimale peut toujours se produire. Cela est dû au fait que, dans la collecte de données finie, la stochasticité de l'échantillonnage d'actions indépendantes provoque une déviation de la distribution de données jointe empirique par rapport à la distribution jointe attendue sur la politique. Cette déviation entraîne des estimations de gradient imprécises. Crucialement, les agents peuvent avoir une erreur d'échantillonnage nulle concernant leurs propres distributions marginales d'actions tout en souffrant d'une erreur d'échantillonnage jointe significative, les amenant à renforcer des actions conjointes sous-optimales.

Méthodologie

Pour remédier à cela, l'article propose la Réduction de l'erreur d'échantillonnage coopératif (CoSER), un algorithme adaptatif d'échantillonnage d'actions opérant dans le cadre de l'entraînement centralisé avec exécution décentralisée (CTDE).

Mécanisme central

Contrairement à l'échantillonnage indépendant standard ou aux extensions décentralisées des méthodes d'échantillonnage adaptatif pour un seul agent, CoSER utilise une politique de comportement centralisée ($\pi_\phi$) pour collecter des données. Cette politique de comportement est continuellement adaptée pour augmenter la probabilité des actions conjointes sous-échantillonnées par rapport à la politique cible jointe actuelle ($\pi_\theta$).

Détails algorithmiques

1. Architecture : CoSER définit une politique de comportement centralisée $\pi_\phi(a|s)$ conditionnée par l'état joint complet $s$. Pour garantir que $\pi_\phi$ puisse être initialisée afin de correspondre à la politique cible décentralisée $\pi_\theta$, les auteurs introduisent une architecture spécialisée :
   $$\pi_\phi(\cdot|s) = \sigma(\log \pi_\theta(\cdot|s) + \Delta_\phi(s))$$
   Ici, $\Delta_\phi(s)$ est un réseau de neurones produisant des ajustements de logits. Il est initialisé à zéro, garantissant que $\pi_\phi \equiv \pi_\theta$ au début des mises à jour.
2. Règle de mise à jour : La politique de comportement est mise à jour par ascension de gradient sur un objectif de substitution tronqué (inspiré de PPO et PROPS) afin de minimiser la divergence entre la distribution de données empirique et la distribution de la politique cible. L'objectif augmente la probabilité des actions conjointes sous-échantillonnées et diminue celle des actions sur-échantillonnées.
3. Contraste avec MA-PROPS : L'article oppose CoSER à MA-PROPS, une extension multi-agents de l'algorithme PROPS pour un seul agent. MA-PROPS utilise des politiques de comportement indépendantes pour chaque agent. Les auteurs démontrent théoriquement et empiriquement que, bien que MA-PROPS réduise l'erreur d'échantillonnage pour les agents individuels, il échoue à réduire l'erreur d'échantillonnage jointe car il ne coordonne pas la sélection d'actions entre les agents.

Contributions clés

1. Identification d'un nouveau mode de défaillance : Les auteurs sont les premiers à montrer que l'erreur d'échantillonnage jointe peut provoquer une convergence sous-optimale dans l'apprentissage par renforcement par gradient de politique indépendant sur la politique, même lorsque les gradients attendus s'alignent avec un comportement optimal.
2. Insight théorique : Ils prouvent que la réduction de l'erreur d'échantillonnage pour les agents individuels de manière indépendante (comme le fait MA-PROPS) ne garantit pas une réduction de l'erreur d'échantillonnage jointe. Une sélection coordonnée des actions est requise pour corriger la distribution jointe.
3. Développement d'algorithme (CoSER) : Ils introduisent CoSER, une méthode d'échantillonnage adaptatif centralisée qui réduit efficacement l'erreur d'échantillonnage jointe en attribuant une probabilité plus élevée aux actions conjointes sous-échantillonnées.
4. Analyse de convergence : L'article étend l'analyse de convergence des environnements à un seul agent au MARL, montrant que sous CoSER, la distribution empirique de visite des états joints converge vers la vraie distribution avec une probabilité de 1, et que le taux de convergence pour l'erreur d'échantillonnage jointe est de $O_p(1/m^2)$, contre $O_p(1/m)$ pour l'échantillonnage standard sur la politique.

Résultats expérimentaux

Les auteurs évaluent CoSER sur un ensemble diversifié de jeux multi-agents sans conflit, notamment Level-Based Foraging (LBF), BoulderPush, GridWorld et divers jeux matriciels (2x2 et 3x3).

• Efficacité d'échantillonnage : Dans des tâches avec des politiques cibles fixes, CoSER réduit l'erreur d'échantillonnage jointe significativement plus vite que l'échantillonnage standard sur la politique et MA-PROPS. Dans certains cas, CoSER atteint la même réduction d'erreur avec 30 % à 50 % d'échantillons en moins. Notamment, MA-PROPS échoue souvent à réduire l'erreur d'échantillonnage jointe du tout.
• Fiabilité de la convergence : Pendant l'entraînement complet par RL (en utilisant MAPPO comme algorithme de base), CoSER augmente la probabilité que les agents convergent vers une politique jointe optimale de 10 % à 20 % par rapport aux références.
  • Dans des jeux matriciels difficiles (où les méthodes standard échouent souvent), CoSER est le seul algorithme à converger systématiquement vers la politique optimale.
  • Dans des environnements complexes comme GridWorld et BoulderPush, CoSER améliore les taux de réussite de 15 à 19 points de pourcentage par rapport à l'échantillonnage sur la politique.
• Comparaison avec MA-PROPS : MA-PROPS n'apporte généralement aucune amélioration par rapport à l'échantillonnage standard sur la politique en termes de fiabilité ou de réduction de l'erreur d'échantillonnage jointe, confirmant que l'échantillonnage adaptatif indépendant est insuffisant pour le contexte multi-agent.

Importance et affirmations

L'article affirme que la contribution principale est un changement de compréhension des causes de la convergence sous-optimale dans le MARL. Plutôt que de considérer les échecs de convergence uniquement comme le résultat d'objectifs conflictuels ou d'une mauvaise sélection d'équilibre (où les gradients pointent dans la mauvaise direction), les auteurs soutiennent que l'inefficacité de la collecte de données (erreur d'échantillonnage jointe) est un facteur critique, précédemment négligé.

L'importance de CoSER réside dans sa capacité à améliorer la fiabilité des algorithmes de gradient de politique indépendants sans modifier l'objectif d'apprentissage ni les règles de mise à jour du gradient. En coordonnant simplement la manière dont les données sont collectées via une politique de comportement centralisée, la méthode garantit que les données empiriques approximent mieux la distribution jointe attendue, conduisant à des estimations de gradient plus précises et à une probabilité plus élevée de trouver des politiques conjointes optimales. Les auteurs positionnent CoSER comme une première étape vers l'atténuation de l'erreur d'échantillonnage jointe, reconnaissant les limites de la mise à l'échelle vers un très grand nombre d'agents en raison de la croissance exponentielle de l'espace d'actions jointes.