mlsanityData to 14 Oct 2026

Cooperative Multi-agent RL with Communication Constraints

arXiv 2601.12518 ↗First posted 18 Jan 2026cs.LG cs.AI stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

Cooperative MARL often assumes frequent access to global information in a data buffer, such as team rewards or other agents' actions, which is typically unrealistic in decentralized MARL systems due to high communication costs. When communication is limited, agents must rely on outdated information to estimate gradients and update their policies. A common approach to handle missing data is called importance sampling, in which we reweigh old data from a base policy to estimate gradients for the current policy. However, it quickly becomes unstable when the communication is limited (i.e. missing data probability is high), so that the base policy in importance sampling is outdated. To address this issue, we propose a technique called base policy prediction, which utilizes old gradients to predict the policy update and collect samples for a sequence of base policies, which reduces the gap between the base policy and the current policy. This approach enables effective learning with significantly fewer communication rounds, since the samples of predicted base policies could be collected within one communication round. Theoretically, we show that our algorithm converges to an varepsilon-Nash equilibrium in potential games with only O(varepsilon-3/4) communication rounds and O(poly(maxi |Ai|)varepsilon-11/4) samples, improving existing state-of-the-art results in communication cost, as well as sample complexity without the exponential dependence on the joint action space size. We also extend these results to general Markov Cooperative Games to find an agent-wise local maximum. Empirically, we test the base policy prediction algorithm in both simulated games and MAPPO for complex environments.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 39 of its 49 references that are in the map. First posted on arXiv 18 Jan 2026.

Builds on

39 of 49 references.

References · 39

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2015Trust Region Policy Optimizationcited by 2,580
  3. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,558
  4. 2021The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Gamescited by 942
  5. 2019The StarCraft Multi-Agent Challengecited by 597
  6. 2017Value-Decomposition Networks For Cooperative Multi-Agent Learningcited by 503
  7. 2020Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learningcited by 485
  8. 2016Learning Multiagent Communication with Backpropagationcited by 366
  9. 2015Doubly Robust Off-policy Value Evaluation for Reinforcement Learningcited by 339
  10. 2020Is Independent Learning All You Need in the StarCraft Multi-Agent Challenge?cited by 294
  11. 2016Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learningcited by 286
  12. 2016Safe and Efficient Off-Policy Reinforcement Learningcited by 264
27 more
  1. 2019Multi-Agent Deep Reinforcement Learning for Large-scale Traffic Signal Controlcited by 164
  2. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 114
  3. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 105
  4. 2020Off-Policy Multi-Agent Decomposed Policy Gradientscited by 98
  5. 2017Multiagent Bidirectionally-Coordinated Nets: Emergence of Human-level Coordination in Learning to Play StarCraft Combat Gamescited by 96
  6. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 93
  7. 2016Delay and Cooperation in Nonstochastic Banditscited by 71
  8. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 67
  9. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 57
  10. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 49
  11. 2019Efficient Communication in Multi-Agent Reinforcement Learning via Variance Based Controlcited by 46
  12. 2019An Optimal Algorithm for Adversarial Bandits with Arbitrary Delayscited by 44
  13. 2020Stochastic bandits with arm-dependent delayscited by 36
  14. 2020Learning Adversarial Markov Decision Processes with Delayed Feedbackcited by 33
  15. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 30
  16. 2020Adapting to Delays and Data in Adversarial Multi-Armed Banditscited by 29
  17. 2022Sample-Efficient Reinforcement Learning of Partially Observable Markov Gamescited by 27
  18. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 27
  19. 2021Provably Efficient Cooperative Multi-Agent Reinforcement Learning with Function Approximationcited by 23
  20. 2022Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 22
  21. 2024Randomized Exploration in Cooperative Multi-Agent Reinforcement Learningcited by 17
  22. 2023Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Gamescited by 13
  23. 2022Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Gamescited by 12
  24. 2022Multi-Agent Reinforcement Learning with Reward Delayscited by 9
  25. 2023Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximationcited by 9
  26. 2023Communication-Efficient Decentralized Multi-Agent Reinforcement Learning for Cooperative Adaptive Cruise Controlcited by 9
  27. 2025Belief-Based Offline Reinforcement Learning for Delay-Robust Policy Optimizationcited by 1

Built on by

Not cited yet.