In distributed systems and multi-agent reinforcement learning (MARL), independent actors must work together to optimize a global objective. However, communicating in real time is often impossible, slow, or restricted by bandwidth constraints.
When agents are forced to act in isolation, independent randomization leads to miscoordination. In multi-player multi-armed bandits, independent exploration causes catastrophic collisions. In game theory, independent learning struggles to converge to optimal equilibria. As proven by Dylan J Foster et al. in Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games, independent no-regret learning in sequential Markov games is computationally intractable and statistically impossible without an exponential number of samples.
To bypass these fundamental hardness barriers, researchers leverage shared randomness. By utilizing a pre-shared random seed, a common external signal, or synchronized deterministic rules, independent actors can align their stochastic decisions completely locally. This approach simulates communication at zero cost, expanding the reachable joint policy space to match centralized control.
The Core Mechanism: Pseudo-Random Synchronization
Why does shared randomness work? At its core, the mechanism exploits the deterministic nature of pseudo-random number generators (PRNGs). If two isolated computers run the exact same PRNG initialized with the exact same seed, they will produce the exact same sequence of numbers. This allows them to make identical or perfectly complementary "random" choices locally, without exchanging a single byte of data over the network.
[Shared Seed / Signal]
│
├──────────────────────────────┐
▼ ▼
┌──────────────┐ ┌──────────────┐
│ Agent A │ │ Agent B │
│ Local PRNG │ │ Local PRNG │
└──────┬───────┘ └──────┬───────┘
│ │
▼ ▼
[Identical/Aligned] [Identical/Aligned]
┌─────────────────────────────────────────────┐
│ Perfectly Coordinated Execution │
└─────────────────────────────────────────────┘
This simple insight yields massive communication savings across diverse fields:
- Distributed Computing: Adam Karczmarz et al. demonstrate in Distributed Tasks: Introducing Distributed Computing to Programming Competitions that a shared seed allows parallel nodes to make identical work-partitioning and checkpointing decisions independently, eliminating network overhead.
- Distributed Optimization: In large-scale machine learning, Rafal Szlendak et al. leverage this in Permutation Compressors for Provably Faster Distributed Nonconvex Optimization to let distributed nodes locally generate identical permutations for coordinate selection, partitioning global tasks without server handshakes.
- Decentralized Federated Learning: Akihito Taya et al. use a pre-shared seed in Convergence Visualizer of Decentralized Federated Distillation with Reduced Communication Costs to synchronize data sample selection across nodes, eliminating the need to transmit sample identifiers.
- Algorithmic Replicability: Beyond optimization, Alkis Kalavasis et al. explore this in On the Computational Landscape of Replicable Learning, proving that shared-seed coordination aligns the stochastic components of learning algorithms to guarantee identical model outputs across independent instances trained on distinct datasets.
Expanding the Policy Space via Correlation Devices
In game theory, independent randomization limits agents to mixed Nash equilibria, which are often sub-optimal. A "correlation device" that broadcasts a common signal allows agents to reach a correlated equilibrium, unlocking higher team rewards.
Daniel S. Bernstein et al. introduced this concept to decentralized POMDPs in Bounded Policy Iteration for Decentralized POMDPs, showing that a shared source of randomness allows memory-bounded controllers to synchronize complex joint behaviors—such as alternating turns—without active communication during execution.
Mathematically, this works because conditioning decentralized policies on a shared signal breaks the independence constraint. As Liheng Chen et al. explain in Signal Instructed Coordination in Cooperative Multi-agent Reinforcement Learning, broadcasting a shared continuous random vector at the start of an episode expands the reachable joint policy space to exactly match that of a fully centralized controller.
This mechanism is highly versatile across different game structures:
- Stochastic Games: William Brown demonstrates in Learning in Multi-Player Stochastic Games that a shared random seed provides the common signal necessary for independent learners to achieve simultaneous no-regret bounds and converge to correlated equilibria.
- Adversarial Settings: Federico Cacciamani et al. show in Multi-Agent Coordination in Adversarial Environments through Signal Mediated Strategies that sampling a shared latent signal allows a team of agents to execute complex, synchronized strategies against an opponent that would be mathematically impossible under purely independent execution.
- Multi-Modal Policies: Junjie Sheng et al. demonstrate in Negotiated Reasoning: On Provably Addressing Relative Over-Generalization that synchronized random seeds allow decentralized agents to coordinate on specific modes of a multi-modal policy, avoiding the risk of miscoordination without requiring real-time communication.
Synchronized Exploration and Collision Avoidance
A classic failure mode in decentralized learning occurs in multi-player multi-armed bandits: if two players pull the same arm, they collide, resulting in wasted effort or zero reward.
Sebastien Bubeck et al. resolve this in Coordination without communication: optimal regret in two players multi-armed bandits and Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal Regret With Neither Communication Nor Collisions. By utilizing a pre-shared random seed, agents construct randomized geometric partitions of the action space. Because the seed is shared, both players agree on the boundaries of these partitions locally, allowing them to completely avoid collisions while maintaining optimal exploration rates.
Without Shared Randomness (Collisions):
Player 1: Explores Arm A ──┐
├──► [COLLISION] (Zero Reward)
Player 2: Explores Arm A ──┘
With Shared Randomness (Geometric Partitioning via Shared Seed):
Player 1: Explores Partition 1 (Arm A) ──► Success
Player 2: Explores Partition 2 (Arm B) ──► Success
Similarly, in online queuing systems, Flore Sentenac et al. demonstrate in Decentralized Learning in Online Queuing Systems that combining unique agent identifiers with shared random seeds allows independent actors to synchronize their exploration and exploitation phases. This enables them to run structured tournaments to estimate arrival and service rates without disrupting standard traffic flow.
In uncoupled learning for zero-sum games, Côme Fiegel et al. show in The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback that a shared random seed allows players to synchronize when to update their strategies versus when to exploit current information, achieving optimal last-iterate convergence without direct communication.
Implicit Coordination via Shared History and Determinism
What happens if a pre-shared random seed is unavailable? Agents can dynamically generate shared randomness from their environment or rely on strict algorithmic alignment.
Dynamic Hashing of Shared History
Xiao Feng Wang et al. show in Learning Near-Pareto-Optimal Conventions in Polynomial Time that decentralized agents can use their shared history of joint actions to seed a common cryptographic hash function. This dynamically generated shared randomness allows them to perform identical Markov Chain Monte Carlo walks, enabling them to sample and agree upon the same Pareto-optimal Nash equilibrium without explicit message exchange.
Shared Determinism
If agents run identical deterministic algorithms and share strict tie-breaking rules, they can achieve perfect coordination implicitly. As Moshe Tennenholtz et al. demonstrate in Learning to Coordinate Efficiently: A Model-based Approach, when agents maintain synchronized internal models of the environment, their independent calculations of optimal joint actions naturally align, causing them to act as a single distributed entity.
W. Z. Chang et al. utilize a similar principle in Online Learning for Cooperative Multi-Player Multi-Armed Bandits, where strictly deterministic exploration sequences allow players to implicitly calculate their teammates' actions based solely on the elapsed time step.
By substituting a shared algorithmic framework or a common source of randomness for real-time communication, these methods allow decentralized systems to achieve the efficiency, stability, and optimality of a centralized controller.
Key Foundational Work
Cooperation without Communication (1986) — contributed 3 concept elements to this direction.
Learning Near-Pareto-Optimal Conventions in Polynomial Time (2003) — contributed 2 concept elements to this direction.
Learning to Coordinate Efficiently: A Model-based Approach (2003) — contributed 2 concept elements to this direction.