Shared Randomness for Decentralized Coordination

93 concepts55 papers1 proposal

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:


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:


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.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 59 papers
  2. Version 1 · 2026-10-04 · 41 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_shared_randomness_synchronization_4295743f,
  title = {shared randomness synchronization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/shared-randomness-synchronization/rdr_4295743f2f264df7a4e2b18c2276bd11},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_shared_randomness_synchronization_4295743f_v2,
  title = {shared randomness synchronization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/shared-randomness-synchronization/rdr_4295743f2f264df7a4e2b18c2276bd11/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake