Abstract
Solving large-scale cooperative multi-agent Markov decision processes (MDPs) is computationally challenging due to the exponential growth of state and action spaces. This paper introduces Approximate Decentralized Policy Iteration (ADPI), a framework that integrates Approximate Linear Programming (ALP) with decentralized policy improvement. By decoupling the complexity of state-space approximation from the coordination of joint actions, ADPI achieves significant computational speedups and scalability. Experimental results in grid-world environments demonstrate that ADPI provides up to 19x faster convergence than traditional methods while maintaining strong theoretical performance guarantees.
1. Introduction
Sequential decision-making in multi-agent environments is often modeled using Markov Decision Processes (MDPs). In cooperative settings, agents must coordinate their actions to maximize a shared reward. However, traditional solution methods face two primary obstacles: the "state space explosion" and the "action space explosion." As the number of agents and environmental variables increases, the computational resources required to find an optimal policy grow exponentially, rendering exact solutions impractical for real-world applications.
This research addresses these challenges by proposing a scalable framework that combines decentralized decision-making with function approximation. The resulting algorithm, Approximate Decentralized Policy Iteration (ADPI), allows agents to coordinate effectively without the prohibitive costs associated with centralized, exact methods.
2. The Curse of Dimensionality in Multi-agent MDPs
The difficulty of multi-agent coordination stems from two distinct dimensions of complexity:
- State Space Explosion: In complex environments, the number of possible configurations of agents and objects grows exponentially with the number of variables.
- Action Space Explosion: In a cooperative MDP, the "joint action" is the Cartesian product of all individual agents' actions. For instance, if 10 agents each have 5 possible moves, the system must evaluate $5^{10}$ (approximately 9.7 million) possible joint actions at every step.
While decentralized methods have previously been proposed to allow agents to update policies sequentially, these methods typically require calculating exact values for every state. ADPI fills this gap by integrating approximation techniques directly into the decentralized update loop.
3. Methodology: The ADPI Framework
The ADPI algorithm is designed for both finite time horizons and infinite discounted horizons. Its efficiency is derived from two core pillars:
3.1 Decentralized Policy Improvement (DPIm)
Rather than optimizing the joint action of all agents simultaneously, ADPI employs a sequential "agent-by-agent" update mechanism. In this setup, Agent $i$ improves its policy based on the assumption that agents $1$ through $i-1$ have already updated their policies, while agents $i+1$ through $m$ continue to use their previous policies. This transformation reduces a single, massive optimization problem into $m$ smaller, manageable sub-problems.
3.2 Approximate Linear Programming (ALP)
To manage the state space, the framework utilizes function approximation. The value function is represented as a linear combination of a predefined set of "basis functions." By solving a Linear Program to determine the optimal weights for these functions, the algorithm avoids the need to compute values for every individual state. This approach significantly reduces the dimensionality of the problem; in one experiment involving 10 agents, the authors reduced the state-action space by a factor of approximately $3.2 \times 10^{32}$ using only 30 basis functions.
4. Theoretical Guarantees
A critical contribution of this work is the establishment of theoretical bounds on performance. Through Theorems 1 and 2, the authors demonstrate that the error of the policy generated by ADPI is bounded. Specifically, if the function approximation (the basis functions) is sufficiently representative of the true value function, the resulting decentralized policy is guaranteed to remain close to the true optimal policy. This provides a "safety net" that distinguishes ADPI from purely heuristic approximation methods.
5. Experimental Evaluation
The authors validated ADPI using two primary simulated environments:
- Flies-Spiders Task: A 2D grid world where two "spider" agents coordinate to capture two "flies" while avoiding collisions.
- Large-Scale Grid World: A complex environment featuring 2,500 states and up to 10 agents, designed to test the scalability of the algorithm.
5.1 Efficiency and Convergence
In the Flies-Spiders task, ADPI demonstrated remarkable efficiency, performing 9 times faster than standard Dynamic Programming for finite horizons and over 19 times faster than standard Policy Iteration for infinite horizons. Furthermore, ADPI showed superior convergence properties; in the infinite horizon spider task, the algorithm converged in a single iteration, whereas regular Policy Iteration required 200 iterations.
5.2 Performance and Scalability
Despite the use of approximations, ADPI achieved average rewards that met or exceeded those of exact methods. It significantly outperformed other decentralized benchmarks, such as "Fully Decentralized DP/PI," particularly as the number of agents increased.
6. Conclusion and Future Directions
The ADPI framework provides a robust solution for scaling multi-agent coordination by decoupling state and action space complexities. While the current implementation relies on expert-selected basis functions and requires "weak communication" between agents during updates, it sets a strong foundation for future research. Potential extensions include the automated discovery of basis functions via deep learning and the adaptation of these techniques to competitive, general-sum game settings.
Summary updated