Résumé Technique : ACPO : Agent-Chained Policy Optimization for Multi-Agent Reinforcement Learning

Énoncé du Problème

L'apprentissage par renforcement multi-agent coopératif (MARL) vise à trouver des politiques décentralisées qui maximisent conjointement un retour partagé. Sous le paradigme CTDE (Centralized Training with Decentralized Execution - Entraînement Centralisé avec Exécution Décentralisée), un défi fondamental demeure : le calcul direct du gradient de la politique jointe est difficile. Les approches existantes se divisent généralement en deux catégories, présentant toutes deux des limitations significatives :

1. Optimisation de Politiques Indépendantes (ex: MAPPO, MADDPG) : Les agents mettent à jour leurs politiques indépendamment en utilisant des critiques centralisés. Bien que ces méthodes soient évolutives, elles manquent de garanties générales d'amélioration de la politique jointe car elles ne tiennent pas compte de la non-stationnarité introduite par les changements de politiques des autres agents. La convergence n'est garantie que sous des hypothèses structurelles fortes, telles que la décomposition de la valeur.
2. Optimisation par Meilleure Réponse Alternée (ex: HAPPO, HATRRO) : Les agents effectuent des mises à jour séquentielles, traitant les politiques des autres comme étant fixes. Bien que cela garantisse l'amélioration monotone du retour conjoint à chaque étape, le point fixe est un Équilibre de Nash (NE). Dans les contextes coopératifs, un NE peut être arbitrairement sous-optimal par rapport à l'optimum social réel, et les agents n'ont aucun mécanisme pour échapper à ces équilibres sous-optimaux.

L'article postule qu'aucune de ces approches ne cible efficacement la politique jointe optimale du MDP multi-agent (MMDP) sous-jacent sans hypothèses restrictives ou convergence vers des équilibres sous-optimaux.

Méthodologie : Agent-Chained Policy Optimization (ACPO)

La contribution centrale de l'article est la dérivation d'une décomposition décentralisée exacte du gradient de la politique jointe. Ceci est réalisé en introduisant un nouveau formalisme, l'Agent-Chained Belief MDP (AC-BMDP), qui transforme le problème de décision jointe simultanée en un processus de décision sérialisé avec une information imparfaite.

1. L'Agent-Chained Belief MDP (AC-BMDP)

Motivé par les résultats de la théorie des jeux stipulant que les jeux simultanés peuvent être reformulés en processus sérialisés avec une information imparfaite, les auteurs décomposent chaque pas de temps de l'environnement $t$ en $N$ micro-étapes, une pour chaque agent $i \in \{1, \dots, N\}$.

• Sérialisation : Les agents s'engagent dans des actions séquentiellement au sein d'un même pas de temps. L'agent $i$ agit après les agents $1$à$i-1$.
• Augmentation de l'État : L'état pour l'agent $i$ est augmenté d'une croyance (belief) $b^{(i)}_t$ sur les actions réalisées par les agents précédents ($\vec{a}^{<i}_t$).
• Exécution Décentralisée : Puisque les actions réalisées par les agents précédents ne sont pas observées lors de l'exécution, la croyance est construite à partir des distributions d'actions ($\phi^{(j)}_t$) des agents précédents. Ces distributions sont des fonctions déterministes de l'état partagé et des politiques des agents, ce qui les rend accessibles sans communication.
• Opérateurs de Bellman Chaînés : La fonction de valeur pour l'agent $i$, $Q^{(i)}$, est définie de manière récursive. La valeur de l'agent $i$ dépend de la valeur de l'agent $i+1$ (l'agent suivant dans la chaîne). Seul l'agent final ($N$) reçoit la récompense de l'environnement et effectue le bootstrapping vers la valeur du premier agent au pas de temps suivant. Cet "enchevêtrement" (chaining) permet l'attribution de crédit sans supposer une fonction de valeur jointe décomposable.

2. Fondements Théoriques

L'article établit deux théorèmes clés :

• Théorème du Gradient de Politique Agent-Chained : Le gradient de la politique pour l'AC-BMDP peut être calculé en utilisant une fonction de score standard et un critique décentralisé $Q^{(i)}$ qui conditionne uniquement sur l'état propre de l'agent et la croyance sur les actions précédentes.
• Théorème de Décomposition du Gradient de Politique Multi-Agent : Le gradient de la politique jointe du MMDP original est montré comme étant exactement équivalent à une somme de $N$ termes indépendants par agent dérivés de l'AC-BMDP.
  $$\nabla_\theta J(\vec{\pi}_\theta) = \frac{1}{(\gamma')^{N-1}} \sum_{i=1}^N \mathbb{E} \left[ \nabla_\theta \log \pi^{(i)}_\theta(a^{(i)} | s, b^{(i)}) \cdot Q^{(i)}([s, b^{(i)}], a^{(i)}) \right]$$
  Crucialement, cette décomposition ne nécessite aucune hypothèse structurelle sur la fonction de valeur jointe (contrairement à VDN ou QMIX) et évite les points fixes sous-optimaux des mises à jour alternées.

3. Instanciations Algorithmiques

Les auteurs instaurent l'ACPO sous deux formes pratiques :

• ACPPO (On-Policy) : Un algorithme basé sur PPO où chaque agent optimise un objectif de substitution découpé (clipped surrogate objective) en utilisant les estimations d'avantage chaînées. L'avantage est calculé via une estimation de l'avantage généralisé (GAE) qui somme les résidus de différence temporelle (TD) chaînés à travers la chaîne d'agents.
• ACTD3 (Off-Policy) : Un algorithme basé sur TD3 pour le contrôle continu, où les agents maintient des doubles critiques suivant la structure de Bellman chaînée.

Approximation de la Croyance :

• Dans les contextes de Pleine Observabilité (MMDP), les agents calculent les croyances exactement en interrogeant les réseaux de politique des agents précédents.
• Dans les contextes d'Observabilité Partielle (Dec-POMDP), les agents emploient un Réseau de Croyance d'Action (Action Belief Network) pour prédire les distributions d'action des agents précédents basées sur leur propre historique local, entraîné via une perte de divergence KL contre la cible centralisée.

Contributions Clés

1. Formalisation de l'AC-BMDP : L'introduction d'un cadre formel combinant la sérialisation et l'augmentation de la croyance, permettant l'apprentissage optimal de la politique jointe sous CTDE sans hypothèses de décomposition de valeur.
2. Décomposition Exacte du Gradient : La preuve que le gradient de la politique jointe admet une décomposition exacte en termes par agent, permettant à des mises à jour indépendantes de constituer ensemble un seul pas de gradient sur l'objectif conjoint.
3. Convergence vers la Politique Jointe Optimale : Contrairement aux méthodes alternées qui convergent vers des Équilibres de Nash, l'article prouve que dans les contextes tabulaires, l'Itération de Politique Agent-Chained (ACPI) converge vers la politique jointe optimale du MMDP sous-jacent.
4. Algorithmes Évolutifs : Le développement d'ACPPO et d'ACTD3, qui démontrent que l'agent-chaining peut être appliqué à des algorithmes de Deep RL tant On-Policy qu'Off-Policy.

Résultats Expérimentaux

Les auteurs ont évalué l'ACPO sur trois benchmarks standards : Multi-Robot Warehouse (RWARE), SMACv2, et MA-MuJoCo.

• Performance : L'ACPO (spécifiquement ACPPO) a systématiquement surpassé les bases solides, incluant MAPPO (optimisation indépendante), HAPPO/HATRP (optimisation alternée) et les méthodes de décomposition de valeur (VDN, QMIX).
• Évolutivité avec le nombre d'agents : Une conclusion critique est que l'écart de performance entre l'ACPO et les bases s'élargit à mesure que le nombre d'agents augmente. Dans RWARE, l'avantage était particulièrement marqué dans les scénarios à 8 et 12 agents, suggérant que l'ACPO est particulièrement efficace dans les environnements à haute coordination et très encombrés.
• Performance Off-Policy : La variante off-policy, ACTD3, a également surpassé les bases (MADDPG, HATD3) dans MA-MuJoCo, démontrant la généralité du mécanisme d'agent-chaining.
• Études d'Ablation : Le retrait du mécanisme d'agent-chaining (réduisant ACPPO à MAPPO avec des entrées de croyance) a entraîné une performance similaire à MAPPO, confirmant que les gains proviennent du calcul de l'avantage chaîné, et non simplement de l'ajout d'états de croyance.
• Efficacité : Bien que l'ACPO nécessite un calcul de croyance séquentiel, le temps d'entraînement en temps réel reste comparable à MAPPO et est sensiblement plus rapide que les méthodes alternées (HAPPO/HATRP), qui nécessitent des mises à jour séquentielles des agents pendant l'entraînement.

Signification et Revendications

L'article affirme que l'ACPO fournit une solution fondée sur des principes au problème du MARL coopératif sous CTDE. Sa signification réside dans :

• Réduction du fossé : Il unifie les avantages des mises à jour indépendantes (évolutivité) et des mises à jour alternées (garanties d'amélioration monotone) tout en évitant leurs pièges respectifs (non-stationarité et équilibres de Nash sous-optimaux).
• Rigueur Théorique : Il offre la première décomposition exacte du gradient de la politique jointe qui ne repose pas sur des hypothèses de décomposition de valeur, garantissant théoriquement la convergence vers l'optimum social dans les contextes tabulaires.
• Efficacité Pratique : Les résultats empiriques suggèrent qu'une coordination explicite via le chaînage de croyance est un mécanisme supérieur pour gérer les tâches de coordination multi-agents complexes par rapport aux méthodes de l'état de l'art actuel, particulièrement lorsque la complexité de la population d'agents croît.

Les auteurs notent modestement des limitations, spécifiquement que le calcul de la croyance passe à l'échelle linéairement avec le nombre d'agents (menant à des passes avant de $O(N^2)$) et que les garanties théoriques actuelles reposent sur la pleine observabilité (MMDP), laissant l'extension aux Dec-POMDP généraux comme travail futur.