Reproduce “Action Dependency Graphs for Globally Optimal Coordinated Reinforcement Learning” on OpenResearch

About this paper

Jianglin Ding, Jingcheng Tang, Gangshan Jing

Researchers at Chongqing University developed a theoretical framework demonstrating that sparse Action Dependency Graphs (ADGs), structured by Coordination Graphs, can guarantee global optimality in cooperative Multi-Agent Reinforcement Learning (MARL). Their methodology integrates into existing deep MARL algorithms, showing improved performance and computational efficiency across various cooperative tasks compared to independent policies or dense ADG approaches.

Key insights

• Global optimality in cooperative MARL can be achieved with sparse Action Dependency Graphs (ADGs) if their structure satisfies a specific condition related to the problem's Coordination Graph (CG).
• The proposed G_d-local optimality criterion is a stronger form of optimality that, when combined with the structured sparse ADG, guarantees convergence to the global optimum.
• Explicitly structuring action dependencies according to a problem's underlying coordination graph enables the design of scalable yet theoretically robust multi-agent policies.

Summary by alphaXiv.