Randomness is sometimes necessary for coordination

• URL: http://arxiv.org/abs/2605.06825v1
• Date: Thu, 07 May 2026 18:27:15 GMT
• Title: Randomness is sometimes necessary for coordination
• Abstract summary: Full parameter sharing is standard in cooperative multi-agent reinforcement learning (MARL) for homogeneous agents.<n>Under permutation-symmetric observations, a shared deterministic policy outputs identical action distributions for every agent, making role differentiation impossible.<n>We propose Diamond Attention, a cross-attention architecture in which each agent samples a scalar random number per timestep.
• Score: 2.1104538070656087
• License: http://creativecommons.org/licenses/by/4.0/
• 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$ success while all deterministic baselines plateau near $0.5$. On control coordination tasks, a policy trained on $N=4$ generalizes zero-shot to $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/

Related papers

• Adaptive Order Policies for Masked Diffusion [56.27207032553083]
  We propose a scheme for learning the unmasking order using an additional lightweight policy network on top of a diffusion model.<n>Our proposed loss reweights terms in the masked diffusion loss according to policy probabilities, and results in a policy that prefers positions where the denoiser is more likely to be correct.
  arXiv  Detail & Related papers  (2026-05-29T19:26:53Z)
• Adaptation to Intrinsic Dependence in Diffusion Language Models [5.185131234265025]
  Diffusion language models (DLMs) have emerged as a promising alternative to autoregressive (AR) approaches.<n>We introduce a distribution-agnostic unmasking schedule for DLMs that adapts to the (unknown) dependence structure of the target data distribution.<n>Our results significantly improve upon prior convergence theories and yield substantial sampling acceleration for low-complexity distributions.
  arXiv  Detail & Related papers  (2026-02-23T18:41:34Z)
• Mean-Field Reinforcement Learning without Synchrony [11.907264672363718]
  Mean-field reinforcement learning scales to large populations by reducing each agent's dependence on others to a single summary statistic -- the mean action.<n>Existing MF-RL theory is built on the mean action and does not extend to $$.<n>We construct the Temporal Mean Field framework around the population distribution $$ from scratch, covering the full spectrum from fully synchronous to purely sequential decision-making.
  arXiv  Detail & Related papers  (2026-02-20T06:42:08Z)
• See Less, Drive Better: Generalizable End-to-End Autonomous Driving via Foundation Models Stochastic Patch Selection [51.59559387222532]
  Recent advances in end-to-end autonomous driving show that policies trained on patch-aligned features generalize better to Out-of-Distribution (OOD)<n>We present $2.4-Patch-Selection (SPS), a simple yet effective approach for learning policies that are more robust, generalizable, and efficient.
  arXiv  Detail & Related papers  (2026-01-15T18:58:33Z)
• Batched Stochastic Matching Bandits [43.651070266360954]
  We introduce a novel bandit framework for matching based on the Multi-nomial Logit (MNL) choice model.<n>In our setting, $N$ agents on one side are assigned to $K$ arms on the other side, where each armally selects an agent from its assigned pool according to an unknown preference.<n>The objective is to minimize regret by maximizing the cumulative revenue from successful matches across all agents.
  arXiv  Detail & Related papers  (2025-09-04T13:16:32Z)
• From Continual Learning to SGD and Back: Better Rates for Continual Linear Models [50.11453013647086]
  We analyze the forgetting, i.e., loss on previously seen tasks, after $k$ iterations.<n>We develop novel last-iterate upper bounds in the realizable least squares setup.<n>We prove for the first time that randomization alone, with no task repetition, can prevent catastrophic in sufficiently long task sequences.
  arXiv  Detail & Related papers  (2025-04-06T18:39:45Z)
• Cooperative Multi-Agent Constrained Stochastic Linear Bandits [2.099922236065961]
  A network of $N$ agents communicate locally to minimize their collective regret while keeping their expected cost under a specified threshold $tau$. We propose a safe distributed upper confidence bound algorithm, so called textitMA-OPLB, and establish a high probability bound on its $T$-round regret. We show that our regret bound is of order $ mathcalOleft(fracdtau-c_0fraclog(NT)2sqrtNsqrtTlog (1/|lambda|)
  arXiv  Detail & Related papers  (2024-10-22T19:34:53Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed. SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
  arXiv  Detail & Related papers  (2023-12-13T11:08:25Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  This paper investigates group distributionally robust optimization (GDRO) with the goal of learning a model that performs well over $m$ different distributions. To reduce the number of samples in each round from $m$ to 1, we cast GDRO as a two-player game, where one player conducts and the other executes an online algorithm for non-oblivious multi-armed bandits. In the second scenario, we propose to optimize the average top-$k$ risk instead of the maximum risk, thereby mitigating the impact of distributions.
  arXiv  Detail & Related papers  (2023-02-18T09:24:15Z)
• Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits [81.60136088841948]
  We propose an algorithm that minimizes the regret over the horizon of time $T$. The proposed algorithm is applicable to domains such as recommendation systems and transportation.
  arXiv  Detail & Related papers  (2023-01-31T03:49:00Z)
• Collaborative Multi-agent Stochastic Linear Bandits [28.268809091816287]
  We study a collaborative multi-agent linear bandit setting, where $N$ agents that form a network communicate locally to minimize their overall regret. All the agents observe the corresponding rewards of the played actions and use an accelerated consensus procedure to compute an estimate of the average of the rewards obtained by all the agents.
  arXiv  Detail & Related papers  (2022-05-12T19:46:35Z)
• Cooperative Online Learning in Stochastic and Adversarial MDPs [50.62439652257712]
  We study cooperative online learning in and adversarial Markov decision process (MDP) In each episode, $m$ agents interact with an MDP simultaneously and share information in order to minimize their individual regret. We are the first to consider cooperative reinforcement learning (RL) with either non-fresh randomness or in adversarial MDPs.
  arXiv  Detail & Related papers  (2022-01-31T12:32:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.