Randomness is sometimes necessary for coordination

Rohan PatilJai MalegaonkarHenrik I. ChristensenDepartment of Computer Science and EngineeringUniversity of California San DiegoSan Diego, CA 92093 {rpatil, jmalegaonkar, hichristensen}@ucsd.edu · 2026

Read Randomness is sometimes necessary for coordination by Rohan PatilJai MalegaonkarHenrik I. ChristensenDepartment of Computer Science and EngineeringUniversity of California San DiegoSan Diego, CA 92093 {rpatil, jmalegaonkar, hichristensen}@ucsd.edu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-06825.txt.

Introduction

Rohan Patil, Jai Malegaonkar, and Henrik I. Christensen show that randomness is sometimes needed for same agents to act as a team. Cooperative learning teams usually share one policy, but under symmetric views a shared deterministic policy gives every agent the same action spread, making role split impossible. Symmetry breaking among unnamed chips is known to require randomness, and their Diamond Attention architecture builds it in.

Each agent samples a random number per step, creating a brief ranking that hides lower-ranked peers from agent-to-agent attention while task attention stays open. A team trained with four agents deploys as-is to teams of two through eight. On a symmetric test game it succeeds fully where deterministic rivals stall near chance.

Catalog record

CREATORRohan PatilJai MalegaonkarHenrik I. ChristensenDepartment of Computer Science and EngineeringUniversity of California San DiegoSan Diego, CA 92093 {rpatil, jmalegaonkar, hichristensen}@ucsd.edu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.06825

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Randomness is sometimes necessary for coordination Rohan PatilJai MalegaonkarHenrik I. ChristensenDepartment of Computer Science and EngineeringUniversity of California San DiegoSan Diego, CA 92093 {rpatil, jmalegaonkar, hichristensen}@ucsd.edu 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 1.0 success while all deterministic baselines plateau near 0.5 0.5 . On control coordination tasks, a policy trained on N = 4 N=4 generalizes zero-shot to N ∈ [ 2 , 8 ] 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/ 1 Introduction A widely adopted design choice in cooperative multi-agent reinforcement learning (MARL) is full parameter sharing, where all homogeneous agents execute copies of a single learned policy Gupta et al. 2017 ; Terry et al. 2020 . Combined with the centralized training and decentralized execution (CTDE) paradigm Lowe et al. 2017 and value decomposition methods such as VDN Sunehag et al. 2017 and QMIX Rashid et al. 2020 , this approach reduces sample complexity, simplifies training infrastructure, and scales naturally with team size. It has become the default substrate for cooperative MARL Sunehag et al. 2017 ; Rashid et al. 2020 ; Gronauer & Diepold 2022 ; Oroojlooy & Hajinezhad 2023 . This default fails in tasks with multi-modal reward structures, where multiple equally optimal joint strategies exist. Under such conditions, all agents produce identical action distributions when observations are structurally identical, making role differentiation impossible. Fu et al. 2022 use the XOR game—where two agents must choose opposite actions to receive any reward—to show that a shared deterministic policy outputs the same action for both agents, guaranteeing zero reward regardless of training duration, illustrating that this is not an empirical pathology that better optimization can resolve. Angluin 1980 proved that symmetry breaking among anonymous processors is impossible deterministically; Case et al. 2005 extended this to cooperative games, establishing that access to shared random bits is necessary , not merely beneficial, for coordination when agents lack unique identifiers. Section 2 develops these theoretical foundations and surveys how prior work falls short on each axis. Existing approaches address this problem on two axes, but no prior method satisfies both simultaneously. Methods that modify parameter sharing or optimization dynamics improve coordination in symmetric settings but remain deterministic at execution time, failing the theoretical randomness requirement. Methods that achieve symmetry breaking through sequential execution resolve the symmetry problem but require \mathcal{O}(N) inference rounds and an externally imposed execution order—which, in a truly decentralized homogeneous setting, is itself the symmetry-breaking problem. We operationalize the theoretical prescription of Case et al. 2005 in a practical MARL architecture. Our proposed Diamond Attention is a cross-attention mechanism between agent and task embeddings that incorporates structured random masking. At each timestep, every agent samples a scalar random number and shares it with the team via a single broadcast round. These scalars induce a strict rank ordering over agents, generating asymmetric attention masks over the agent dimension: each agent masks all agents ranked below it and attends only to agents at equal or higher rank. The mask applies only to agent-to-agent attention; task attention remains fully unmasked. The resulting asymmetry creates a dynamic, per-timestep hierarchy in which high-ranked agents attend to few peers and act largely independently, while low-ranked agents condition their behavior on what higher-ranked agents are doing. Because Diamond Attention operates over sets of agent and task embeddings, the architecture accepts any number of agents and any number of tasks without modification: policies trained on one team size generalize zero-shot to others as an inherent property of computing attention over variable-length sequences. Our contributions are as follows: • Theory. We formalize the equivalence between XOR coordination and random-bit sharing , providing the theoretical bridge that motivates each architectural component of Diamond Attention and grounds the structured mask in the necessity result of Case et al. (2005). • Architecture. We propose Diamond Attention, which realizes this protocol via structured random masking in a single broadcast round while retaining the set-based scalability of standard cross-attention. The architecture requires no sequential execution and no external agent identifiers. • Empirical validation. We validate across three regimes: Diamond Attention is the only approach to achieve 1.0 success on the XOR game where all deterministic baselines plateau at the random-action floor; a policy trained on N=4 generalizes zero-shot to N\in[2,8] on VMAS continuous coordination tasks; and the architecture achieves zero-shot transfer from easier to harder SMACLite scenarios where all baselines and ablations fail entirely. 2 Related Work Parameter sharing (PS) has become the dominant paradigm in cooperative MARL Gupta et al. 2017 ; Terry et al. 2020 , especially when combined with the CTDE framework Lowe et al. 2017 and value decomposition methods such as VDN Sunehag et al. 2017 and QMIX Rashid et al. 2020 . Under symmetric observations a shared deterministic policy produces identical outputs for all agents, and gradient updates that improve one agent’s strategy identically affect all others Fu et al. 2022 , trapping the system in symmetric equilibria. Recent work mitigates this while preserving PS efficiency: Kaleidoscope Li et al. 2024 introduces learnable sparse masks to induce per-agent heterogeneity at training time, GradPS Qin et al. 2025 resolves gradient conflicts that arise from opposing update signals, and pH-MARL Sebastián et al. 2025 leverages port-Hamiltonian geometric priors to enforce valid distributed coordination structures. However, Kaleidoscope’s learned masks are deterministic once trained; GradPS resolves gradient conflicts during optimization but produces no execution-time differentiation between agents; and pH-MARL’s geometric priors enforce coordination structure without introducing the stochasticity that theory demands. These methods address symptoms of the symmetry problem rather than its theoretical root. A related challenge is zero-shot scalability: deploying a trained policy to teams of varying size without retraining Liu et al. 2024 . UPDeT Hu et al. 2021 achieves scalability by treating each agent’s observation as part of a variable-length sequence, but agents act simultaneously from independent observations, leaving symmetry breaking unaddressed in multi-modal reward settings. Autoregressive models MAT Wen et al. 2022 and Sable Mahjoub et al. 2024 achieve symmetry breaking by construction through sequential execution, but at the cost of \mathcal{O}(N) inference latency and an externally imposed execution order—establishing that order requires a coordination mechanism, and in a truly decentralized homogeneous setting, agreeing on who executes first is equivalent to solving the symmetry-breaking problem, making the approach circularly dependent on an

Read the complete text