Randomness is sometimes necessary for coordination
Authors: Rohan Patil, Jai Malegaonkar, Henrik I. Christensen
Summary
The authors show that standard parameter sharing in multi-agent reinforcement learning fails when agents have symmetric observations—everyone gets identical action distributions, making role differentiation impossible. They propose Diamond Attention, where each agent samples a random number that creates a temporary rank ordering; lower-ranked agents can't see higher-ranked ones in agent-to-agent attention, breaking symmetry and enabling coordination. This implements a random-bit coordination protocol in one communication round.
Main takeaways:
- Under symmetric observations, a shared deterministic policy outputs identical actions for all agents, preventing any role specialization (e.g., in the XOR game, deterministic baselines plateau at 0.5 success; Diamond Attention hits 1.0).
- Each agent samples a scalar random number per timestep to induce a transient rank; lower-ranked agents' attention to higher-ranked peers is masked.
- Set-based attention enables zero-shot generalization: a policy trained on 4 agents works on 2–8 agents without retraining.
- Replacing structured randomness with standard dropout gives 0% win rate, confirming that protocol structure (not just noise) is essential.
- Demonstrates that randomness is sometimes theoretically necessary for coordination, not just an engineering trick.
Relevance
Not directly related to my persona/midtraining work—this is about multi-agent coordination via structured randomness in RL, not about language model conditioning or behavioral installation.
Abstract
arXiv:2605.06825v1 Announce Type: new Abstract: Full parameter sharing is standard in cooperative multi-agent reinforcement learning (MARL) for homogeneous agents. Under permutation-symmetric observations, however, a shared deterministic policy outputs identical action distributions for every agent, making role differentiation impossible. This failure can theoretically be resolved using symmetry breaking among anonymous identical processors, which requires randomness. We propose Diamond Attention, a cross-attention architecture in which each agent samples a scalar random number per timestep, inducing a transient rank ordering that masks lower-ranked peers from agent-to-agent attention while leaving task attention fully unmasked. This realizes a random-bit coordination protocol in a single broadcast round, and the set-based attention enables zero-shot deployment to teams of different sizes. We evaluate across three regimes that isolate when structured randomness matters. On the perfectly symmetric XOR game, our method achieves $1.0$ success while all deterministic baselines plateau near $0.5$. On control coordination tasks, a policy trained on $N=4$ generalizes zero-shot to $N \in [2,8]$. On SMACLite cross-scenario transfer, we achieve zero-shot transfer where standard baselines cannot transfer due to structural limitations. Furthermore, replacing the structured mask with standard dropout-based randomness results in a 0% win rate, confirming that protocol-space structure, not stochastic noise, is the operative ingredient. https://anonymous.4open.science/r/randomness-137A/