# Approximate Linear Programming for Decentralized Policy Iteration in Cooperative Multi-agent Markov Decision Processes

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 19 references that are in the map.
- First posted on arXiv 20 Nov 2023.

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

- [Decentralized Q-Learning in Zero-sum Markov Games](https://mlsanity.com/paper/2106.02748/) (2021)
- [Model-based Safe Deep Reinforcement Learning via a Constrained Proximal Policy Optimization Algorithm](https://mlsanity.com/paper/2210.07573/) (2022)
- [Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysis](https://mlsanity.com/paper/2109.03699/) (2021)
- [Linear Programming for Large-Scale Markov Decision Problems](https://mlsanity.com/paper/1402.6763/) (2014)
- [Multiagent Value Iteration Algorithms in Dynamic Programming and Reinforcement Learning](https://mlsanity.com/paper/2005.01627/) (2020)
- [A Linearly Relaxed Approximate Linear Program for Markov Decision Processes](https://mlsanity.com/paper/1704.02544/) (2017)

## Abstract (arXiv)

In this work, we consider a cooperative multi-agent Markov decision process (MDP) involving m agents. At each decision epoch, all the m agents independently select actions in order to maximize a common long-term objective. In the policy iteration process of multi-agent setup, the number of actions grows exponentially with the number of agents, incurring huge computational costs. Thus, recent works consider decentralized policy improvement, where each agent improves its decisions unilaterally, assuming that the decisions of the other agents are fixed. However, exact value functions are considered in the literature, which is computationally expensive for a large number of agents with high dimensional state-action space. Thus, we propose approximate decentralized policy iteration algorithms, using approximate linear programming with function approximation to compute the approximate value function for decentralized policy improvement. Further, we consider (both) cooperative multi-agent finite and infinite horizon discounted MDPs and propose suitable algorithms in each case. Moreover, we provide theoretical guarantees for our algorithms and also demonstrate their advantages over existing state-of-the-art algorithms in the literature.