Résumé Technique : Graph-SND : Agrégation Éparse pour la Diversité Comportementale en Apprentissage par Renforcement Multi-Agent

1. Énoncé du Problème

En Apprentissage par Renforcement Multi-Agent (MARL), la Diversité Neurale Systémique (SND) est une métrique utilisée pour mesurer l'hétérogénéité comportementale entre les agents en moyennant les distances de Wasserstein par paires entre leurs distributions d'actions. Bien que la SND permette un contrôle de la diversité (par exemple, via l'algorithme DiCo), son calcul présente un goulot d'étranglement sévère en matière d'évolutivité. Le calcul de la SND complète nécessite d'évaluer toutes les $\binom{n}{2}$ paires d'agents, entraînant une complexité quadratique $O(n^2)$ par rapport au nombre d'agents $n$. Ce coût d'agrégation devient prohibitif pour les équipes à grande échelle, limitant l'application pratique de l'entraînement et du contrôle conscients de la diversité. L'article identifie l'étape d'« agrégation sous-groupe-vers-système » comme le principal défi ouvert, notant que les métriques existantes traitent la moyenne de toutes les paires comme une exigence fixe et non négociable.

2. Méthodologie : Graph-SND

Les auteurs introduisent Graph-SND, une généralisation de la SND qui remplace la moyenne du graphe complet par une moyenne pondérée sur les arêtes d'un graphe arbitraire $G = (A, E, w)$.

Définition

Soit $d(i, j)$ la distance comportementale de Monte Carlo entre les agents $i$ et $j$. Le Graph-SND est défini comme suit :
$$\text{SND}_G(D, G) = \frac{1}{W(G)} \sum_{\{i,j\} \in E} w_{ij} d(i, j)$$
où $W(G) = \sum_{\{i,j\} \in E} w_{ij}$ est le poids total des arêtes.

Trois Régimes Opérationnels

Le cadre prend en charge trois régimes distincts basés sur le choix du graphe $G$ :

1. Récupération Exacte ($G = K_n$) : Lorsque $G$ est le graphe complet avec des poids unitaires, Graph-SND récupère exactement la SND originale.
2. Diversité Localisée (Graphes Epars Fixes) : Lorsque $G$ est un graphe éparse fixe (par exemple, $k$ plus proches voisins, topologie de communication), la métrique mesure la diversité uniquement sur les interactions pertinentes pour la tâche. Cela réduit le coût computationnel à $O(|E|)$.
3. Estimation Éparse (Graphes Aléatoires) : Lorsque les arêtes sont échantillonnées aléatoirement (par exemple, échantillonnage de Bernoulli), Graph-SND agit comme un estimateur éparse de la SND complète.
   • Estimation Non biaisée : En utilisant les poids de Horvitz-Thompson ($w_{ij} = 1/p$), l'estimateur est inconditionnellement non biaisé.
   • Concentration : La moyenne d'échantillon normalisée (poids uniformes) satisfait des bornes de concentration de type Hoeffding, convergeant vers la vraie SND avec un taux de $O(1/\sqrt{m})$, où $m$ est le nombre d'arêtes échantillonnées.

Bornes Théoriques

• Distorsion Déterministe : Pour les graphes connectés fixes, l'article dérive des bornes reliant $\text{SND}_G$ à $\text{SND}$ en utilisant l'indice de routage des arêtes $\pi(G)$. Plus précisément, $|\text{SND}_G - \text{SND}|$ est borné par des facteurs impliquant $\pi(G)$.
• Graphes Expanders : Pour les graphes expanders aléatoires $d$-réguliers, l'indice de routage évolue comme $O(n \log n / d)$. Les auteurs prouvent que pour $d = \Theta(\log n)$, la distorsion relative dans le pire des cas est de $O(\log n)$.
• Raffinement Spectral : Sous des structures de distance de faible rang (norme nucléaire normalisée contrôlée), la borne d'erreur pour les expanders s'améliore à $O(\rho^*/\sqrt{d})$, expliquant les ratios empiriques proches de l'unité.
• Bornes Probabilistes : Pour les graphes aléatoires $d$-réguliers, une borne probabiliste inconditionnelle de $\tilde{O}(D_{\max}/\sqrt{n})$ est établie.

3. Contributions Clés

1. Définition de Graph-SND : Une couche d'agrégation éparse qui récupère la SND sur les graphes complets et coûte $O(|E|)$ sur les graphes précalculés.
2. Garanties Théoriques : Preuves de récupération, de non-négativité, d'invariance par automorphisme de graphe, d'absence de biais de Horvitz-Thompson et d'inégalités de concentration (Hoeffding/Serfling). L'article établit également des bornes de distorsion déterministes pour les graphes fixes et des bornes probabilistes inconditionnelles pour les graphes réguliers aléatoires.
3. Validation Empirique :
   • Récupération et Non-biais : Vérifié sur les environnements VMAS, montrant une récupération exacte sur $K_4$ et l'absence de biais de l'estimateur de Horvitz-Thompson pour $n=8$.
   • Évolutivité : Des accélérations en temps réel démontrées évoluant linéairement avec $1/p$ (probabilité d'échantillonnage) jusqu'à $n=500$.
   • Contrôle en Boucle Fermée : Intégration de Graph-SND dans le contrôleur de diversité DiCo. Pour $n=50$, Graph-SND de Bernoulli-0,1 a suivi les points de consigne avec une erreur relative inférieure à 1 % et a produit des différences de récompense indiscernables de zéro par rapport à la SND complète, tout en réduisant le coût de la métrique par appel d'environ $9,5\times$.
   • Performance des Expanders : Les expanders aléatoires $d$-réguliers ont atteint $\text{SND}_G/\text{SND} \in [0,9987, 1,0013]$ avec $\Theta(n \log n)$ arêtes, surpassant significativement d'autres bases éparces en termes de ratios distorsion-coût.

4. Résultats

• Efficacité : Dans une exécution PPO de 500 itérations avec $n=100$, Graph-SND de Bernoulli-0,1 a suivi la SND complète tout en réduisant le temps de métrique par appel d'environ $10\times$.
• Évolutivité : Le chronométrage GPU sur des politiques figées jusqu'à $n=500$ a confirmé l'accélération prédite de $\binom{n}{2}/|E|$, réduisant le temps de métrique d'environ 15,5 secondes à environ 1,5 seconde pour $n=500$ avec une densité d'arêtes de 10 %.
• Stabilité du Contrôle : Dans les expériences DiCo pour $n=50$, le contrôleur éparse a maintenu le suivi des points de consigne et a produit des différences de récompenses appariées centrées près de zéro sur neuf cellules appariées, avec une différence de récompense moyenne de $-6,2 \times 10^{-4}$.
• Robustesse : La méthode s'est transférée à des paramètres non gaussiens (PettingZoo MPE avec politiques catégorielles et distance de variation totale), maintenant un faible biais et des réductions de coût.

5. Importance et Revendications

L'article revendique que Graph-SND supprime avec succès le goulot d'étranglement d'agrégation de la SND sans altérer la sémantique de la métrique ni nécessiter de modifications des architectures de politique ou des algorithmes d'entraînement.

• Alternative Plug-and-Play : Il fournit une « alternative éparse plug-and-play » qui s'étend au-delà de la SND de graphe complet, prenant en charge à la fois la mesure passive et le contrôle de diversité en boucle fermée.
• Flexibilité Sémantique : Le graphe $G$ n'est pas présenté comme un paramètre de nuisance mais comme un choix délibéré déterminant la cible de mesure :
  • Utiliser un échantillonnage de Bernoulli pour estimer la diversité systémique complète.
  • Utiliser des graphes locaux fixes (par exemple, communication, $k$-NN) pour mesurer la diversité pertinente pour des structures d'interaction spécifiques.
  • Utiliser des graphes expanders pour des proxies éparces déterministes, quasi-linéaires, avec de fortes garanties structurelles dans le pire des cas.
• Limites Modestes : Les auteurs reconnaissent que bien que les bornes théoriques pour les expanders soient de $O(\log n)$, les ratios observés proches de l'unité dépendent des données et sont partiellement expliqués par les propriétés spectrales des matrices de distance MARL. Ils notent également que les expériences actuelles se concentrent sur le PPO indépendant, les algorithmes à critique centralisé étant laissés pour un travail futur.

En résumé, Graph-SND reformule l'agrégation de la diversité comme un problème de sélection de graphe, offrant un cadre unifié qui équilibre l'efficacité computationnelle avec des garanties théoriques pour la diversité comportementale en MARL.