# Multiagent Rollout Algorithms and Reinforcement Learning

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Sep 2019.

## Built on by (most cited first, 10 of 10)

- [Trust Region Policy Optimisation in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2109.11251/) (2021)
- [Heterogeneous-Agent Reinforcement Learning](https://mlsanity.com/paper/2304.09870/) (2023)
- [Lessons from AlphaZero for Optimal, Model Predictive, and Adaptive Control](https://mlsanity.com/paper/2108.10315/) (2021)
- [More Centralized Training, Still Decentralized Execution: Multi-Agent Conditional Policy Factorization](https://mlsanity.com/paper/2209.12681/) (2022)
- [ACE: Cooperative Multi-agent Q-learning with Bidirectional Action-Dependency](https://mlsanity.com/paper/2211.16068/) (2022)
- [Revisiting Multi-Agent World Modeling from a Diffusion-Inspired Perspective](https://mlsanity.com/paper/2505.20922/) (2025)
- [Multiagent Reinforcement Learning for Autonomous Routing and Pickup Problem with Adaptation to Variable Demand](https://mlsanity.com/paper/2211.14983/) (2022)
- [Towards Global Optimality in Cooperative MARL with the Transformation And Distillation Framework](https://mlsanity.com/paper/2207.11143/) (2022)
- [Scalable Balanced Training of Conditional Generative Adversarial Neural Networks on Image Data](https://mlsanity.com/paper/2102.10485/) (2021)
- [Stable Parallel Training of Wasserstein Conditional Generative Adversarial Neural Networks](https://mlsanity.com/paper/2207.12315/) (2022)

## Abstract (arXiv)

We consider finite and infinite horizon dynamic programming problems, where the control at each stage consists of several distinct decisions, each one made by one of several agents. We introduce an approach, whereby at every stage, each agent's decision is made by executing a local rollout algorithm that uses a base policy, together with some coordinating information from the other agents. The amount of local computation required at every stage by each agent is independent of the number of agents, while the amount of total computation (over all agents) grows linearly with the number of agents. By contrast, with the standard rollout algorithm, the amount of total computation grows exponentially with the number of agents. Despite the drastic reduction in required computation, we show that our algorithm has the fundamental cost improvement property of rollout: an improved performance relative to the base policy. We also discuss possibilities to improve further the method's computational efficiency through limited agent coordination and parallelization of the agents' computations. Finally, we explore related approximate policy iteration algorithms for infinite horizon problems, and we prove that the cost improvement property steers the algorithm towards convergence to an agent-by-agent optimal policy.