# MARL-LNS: Cooperative Multi-agent Reinforcement Learning via Large Neighborhoods Search

arXiv: https://arxiv.org/abs/2404.03101 · HTML: https://mlsanity.com/paper/2404.03101/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 38 references that are in the map.
- First posted on arXiv 3 Apr 2024.

## Builds on (most cited first, 22 of 22)

- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (2015)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games](https://mlsanity.com/paper/2103.01955/) (2021)
- [Counterfactual Multi-Agent Policy Gradients](https://mlsanity.com/paper/1705.08926/) (2017)
- [QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1803.11485/) (2018)
- [The StarCraft Multi-Agent Challenge](https://mlsanity.com/paper/1902.04043/) (2019)
- [Value-Decomposition Networks For Cooperative Multi-Agent Learning](https://mlsanity.com/paper/1706.05296/) (2017)
- [QTRAN: Learning to Factorize with Transformation for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1905.05408/) (2019)
- [Google Research Football: A Novel Reinforcement Learning Environment](https://mlsanity.com/paper/1907.11180/) (2019)
- [Scaling Multi-Agent Reinforcement Learning with Selective Parameter Sharing](https://mlsanity.com/paper/2102.07475/) (2021)
- [JaxMARL: Multi-Agent RL Environments and Algorithms in JAX](https://mlsanity.com/paper/2311.10090/) (2023)
- [Guided Deep Reinforcement Learning for Swarm Systems](https://mlsanity.com/paper/1709.06011/) (2017)
- [Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs](https://mlsanity.com/paper/2107.10201/) (2021)
- [Human-Level Performance in No-Press Diplomacy via Equilibrium Search](https://mlsanity.com/paper/2010.02923/) (2020)
- [Randomized Entity-wise Factorization for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2006.04222/) (2020)
- [On the Complexity Analysis of Randomized Block-Coordinate Descent Methods](https://mlsanity.com/paper/1305.4723/) (2013)
- [Asynchronous Multi-Agent Reinforcement Learning for Efficient Real-Time Multi-Robot Cooperative Exploration](https://mlsanity.com/paper/2301.03398/) (2023)
- [Coordinated Proximal Policy Optimization](https://mlsanity.com/paper/2111.04051/) (2021)
- [Flatland Competition 2020: MAPF and MARL for Efficient Train Coordination on a Grid World](https://mlsanity.com/paper/2103.16511/) (2021)
- [E-MAPP: Efficient Multi-Agent Reinforcement Learning with Parallel Program Guidance](https://mlsanity.com/paper/2212.02064/) (2022)
- [Towards Efficient Multi-Agent Learning Systems](https://mlsanity.com/paper/2305.13411/) (2023)
- [Temporal Induced Self-Play for Stochastic Bayesian Games](https://mlsanity.com/paper/2108.09444/) (2021)

## Abstract (arXiv)

Cooperative multi-agent reinforcement learning (MARL) has been an increasingly important research topic in the last half-decade because of its great potential for real-world applications. Because of the curse of dimensionality, the popular "centralized training decentralized execution" framework requires a long time in training, yet still cannot converge efficiently. In this paper, we propose a general training framework, MARL-LNS, to algorithmically address these issues by training on alternating subsets of agents using existing deep MARL algorithms as low-level trainers, while not involving any additional parameters to be trained. Based on this framework, we provide three algorithm variants based on the framework: random large neighborhood search (RLNS), batch large neighborhood search (BLNS), and adaptive large neighborhood search (ALNS), which alternate the subsets of agents differently. We test our algorithms on both the StarCraft Multi-Agent Challenge and Google Research Football, showing that our algorithms can automatically reduce at least 10% of training time while reaching the same final skill level as the original algorithm.