Randomness is sometimes necessary for coordination

Résumé Technique : Attention Diamant pour la Coordination Pilotée par l'Aléatoire

Énoncé du Problème
Dans l'apprentissage par renforcement multi-agents (MARL) coopératif, le partage complet des paramètres constitue l'approche standard pour les agents homogènes, souvent combinée à un entraînement centralisé et une exécution décentralisée (CTDE). Cependant, cette approche échoue dans les tâches présentant des structures de récompense multimodales où plusieurs stratégies conjointes équivalentes et optimales existent. Sous des observations invariantes par permutation, une politique déterministe partagée produit des distributions d'actions identiques pour tous les agents, rendant impossible la différenciation des rôles. Des travaux théoriques d'Angluin (1980) et de Case et al. (2005) établissent que la brisure de symétrie parmi des processeurs anonymes est impossible de manière déterministe ; l'accès à des bits aléatoires partagés est une condition nécessaire à la coordination lorsque les agents manquent d'identifiants uniques. Les solutions existantes restent soit déterministes au moment de l'exécution (échouant ainsi à satisfaire l'exigence théorique), soit réalisent une brisure de symétrie par une exécution séquentielle, ce qui introduit une latence d'inférence de $O(N)$ et nécessite un ordre d'exécution imposé de l'extérieur — une dépendance circulaire dans des contextes véritablement décentralisés.

Méthodologie : Attention Diamant
Les auteurs proposent l'Attention Diamant, une architecture d'attention croisée qui opérationnalise la nécessité théorique du partage d'aléa pour briser la symétrie en un seul tour de diffusion.

• Mécanisme Central : À chaque pas de temps, chaque agent échantillonne un nombre aléatoire scalaire $r_i \sim \text{Uniform}[0, 1]$. Ces scalaires sont partagés avec l'équipe via une unique diffusion.
• Masquage Structuré : Les nombres aléatoires induisent un ordre de classement strict et transitoire parmi les agents. Un masque d'attention structuré est appliqué au mécanisme d'attention croisée agent-à-agent :
  • Si l'agent $j$ a un rang inférieur à celui de l'agent $i$ ($r_j < r_i$), l'agent $i$ masque l'agent $j$.
  • L'agent $i$ ne porte attention qu'aux agents ayant un rang égal ou supérieur.
  • L'attention tâche-à-agent reste entièrement non masquée, garantissant que tous les agents conservent l'accès à la structure globale de l'objectif.
• Asymétrie Résultante : Ce masquage crée une hiérarchie dynamique, spécifique à chaque pas de temps. Les agents hautement classés agissent largement de manière indépendante (portant principalement attention aux embeddings de tâche), tandis que les agents moins bien classés conditionnent leur comportement sur les actions de leurs pairs mieux classés. Cela induit des représentations latentes et des distributions d'actions différenciées malgré des paramètres de réseau identiques.
• Évolutivité : L'architecture opère sur des ensembles d'embeddings d'agents et de tâches, lui permettant d'accepter n'importe quel nombre d'agents et de tâches sans modification, permettant ainsi une généralisation zero-shot à différentes tailles d'équipe.

Contributions Clés

1. Formalisation Théorique : L'article formalise l'équivalence entre la coordination XOR et le partage de bits aléatoires, ancrant la conception architecturale dans les résultats d'impossibilité de Case et al. (2005).
2. Innovation Architecturale : L'Attention Diamant réalise un protocole de coordination par bits aléatoires en un seul tour de diffusion, sans nécessiter d'exécution séquentielle ni d'identifiants d'agents externes. Elle remplace le besoin d'un ordre externe par une stochasticité interne et structurée.
3. Validation Empirique : La méthode est validée à travers trois régimes distincts isolant des pathologies spécifiques de coordination :
   • Brisure de Symétrie (Jeu XOR) : Dans un jeu XOR parfaitement symétrique, les baselines déterministes plafonnent près du plancher de l'action aléatoire (0,5 de succès pour $N=2$). L'Attention Diamant atteint un succès de 1,0.
   • Évolutivité Zero-Shot (VMAS) : Une politique entraînée sur $N=4$ agents se généralise en zero-shot à des équipes de $N \in [2, 8]$ dans des environnements statiques (Simple Spread) et dynamiques (Food Collection), surpassant les baselines qui se dégradent sur des tailles d'équipe non vues.
   • Transfert Adversarial (SMACLite) : L'architecture réalise un transfert zero-shot du scénario 2s3z au scénario 3s5z, où les baselines standards échouent totalement en raison de limitations structurelles.

Résultats et Insights d'Ablation

• Nécessité de la Structure : Le remplacement du masque structuré par une aléa standard basé sur le dropout entraîne un taux de victoire de 0 % dans la tâche de transfert SMAC. Cela confirme que l'ingrédient opératoire est la structure dans l'espace des protocoles de l'ordre aléatoire, et non une simple bruit stochastique.
• Limites de Généralisation : Bien que la méthode se généralise bien en contrôle continu (VMAS), elle montre une fragilité lorsqu'elle est entraînée sur un sous-ensemble strict de l'espace d'action (par exemple, $N=2, K=3$) et déployée sur une équipe plus large ($N=3, K=3$) dans le jeu XOR. Cela contraste avec sa robustesse dans les environnements dynamiques où les signaux environnementaux fournissent une asymétrie supplémentaire.
• Comparaison avec les Méthodes Autoregressives : Contrairement aux modèles autoregressifs (par exemple, MAT) qui brisent la symétrie via une exécution séquentielle, l'Attention Diamant atteint un succès de 1,0 sans latence de $O(N)$ ni hypothèses d'ordre externe.

Signification et Revendications
L'article revendique que l'Attention Diamant fournit un primitif de coordination où l'état opératoire est généré de manière interne et stochastique à chaque étape, plutôt que de dépendre de signaux environnementaux. Les auteurs soulignent que cette approche permet une coordination décentralisée sans synchronisation globale ni identités d'agents fixes.

La signification réside dans la démonstration que l'aléa structuré, plutôt qu'une optimisation déterministe ou un bruit non structuré, est le facteur critique pour la coordination dans des contextes symétriques et anonymes. Ce travail suggère que pour des déploiements critiques en termes de temps dans des infrastructures peu fiables (par exemple, réponse aux catastrophes), les états de coordination échantillonnés en interne sont plus résilients aux défaillances de communication et au brouillage adversarial que les schémas reposant sur des indices environnementaux observables. Cependant, les auteurs notent modestement des limitations, notamment la nécessité de couches de projection adaptatives pour gérer des espaces d'action variables sans sacrifier la capacité de représentation, ainsi que les goulots d'étranglement d'apprentissage actuels dans des contextes à haute dimension et à récompense sparse ($N > 5$) sous PPO.