Timezone: »

 
Spotlight
Self-Organized Polynomial-Time Coordination Graphs
Qianlan Yang · Weijun Dong · Zhizhou Ren · Jianhao Wang · Tonghan Wang · Chongjie Zhang

Tue Jul 19 02:05 PM -- 02:10 PM (PDT) @ Room 318 - 320
in RL: Multi-agent »

Coordination graph is a promising approach to model agent collaboration in multi-agent reinforcement learning. It conducts a graph-based value factorization and induces explicit coordination among agents to complete complicated tasks. However, one critical challenge in this paradigm is the complexity of greedy action selection with respect to the factorized values. It refers to the decentralized constraint optimization problem (DCOP), which and whose constant-ratio approximation are NP-hard problems. To bypass this systematic hardness, this paper proposes a novel method, named Self-Organized Polynomial-time Coordination Graphs (SOP-CG), which uses structured graph classes to guarantee the accuracy and the computational efficiency of collaborated action selection. SOP-CG employs dynamic graph topology to ensure sufficient value function expressiveness. The graph selection is unified into an end-to-end learning paradigm. In experiments, we show that our approach learns succinct and well-adapted graph topologies, induces effective coordination, and improves performance across a variety of cooperative multi-agent tasks.

Author Information

Qianlan Yang (Tsinghua University)
Weijun Dong (Tsinghua University)
Zhizhou Ren (University of Illinois at Urbana-Champaign)
Jianhao Wang (Tsinghua University)
Tonghan Wang (Tsinghua University)
Chongjie Zhang (Tsinghua University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors