# Multiagent Rollout and Policy Iteration for POMDP with Application to Multi-Robot Repair Problems

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Nov 2020.

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

- [Partially Observable Markov Decision Processes in Robotics: A Survey](https://mlsanity.com/paper/2209.10342/) (2022)
- [Lessons from AlphaZero for Optimal, Model Predictive, and Adaptive Control](https://mlsanity.com/paper/2108.10315/) (2021)
- [Reinforcement Learning for Adaptive Optimal Stationary Control of Linear Stochastic Systems](https://mlsanity.com/paper/2107.07788/) (2021)
- [Learning Logic Specifications for Policy Guidance in POMDPs: an Inductive Logic Programming Approach](https://mlsanity.com/paper/2402.19265/) (2024)
- [Model Predictive Control and Reinforcement Learning: A Unified Framework Based on Dynamic Programming](https://mlsanity.com/paper/2406.00592/) (2024)
- [Multiagent Reinforcement Learning for Autonomous Routing and Pickup Problem with Adaptation to Variable Demand](https://mlsanity.com/paper/2211.14983/) (2022)
- [Rollout Algorithms and Approximate Dynamic Programming for Bayesian Optimization and Sequential Estimation](https://mlsanity.com/paper/2212.07998/) (2022)
- [Distributed Online Rollout for Multivehicle Routing in Unmapped Environments](https://mlsanity.com/paper/2305.15596/) (2023)
- [Policy Evaluation in Decentralized POMDPs with Belief Sharing](https://mlsanity.com/paper/2302.04151/) (2023)
- [Surge Routing: Event-informed Multiagent Reinforcement Learning for Autonomous Rideshare](https://mlsanity.com/paper/2307.02637/) (2023)
- [Solving Truly Massive Budgeted Monotonic POMDPs with Oracle-Guided Meta-Reinforcement Learning](https://mlsanity.com/paper/2408.07192/) (2024)
- [Pro-Routing: Proactive Routing of Autonomous Multi-Capacity Robots for Pickup-and-Delivery Tasks](https://mlsanity.com/paper/2503.24325/) (2025)
- [A Convolution and Attention Based Encoder for Reinforcement Learning under Partial Observability](https://mlsanity.com/paper/2505.23857/) (2025)

## Abstract (arXiv)

In this paper we consider infinite horizon discounted dynamic programming problems with finite state and control spaces, partial state observations, and a multiagent structure. We discuss and compare algorithms that simultaneously or sequentially optimize the agents' controls by using multistep lookahead, truncated rollout with a known base policy, and a terminal cost function approximation. Our methods specifically address the computational challenges of partially observable multiagent problems. In particular: 1) We consider rollout algorithms that dramatically reduce required computation while preserving the key cost improvement property of the standard rollout method. The per-step computational requirements for our methods are on the order of O(Cm) as compared with O(Cm) for standard rollout, where C is the maximum cardinality of the constraint set for the control component of each agent, and m is the number of agents. 2) We show that our methods can be applied to challenging problems with a graph structure, including a class of robot repair problems whereby multiple robots collaboratively inspect and repair a system under partial information. 3) We provide a simulation study that compares our methods with existing methods, and demonstrate that our methods can handle larger and more complex partially observable multiagent problems (state space size 1037 and control space size 107, respectively). Finally, we incorporate our multiagent rollout algorithms as building blocks in an approximate policy iteration scheme, where successive rollout policies are approximated by using neural network classifiers. While this scheme requires a strictly off-line implementation, it works well in our computational experiments and produces additional significant performance improvement over the single online rollout iteration method.