Inferring Latent Temporal Sparse Coordination Graph for Multi-Agent
  Reinforcement Learning
Wei Duan Jie Lu Junyu Xuan
Effective agent coordination is crucial in cooperative Multi-Agent
Reinforcement Learning (MARL). While agent cooperation can be represented by
graph structures, prevailing graph learning methods in MARL are limited. They
rely solely on one-step observations, neglecting crucial historical
experiences, leading to deficient graphs that foster redundant or detrimental
information exchanges. Additionally, high computational demands for action-pair
calculations in dense graphs impede scalability. To address these challenges,
we propose inferring a Latent Temporal Sparse Coordination Graph (LTS-CG) for
MARL. The LTS-CG leverages agents' historical observations to calculate an
agent-pair probability matrix, where a sparse graph is sampled from and used
for knowledge exchange between agents, thereby simultaneously capturing agent
dependencies and relation uncertainty. The computational complexity of this
procedure is only related to the number of agents. This graph learning process
is further augmented by two innovative characteristics: Predict-Future, which
enables agents to foresee upcoming observations, and Infer-Present, ensuring a
thorough grasp of the environmental context from limited data. These features
allow LTS-CG to construct temporal graphs from historical and real-time
information, promoting knowledge exchange during policy learning and effective
collaboration. Graph learning and agent training occur simultaneously in an
end-to-end manner. Our demonstrated results on the StarCraft II benchmark
underscore LTS-CG's superior performance.