Dynamic Deep Factor Graph for Multi-Agent Reinforcement Learning

Multi-agent reinforcement learning (MARL) requires effective coordination among multiple decision-making agents to achieve joint goals. Approaches based on a global value function face the curse of dimensionality, while fully decomposed centralized training with decentralized execution (CTDE) methods often suffer from relative overgeneralization. Coordination graphs mitigate this issue but typically fail to capture dynamic collaboration patterns that evolve over time and across tasks. We propose Dynamic Deep Factor Graphs (DDFG), a value decomposition algorithm that represents the global value via factor graphs and learns graph structures on the fly through a graph-generation policy, adapting to evolving inter-agent relations. We provide a theoretical upper bound on the approximation error of high-order decompositions and reveal how the maximum order $D$D trades off accuracy against computation, offering guidance for balancing performance and cost. Using max-sum for inference, DDFG efficiently derives joint policies. Experiments on higher-order predator-prey and SMAC show consistent gains over strong value-decomposition baselines, demonstrating improved sample efficiency and robustness in complex settings.