# Randomness is sometimes necessary for coordination

arXiv: https://arxiv.org/abs/2605.06825 · HTML: https://mlsanity.com/paper/2605.06825/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Multi-agent reinforcement learning, one of 15 directions in Deep reinforcement learning methods.
- Builds on 16 of its 28 references that are in the map.
- First posted on arXiv 7 May 2026.

## Placed in

- Deep reinforcement learning methods / [Multi-agent reinforcement learning](https://mlsanity.com/deeprl/multi-agent-reinforcement-learning/)

## Builds on (most cited first, 16 of 16)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games](https://mlsanity.com/paper/2103.01955/) (2021)
- [Value-Decomposition Networks For Cooperative Multi-Agent Learning](https://mlsanity.com/paper/1706.05296/) (2017)
- [Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2003.08839/) (2020)
- [Is Independent Learning All You Need in the StarCraft Multi-Agent Challenge?](https://mlsanity.com/paper/2011.09533/) (2020)
- [A Review of Cooperative Multi-Agent Deep Reinforcement Learning](https://mlsanity.com/paper/1908.03963/) (2019)
- [VMAS: A Vectorized Multi-Agent Simulator for Collective Robot Learning](https://mlsanity.com/paper/2207.03530/) (2022)
- [UPDeT: Universal Multi-agent Reinforcement Learning via Policy Decoupling with Transformers](https://mlsanity.com/paper/2101.08001/) (2021)
- [BenchMARL: Benchmarking Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2312.01472/) (2023)
- [Revisiting Some Common Practices in Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2206.07505/) (2022)
- [Sable: a Performant, Efficient and Scalable Sequence Model for MARL](https://mlsanity.com/paper/2410.01706/) (2024)
- [Multi-player Multi-armed Bandits with Collision-Dependent Reward Distributions](https://mlsanity.com/paper/2106.13669/) (2021)
- [SMAClite: A Lightweight Environment for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2305.05566/) (2023)
- [Kaleidoscope: Learnable Masks for Heterogeneous Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2410.08540/) (2024)

## Built on by (most cited first, 1 of 1)

- [Theory of Scene: Breaking the Symmetry Trap in Multi-Agent LLM Coordination](https://mlsanity.com/paper/2609.32939/) (2026)

## Abstract (arXiv)

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 ∈ [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/