Randomness is sometimes necessary for coordination

Technical Summary: Diamond Attention for Randomness-Driven Coordination

Problem Statement
In cooperative Multi-Agent Reinforcement Learning (MARL), full parameter sharing is the standard approach for homogeneous agents, often combined with Centralized Training and Decentralized Execution (CTDE). However, this approach fails in tasks with multi-modal reward structures where multiple equally optimal joint strategies exist. Under permutation-symmetric observations, a shared deterministic policy produces identical action distributions for all agents, rendering role differentiation impossible. Theoretical work by Angluin (1980) and Case et al. (2005) establishes that symmetry breaking among anonymous processors is impossible deterministically; access to shared random bits is a necessary condition for coordination when agents lack unique identifiers. Existing solutions either remain deterministic at execution time (failing the theoretical requirement) or achieve symmetry breaking through sequential execution, which introduces $O(N)$ inference latency and requires an externally imposed execution order—a circular dependency in truly decentralized settings.

Methodology: Diamond Attention
The authors propose Diamond Attention, a cross-attention architecture that operationalizes the theoretical necessity of shared randomness to break symmetry in a single broadcast round.

• Core Mechanism: At each timestep, every agent samples a scalar random number $r_i \sim \text{Uniform}[0, 1]$. These scalars are shared with the team via a single broadcast.
• Structured Masking: The random numbers induce a transient, strict rank ordering among agents. A structured attention mask is applied to the agent-to-agent cross-attention mechanism:
  • If agent $j$ has a lower rank than agent $i$ ($r_j < r_i$), agent $i$ masks out agent $j$.
  • Agent $i$ attends only to agents with equal or higher ranks.
  • Task-to-agent attention remains fully unmasked, ensuring all agents retain access to the global goal structure.
• Resulting Asymmetry: This masking creates a dynamic, per-timestep hierarchy. High-ranked agents act largely independently (attending primarily to task embeddings), while lower-ranked agents condition their behavior on the actions of higher-ranked peers. This induces differentiated latent representations and action distributions despite identical network parameters.
• Scalability: The architecture operates over sets of agent and task embeddings, allowing it to accept any number of agents and tasks without modification, enabling zero-shot generalization to different team sizes.

Key Contributions

1. Theoretical Formalization: The paper formalizes the equivalence between XOR coordination and random-bit sharing, grounding the architectural design in the impossibility results of Case et al. (2005).
2. Architectural Innovation: Diamond Attention realizes a random-bit coordination protocol in a single broadcast round without requiring sequential execution or external agent identifiers. It replaces the need for external ordering with internal, structured stochasticity.
3. Empirical Validation: The method is validated across three distinct regimes isolating specific coordination pathologies:
   • Symmetry Breaking (XOR Game): In a perfectly symmetric XOR game, deterministic baselines plateau near the random-action floor (0.5 success for $N=2$). Diamond Attention achieves 1.0 success.
   • Zero-Shot Scalability (VMAS): A policy trained on $N=4$ agents generalizes zero-shot to teams of $N \in [2, 8]$ in both static (Simple Spread) and dynamic (Food Collection) environments, outperforming baselines that degrade on unseen team sizes.
   • Adversarial Transfer (SMACLite): The architecture achieves zero-shot transfer from the 2s3z to the 3s5z scenario, where standard baselines fail entirely due to structural limitations.

Results and Ablation Insights

• Necessity of Structure: Replacing the structured mask with standard dropout-based randomness results in a 0% win rate in the SMAC transfer task. This confirms that the operative ingredient is the protocol-space structure of the random ordering, not mere stochastic noise.
• Generalization Limits: While the method generalizes well in continuous control (VMAS), it shows brittleness when trained on a strict subset of the action space (e.g., $N=2, K=3$) and deployed on a larger team ($N=3, K=3$) in the XOR game. This contrasts with its robustness in dynamic environments where environmental signals provide additional asymmetry.
• Comparison to Autoregressive Methods: Unlike autoregressive models (e.g., MAT) that break symmetry via sequential execution, Diamond Attention achieves 1.0 success without $O(N)$ latency or external ordering assumptions.

Significance and Claims
The paper claims that Diamond Attention provides a coordination primitive where the operative state is generated internally and stochastically per step, rather than relying on environmental signals. The authors emphasize that this approach enables decentralized coordination without global synchronization or fixed agent identities.

The significance lies in demonstrating that structured randomness, rather than deterministic optimization or unstructured noise, is the critical factor for coordination in symmetric, anonymous settings. The work suggests that for time-critical deployments in unreliable infrastructure (e.g., disaster response), internally sampled coordination states are more resilient to communication failures and adversarial jamming than schemes relying on observable environmental cues. However, the authors modestly note limitations, including the need for adaptive projection layers to handle variable action spaces without sacrificing representational capacity and the current learning bottlenecks in high-dimensional, sparse-reward settings ($N > 5$) under PPO.