Randomness is sometimes necessary for coordination

Technische Samenvatting: Diamond Attention voor Toevalsgedreven Coördinatie

Probleemstelling
In coöperatief Multi-Agent Reinforcement Learning (MARL) is volledige parameterdeling de standaardbenadering voor homogene agenten, vaak gecombineerd met Gecentraliseerde Training en Gedecentraliseerde Executie (CTDE). Deze aanpak faalt echter in taken met multi-modale beloningsstructuren waar meerdere even optimale gezamenlijke strategieën bestaan. Onder permutatie-symmetrische observaties produceert een gedeeld deterministisch beleid identieke actie-distributies voor alle agenten, waardoor roldifferentiatie onmogelijk wordt. Theoretisch werk van Angluin (1980) en Case et al. (2005) stelt vast dat symmetriebreking onder anonieme processors deterministisch onmogelijk is; toegang tot gedeelde willekeurige bits is een noodzakelijke voorwaarde voor coördinatie wanneer agenten geen unieke identificatoren bezitten. Bestaande oplossingen blijven óf deterministisch op het moment van uitvoering (en voldoen dus niet aan de theoretische vereiste), óf bereiken symmetriebreking via sequentiële uitvoering, wat $O(N)$ inferentiële latentie introduceert en een extern opgelegde uitvoeringsvolgorde vereist—een circulaire afhankelijkheid in echt gedecentraliseerde settings.

Methodologie: Diamond Attention
De auteurs stellen Diamond Attention voor, een cross-attention-architectuur die de theoretische noodzaak van gedeelde willekeur operationaliseert om symmetrie te breken in één enkele broadcastronde.

• Kernmechanisme: Op elk tijdstip samplet elke agent een scalair willekeurig getal $r_i \sim \text{Uniform}[0, 1]$. Deze scalairen worden via een enkele broadcast met het team gedeeld.
• Gestructureerde Maskering: De willekeurige getallen induceren een transient, strikt rangordening onder de agenten. Een gestructureerd attentiemasker wordt toegepast op het agent-naar-agent cross-attention-mechanisme:
  • Als agent $j$ een lagere rang heeft dan agent $i$ ($r_j < r_i$), maskert agent $i$ agent $j$ uit.
  • Agent $i$ attendeert alleen op agenten met gelijke of hogere rangen.
  • Taak-naar-agent-attentie blijft volledig ongemaskerd, zodat alle agenten toegang behouden tot de globale doelstructuur.
• Resultante Asymmetrie: Deze maskering creëert een dynamische, per-tijdstip hiërarchie. Hoog-rang agenten handelen grotendeels onafhankelijk (attenderend voornamelijk op taak-embeddings), terwijl laag-rang agenten hun gedrag conditioneren op de acties van hoger-rang collega's. Dit induceert gedifferentieerde latente representaties en actie-distributies ondanks identieke netwerkparameters.
• Schaalbaarheid: De architectuur opereert over sets van agent- en taak-embeddings, waardoor het elk aantal agenten en taken kan accepteren zonder modificatie, wat zero-shot generalisatie naar verschillende teamgroottes mogelijk maakt.

Belangrijkste Bijdragen

1. Theoretische Formalisering: Het artikel formaliseert de equivalentie tussen XOR-coördinatie en het delen van willekeurige bits, en verankert het architecturale ontwerp in de onmogelijkheidsresultaten van Case et al. (2005).
2. Architecturale Innovatie: Diamond Attention realiseert een coördinatieprotocol met willekeurige bits in één enkele broadcastronde zonder sequentiële uitvoering of externe agent-identificatoren te vereisen. Het vervangt de behoefte aan externe ordening door interne, gestructureerde stochasticiteit.
3. Empirische Validatie: De methode wordt gevalideerd in drie distincte regimes die specifieke coördinatie-pathologieën isoleren:
   • Symmetriebreking (XOR Game): In een perfect symmetrisch XOR-spel plateauën deterministische baselines dicht bij de vloer van willekeurige acties (0,5 succes voor $N=2$). Diamond Attention bereikt 1,0 succes.
   • Zero-Shot Schaalbaarheid (VMAS): Een beleid getraind op $N=4$ agenten generaliseert zero-shot naar teams van $N \in [2, 8]$ in zowel statische (Simple Spread) als dynamische (Food Collection) omgevingen, en presteert beter dan baselines die verslechteren bij ongezette teamgroottes.
   • Adversariale Transfer (SMACLite): De architectuur bereikt zero-shot transfer van het 2s3z-scenario naar het 3s5z-scenario, waarbij standaard baselines volledig falen door structurele beperkingen.

Resultaten en Ablatie-inzichten

• Noodzaak van Structuur: Het vervangen van het gestructureerde masker door standaard op dropout gebaseerde willekeur resulteert in een winpercentage van 0% in de SMAC-transfer-taak. Dit bevestigt dat het werkzame ingrediënt de protocol-ruimtestructuur van de willekeurige ordening is, en niet louter stochastische ruis.
• Generalisatiegrenzen: Hoewel de methode goed generaliseert in continue controle (VMAS), toont het kwetsbaarheid wanneer getraind op een strikt subset van de actieruimte (bijv. $N=2, K=3$) en ingezet op een groter team ($N=3, K=3$) in het XOR-spel. Dit contrasteert met de robuustheid in dynamische omgevingen waar omgevingsignalen extra asymmetrie bieden.
• Vergelijking met Autoregressieve Methoden: In tegenstelling tot autoregressieve modellen (zoals MAT) die symmetrie breken via sequentiële uitvoering, bereikt Diamond Attention 1,0 succes zonder $O(N)$ latentie of aannames over externe ordening.

Betekenis en Claims
Het artikel claimt dat Diamond Attention een coördinatieprimitief biedt waarbij de werkzame staat intern en stochastisch per stap wordt gegenereerd, in plaats van te vertrouwen op omgevingsignalen. De auteurs benadrukken dat deze benadering gedecentraliseerde coördinatie mogelijk maakt zonder globale synchronisatie of vaste agent-identiteiten.

De betekenis ligt in het aantonen dat gestructureerde willekeur, in plaats van deterministische optimalisatie of ongestructureerde ruis, de kritieke factor is voor coördinatie in symmetrische, anonieme settings. Het werk suggereert dat voor tijdkritieke implementaties in onbetrouwbare infrastructuur (bijv. rampenbestrijding) intern gesamplede coördinatie-toestanden veerkrachtiger zijn tegen communicatiefouten en adversariale jamming dan schema's die vertrouwen op waarneembare omgevingsaanwijzingen. De auteurs merken echter bescheiden beperkingen op, waaronder de behoefte aan adaptieve projectielagen om variabele actieruimtes te hanteren zonder representatieve capaciteit te offeren, en de huidige leer-flessenhals in hoog-dimensionale settings met schaarse beloningen ($N > 5$) onder PPO.