# Multiagent Value Iteration Algorithms in Dynamic Programming and Reinforcement Learning

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 May 2020.

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

- [Lessons from AlphaZero for Optimal, Model Predictive, and Adaptive Control](https://mlsanity.com/paper/2108.10315/) (2021)
- [Dealing With Non-stationarity in Decentralized Cooperative Multi-Agent Deep Reinforcement Learning via Multi-Timescale Learning](https://mlsanity.com/paper/2302.02792/) (2023)
- [AlberDICE: Addressing Out-Of-Distribution Joint Actions in Offline Multi-Agent RL via Alternating Stationary Distribution Correction Estimation](https://mlsanity.com/paper/2311.02194/) (2023)
- [Modeling the Interaction between Agents in Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2102.06042/) (2021)
- [Multiagent Reinforcement Learning for Autonomous Routing and Pickup Problem with Adaptation to Variable Demand](https://mlsanity.com/paper/2211.14983/) (2022)
- [MA2QL: A Minimalist Approach to Fully Decentralized Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2209.08244/) (2022)
- [Rollout Algorithms and Approximate Dynamic Programming for Bayesian Optimization and Sequential Estimation](https://mlsanity.com/paper/2212.07998/) (2022)
- [Optimally Solving Simultaneous-Move Dec-POMDPs: The Sequential Central Planning Approach](https://mlsanity.com/paper/2408.13139/) (2024)
- [Scalable Balanced Training of Conditional Generative Adversarial Neural Networks on Image Data](https://mlsanity.com/paper/2102.10485/) (2021)
- [Surge Routing: Event-informed Multiagent Reinforcement Learning for Autonomous Rideshare](https://mlsanity.com/paper/2307.02637/) (2023)
- [Approximate Linear Programming for Decentralized Policy Iteration in Cooperative Multi-agent Markov Decision Processes](https://mlsanity.com/paper/2311.11789/) (2023)
- [ACPO: Agent-Chained Policy Optimization for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2606.30072/) (2026)

## Abstract (arXiv)

We consider infinite horizon dynamic programming problems, where the control at each stage consists of several distinct decisions, each one made by one of several agents. In an earlier work we introduced a policy iteration algorithm, where the policy improvement is done one-agent-at-a-time in a given order, with knowledge of the choices of the preceding agents in the order. As a result, the amount of computation for each policy improvement grows linearly with the number of agents, as opposed to exponentially for the standard all-agents-at-once method. For the case of a finite-state discounted problem, we showed convergence to an agent-by-agent optimal policy. In this paper, this result is extended to value iteration and optimistic versions of policy iteration, as well as to more general DP problems where the Bellman operator is a contraction mapping, such as stochastic shortest path problems with all policies being proper.