Teams of learning agents that each see only part of the world coordinate much better when they can all look at the same random number before acting. In effect they "flip a coin together" and then follow a joint plan keyed to the result. One known result shows that giving every agent the same random vector lets a team of independently acting agents represent any joint behavior a central controller could. Existing methods get this shared coin from a trusted broadcaster or a pre-installed seed. That is a weak point: whoever controls the coin can steer the team, whoever learns it early can predict the team, and one captured agent's seed reveals every future flip. We propose to generate the team's coordination signal with distributed key generation, a family of cryptographic protocols that let $n$ mutually untrusted parties jointly create a secret that no coalition of $t$ or fewer can learn or bias. Each step's coin then comes from a threshold randomness beacon that any $t+1$ teammates can compute together.
The question this raises is about learning more than about cryptography. A threshold beacon changes how the shared signal fails. Instead of arriving noisy or tampered, which breaks correlated coordination silently, the signal either arrives exactly and verifiably or does not arrive. Because the coin does not depend on the game state, it can be generated several steps ahead, so its generation does not slow down the agents' decisions. We want to measure three things: how much coordination value survives this all-or-nothing signal under realistic message loss, how much an opponent gains if it learns the coin, and whether policies can be trained to fall back gracefully when only some teammates hold the coin.
Core Claim
The claim is that a signal produced by distributed key generation is a better coordination device for decentralized multi-agent reinforcement learning than either a central broadcast or a pre-shared seed, whenever two conditions hold. The first is that an opponent benefits from predicting the signal. The second is that agents can be captured or must be revoked. The signal has to come with a training procedure that makes policies robust to a specific failure: an agent may know the coin while a teammate does not.
This claim rests on two pieces of prior work. Signal Instructed Coordination proves that conditioning decentralized policies on a shared Gaussian vector $z$ recovers the full centralized policy space. It reports a predator score in 2v2 predator-prey rising from 3.32 for MADDPG to 145.11 with the signal. However, it assumes a perfect, trusted broadcast of $z$. MACKRL uses a shared random seed for correlated sampling inside a hierarchical policy. It also leaves open what happens when that seed is degraded or untrusted. Both papers motivate this proposal and supply the coordination method we reuse. Neither treats the signal source as something an adversary could attack.
What Is Actually New Relative to the Closest Work
Only two papers in the file connect key generation and multi-agent learning, and both run the connection in the opposite direction.
FD2K uses reinforcement learning to generate keys. Two agents learn, under partial observability, which fluctuations in water-network pressure to turn into matching key bits. It reports a key-agreement advantage over an eavesdropper of 32% to 46%. It is limited to two parties.
PE-VDN uses additive secret sharing to keep the training critic private in centralized training with decentralized execution, the standard setup in which a critic sees everything during training but agents act on local views. It reaches roughly 80% of vanilla VDN's win rate on SMAC 3m at a privacy budget of $\varepsilon \approx 2.90$.
Our proposal differs from both. We use key generation to supply an execution-time coordination signal for a team of size $n$. We protect who can predict and bias the team's joint action, not training data. The cryptographic object, a threshold-signed beacon over the round index, is standard. What is new is treating its properties (exact agreement, verifiability, unpredictability below threshold, all-or-nothing delivery) as properties of a correlation device, and studying how learning should adapt to them.
Research Program
The beacon works as follows. Before deployment, the team runs a dealer-free key generation protocol in the tradition of Franklin et al.. It yields a group public key and per-agent secret shares, with no master key existing anywhere. This avoids the single point of failure that Crutchfield et al. attribute to central key authorities.
At step $t$, each agent broadcasts a partial signature on the index $t+k$. Any agent holding $t_{\mathrm{thr}}+1$ valid partial signatures combines them into a unique group signature. It hashes that signature to obtain $z_{t+k}$. Because the signature is unique and verifiable against the public key, every agent that obtains $z_{t+k}$ obtains the same value. A forged or corrupted partial is rejected rather than silently mixed in.
The lag $k$ is the key design parameter. The signal is independent of the state, so using a coin computed $k$ steps earlier costs nothing in coordination value. It also gives the protocol $k$ steps of retransmission to reach every agent. The quantity that matters is the probability $q_k$ that all agents hold $z_t$ when they act. Under independent per-message loss, $1-q_k$ should fall roughly geometrically in $k$, because each retransmission is an independent chance to collect the missing partials. We will measure this rather than assume it.
On the learning side, we train SIC-style policies whose inputs are either $z_t$ or an explicit "no coin" token. Training samples agent-specific availability masks from the loss model, including the dangerous case where availability differs across teammates. We add one structural rule: an agent that lacks the coin knows its teammates might hold it. To limit the harm, policies are regularized to keep the action they would take without the coin close to the action they would take averaged over the coin. This loss pulls each agent's coin-free action toward the coin-averaged one, so a teammate who lacks the coin stays compatible with teammates who have it. We expect this to limit miscoordination when availability is not common knowledge.
Finally, we build an adversarial evaluation: a learned opponent that, in the threat condition, receives the team's $z_t$. This measures exploitability directly.
Baselines
The naive reference point is decentralized execution with no shared signal, using MADDPG in particle environments and QMIX (QMIX) or COMA (COMA) on SMAC. COMA reports an 81% mean win rate on SMAC 5m. This baseline marks what the coin is worth at all.
The strongest competitor is SIC with an ideal trusted broadcast, as published. Its reported 2v2 predator-prey score of 145.11 is the ceiling we should approach. We will rerun it in our harness with the same environment seeds, network sizes, number of environment steps, and hyperparameter search budget as our method. We do not compare to the published number directly. Matching that ideal-broadcast score, within run-to-run spread over at least five seeds, at realistic loss rates and a modest lag, counts as success on utility. Beating it is not expected, because the ideal broadcast is an upper bound when no adversary is present.
We also compare against SIC with a noisy or tampered broadcast, where Gaussian corruption or a single adversarial relay alters $z$. This is the failure mode the file flags for SIC and MACKRL. The beacon should dominate it at matched loss rates.
The isolating ablation keeps the identical beacon but trains without availability masks and without the consistency regularizer. If this ablation does as well under realistic loss, the learning contribution is empty and the work reduces to an engineering result.
Why not just…?
Why not just pre-share a secret seed and run a keyed pseudorandom generator, as MACKRL effectively does? This is the most serious threat. It is free at run time and keeps $z$ secret from outside opponents. If no agent can ever be captured and the team never changes, it will match our method on every utility and secrecy metric, and we will report that. It loses in two places. First, capturing one agent exposes the key and therefore every future coin, which lets an opponent precompute the team's correlated plan offline. With a threshold beacon, capturing up to $t_{\mathrm{thr}}$ agents reveals nothing about future coins, and a re-run of key generation that excludes the captured agent restores secrecy without any trusted dealer. Second, someone has to install the seed, which reintroduces the dealer that AriaNN itself names as its main weakness. Our capture experiment settles whether these advantages matter in practice.
Why not just run a commit-then-reveal coin flip each round? It needs no key generation, but it needs every agent to finish both phases. The last agent to reveal can abort after seeing the others' values, which biases the coin. A single dropped agent stalls the round. The threshold beacon tolerates missing agents and cannot be biased by any coalition below threshold. We will compare availability $q_k$ and bias under adversarial aborts at equal message budgets.
Why not just skip the signal and rely on observed common knowledge or learned communication? MACKRL's line-of-sight common knowledge needs no cryptography and reportedly beats QMIX and COMA on SMAC 2s3z and 3m. The file gives no numeric win rates for this, so no reported result was found on Lacuna for MACKRL's exact scores. The limitation is that common knowledge from shared views disappears exactly when agents are spread out. SIC's matrix-game result, that standard learners converge to penalized joint actions, shows that a shared coin solves coordination problems that observation alone does not. We include MACKRL on SMAC to test whether the coin adds value beyond common knowledge.
Proposed Experiments
We will use three environments. The first is MPE 2v2 predator-prey, where SIC's numbers anchor the comparison. The second is SIC's Rock-Paper-Scissors-Well matrix game, for which no reported number was found on Lacuna, so we will establish our own reference values. The third is SMAC 3m, 2s3z and 5m from The StarCraft Multi-Agent Challenge, with MACKRL-style correlated sampling. All agent-to-agent messages pass through a simulated network with per-message loss swept from 0 to 30%, the lag $k$ from 0 to 8, and team sizes up to the largest SMAC map we can afford.
Metrics are team return or win rate, measured availability $q_k$, the fraction of steps where teammates disagree on coin availability, bytes and cryptographic operations per agent per step, and the exploitation gap. The exploitation gap is the drop in team return when a learned prey or opponent is given $z$. This makes concrete the threat model in which asynchronous protocols (asynchronous DKG) and UAV deployments (BASUV) operate.
Four checks decide the outcome. First, the exploitation gap must be substantial in predator-prey with a learned prey that sees $z$. If an opponent gains little from knowing the coin, keeping the coin secret does not matter and the pre-shared seed suffices. Second, at 10–20% loss with a small lag, the beacon-trained SIC policy must stay close to ideal-broadcast SIC, while noisy-broadcast SIC degrades. Third, the mask-trained policy with the consistency regularizer must beat the untrained-mask ablation at high loss. Fourth, in the capture experiment, an opponent holding one agent's secret must exploit the pre-shared-seed team on future rounds but not the threshold-beacon team after re-keying. If the first or fourth check fails, we will report that pre-shared seeds are enough and narrow the claim accordingly.
References
- Signal Instructed Coordination in Cooperative Multi-agent Reinforcement Learning
- Multi-Agent Common Knowledge Reinforcement Learning
- Securing IoT Communication Using Physical Sensor Data — Graph Layer Security with Federated Multi-agent Deep Reinforcement Learning
- Privacy-Engineered Value Decomposition Networks for Cooperative Multi-Agent Reinforcement Learning
- Efficient Generation of Shared RSA Keys (Extended Abstract)
- Generic On-Line/Off-Line Threshold Signatures
- QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning
- Counterfactual Multi-Agent Policy Gradients
- AriaNN: Low-Interaction Privacy-Preserving Deep Learning via Function Secret Sharing
- The StarCraft Multi-Agent Challenge
- Reaching Consensus for Asynchronous Distributed Key Generation
- BASUV: A Blockchain-Enabled UAV Authentication Scheme for Internet of Vehicles