Action Dependency Graphs for Globally Optimal Coordinated Reinforcement Learning
This work addresses scalability challenges in multi-agent reinforcement learning for researchers and practitioners, offering a theoretical and algorithmic framework that is incremental but enhances existing methods.
The paper tackles the computational scalability issue of action-dependent policies in multi-agent reinforcement learning by introducing action dependency graphs (ADGs) to model inter-agent dependencies, proving that sparse ADGs can achieve global optimality under specific conditions and demonstrating empirical robustness in complex environments.
Action-dependent individual policies, which incorporate both environmental states and the actions of other agents in decision-making, have emerged as a promising paradigm for achieving global optimality in multi-agent reinforcement learning (MARL). However, the existing literature often adopts auto-regressive action-dependent policies, where each agent's policy depends on the actions of all preceding agents. This formulation incurs substantial computational complexity as the number of agents increases, thereby limiting scalability. In this work, we consider a more generalized class of action-dependent policies, which do not necessarily follow the auto-regressive form. We propose to use the `action dependency graph (ADG)' to model the inter-agent action dependencies. Within the context of MARL problems structured by coordination graphs, we prove that an action-dependent policy with a sparse ADG can achieve global optimality, provided the ADG satisfies specific conditions specified by the coordination graph. Building on this theoretical foundation, we develop a tabular policy iteration algorithm with guaranteed global optimality. Furthermore, we integrate our framework into several SOTA algorithms and conduct experiments in complex environments. The empirical results affirm the robustness and applicability of our approach in more general scenarios, underscoring its potential for broader MARL challenges.