Proceedings

Deep Hierarchical Communication Graph in Multi-Agent Reinforcement Learning

Download BibTeX Cite

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence. Main Track. Pages 208-216.

https://doi.org/10.24963/ijcai.2023/24

Abstract

Sharing intentions is crucial for efficient cooperation in communication-enabled multi-agent reinforcement learning. Recent work applies static or undirected graphs to determine the order of interaction. However, the static graph is not general for complex cooperative tasks, and the parallel message-passing update in the undirected graph with cycles cannot guarantee convergence. To solve this problem, we propose Deep Hierarchical Communication Graph (DHCG) to learn the dependency relationships between agents based on their messages. The relationships are formulated as directed acyclic graphs (DAGs), where the selection of the proper topology is viewed as an action and trained in an end-to-end fashion. To eliminate the cycles in the graph, we apply an acyclicity constraint as intrinsic rewards and then project the graph in the admissible solution set of DAGs. As a result, DHCG removes redundant communication edges for cost improvement and guarantees convergence. To show the effectiveness of the learned graphs, we propose policy-based and value-based DHCG. Policy-based DHCG factorizes the joint policy in an auto-regressive manner, and value-based DHCG factorizes the joint value function to individual value functions and pairwise payoff functions. Empirical results show that our method improves performance across various cooperative multi-agent tasks, including Predator-Prey, Multi-Agent Coordination Challenge, and StarCraft Multi-Agent Challenge.

  1. [Bargiacchi et al., 2018] Eugenio Bargiacchi, Timothy Ver- straeten, Diederik Roijers, Ann Nowé, and Hado Hasselt. Learning to coordinate with coordination graphs in re- peated single-stage multi-agent decision problems. In In- ternational Conference on Machine Learning, pages 482- 490. PMLR, 2018.
  2. [Bertsekas, 2019] Dimitri P. Bertsekas. Multiagent roll- out algorithms and reinforcement learning. CoRR, abs/1910.00120, 2019.
  3. [Böhmer et al., 2020] Wendelin Böhmer, Vitaly Kurin, and Shimon Whiteson. Deep coordination graphs. In Interna- tional Conference on Machine Learning, pages 980-991.
  4. PMLR, 2020.
  5. [Conte and Sichman, 2002] Rosaria Conte and Jaime Simão Sichman. Dependence graphs: Dependence within and between groups. Computational & Mathematical Organi- zation Theory, 8(2):87-112, 2002.
  6. [Das et al., 2019] Abhishek Das, Théophile Gervet, Joshua Romoff, Dhruv Batra, Devi Parikh, Mike Rabbat, and Joelle Pineau. Tarmac: Targeted multi-agent communi- cation. In International Conference on Machine Learning, pages 1538-1546. PMLR, 2019.
  7. [Dimakopoulou and Van Roy, 2018] Maria Dimakopoulou and Benjamin Van Roy. Coordinated exploration in concurrent reinforcement learning. In International Conference on Machine Learning, pages 1271-1279.
  8. PMLR, 2018.
  9. [Dimakopoulou et al., 2018] Maria Dimakopoulou, Ian Os- band, and Benjamin Van Roy. Scalable coordinated ex- ploration in concurrent reinforcement learning. Advances in Neural Information Processing Systems, 31:4223-4232, 2018.
  10. [Fu et al., 2022] Wei Fu, Chao Yu, Zelai Xu, Jiaqi Yang, and Yi Wu. Revisiting some common practices in cooperative multi-agent reinforcement learning. In International Con- ference on Machine Learning, pages 6863-6877. PMLR, 2022.
  11. [Guestrin et al., 2002] Carlos Guestrin, Michail Lagoudakis, and Ronald Parr. Coordinated reinforcement learning. In International Conference on Machine Learning, pages 227-234. Citeseer, 2002.
  12. [Hernandez-Leal et al., 2019] Pablo Hernandez-Leal, Bilal Kartal, and Matthew E Taylor. A survey and critique of multiagent deep reinforcement learning. In International Conference on Autonomous Agents and Multi-Agent Sys- tems, pages 750-797, 2019.
  13. [Jiang and Lu, 2018] Jiechuan Jiang and Zongqing Lu. Learning attentional communication for multi-agent coop- eration. Advances in Neural Information Processing Sys- tems, 31:7254-7264, 2018.
  14. [Kim et al., 2021] Woojun Kim, Jongeui Park, and Youngchul Sung. Communication in multi-agent re- inforcement learning: Intention sharing. In International Conference on Learning Representations, 2021.
  15. [Kuba et al., 2022] Jakub Grudzien Kuba, Ruiqing Chen, Muning Wen, Ying Wen, Fanglei Sun, Jun Wang, and Yaodong Yang. Trust region policy optimisation in multi- agent reinforcement learning. In International Conference on Learning Representations, 2022.
  16. [Li et al., 2019] Xihan Li, Jia Zhang, Jiang Bian, Yunhai Tong, and Tie-Yan Liu. A cooperative multi-agent rein- forcement learning framework for resource balancing in complex logistics network. In International Conference on Autonomous Agents and Multi-Agent Systems, pages 980- 988, 2019.
  17. [Li et al., 2021] Sheng Li, Jayesh K Gupta, Peter Morales, Ross Allen, and Mykel J Kochenderfer. Deep implicit co- ordination graphs for multi-agent reinforcement learning. In International Conference on Autonomous Agents and Multi-Agent Systems, pages 764-772, 2021.
  18. [Lillicrap et al., 2016] Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In International Conference on Learning Representations, 2016.
  19. [Liu et al., 2020] Yong Liu, Weixun Wang, Yujing Hu, Jianye Hao, Xingguo Chen, and Yang Gao. Multi-agent game abstraction via graph attention neural network. In Proceedings of the AAAI Conference on Artificial Intelli- gence, pages 34(05):7211-7218, 2020.
  20. [Oliehoek and Amato, 2016] Frans A. Oliehoek and Christo- pher Amato. A Concise Introduction to Decentral- ized POMDPs. Springer Briefs in Intelligent Systems. Springer, 2016.
  21. [Palanisamy, 2020] Praveen Palanisamy. Multi-agent con- nected autonomous driving using deep reinforcement learning. In International Joint Conference on Neural Net- works, pages 1-7. IEEE, 2020.
  22. [Pearl, 1989] Judea Pearl. Probabilistic reasoning in intel- ligent systems -networks of plausible inference. Morgan Kaufmann series in representation and reasoning. Morgan Kaufmann, 1989.
  23. [Rashid et al., 2018] Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In International Conference on Machine Learning, pages 4295-4304. PMLR, 2018.
  24. [Rashid et al., 2020] Tabish Rashid, Gregory Farquhar, Bei Peng, and Shimon Whiteson. Weighted qmix: Expand- ing monotonic value function factorisation for deep multi- agent reinforcement learning. Advances in Neural Infor- mation Processing Systems, 33:10199-10210, 2020.
  25. [Samvelyan et al., 2019] Mikayel Samvelyan, Tabish Rashid, Christian Schröder de Witt, Gregory Farquhar, Nantas Nardelli, Tim GJ Rudner, Chia-Man Hung, Philip HS Torr, Jakob N Foerster, and Shimon Whiteson. The starcraft multi-agent challenge. In International Conference on Autonomous Agents and Multi-Agent Systems, pages 2186-2188, 2019.
  26. [Schulman et al., 2016] John Schulman, Philipp Moritz, Sergey Levine, Michael I. Jordan, and Pieter Abbeel. High-dimensional continuous control using generalized advantage estimation. In International Conference on Learning Representations, 2016.
  27. [Schulman et al., 2017] John Schulman, Filip Wolski, Pra- fulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. CoRR, abs/1707.06347, 2017.
  28. [Shi et al., 2019] Zhenyu Shi, Runsheng Yu, Xinrun Wang, Rundong Wang, Youzhi Zhang, Hanjiang Lai, and Bo An. Learning expensive coordination: An event-based deep rl approach. In International Conference on Learning Rep- resentations, 2019.
  29. [Son et al., 2019] Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. Qtran: Learn- ing to factorize with transformation for cooperative multi- agent reinforcement learning. In International Conference on Machine Learning, pages 5887-5896. PMLR, 2019.
  30. [Sukhbaatar et al., 2016] Sainbayar Sukhbaatar, Rob Fergus, et al. Learning multiagent communication with backprop- agation. Advances in Neural Information Processing Sys- tems, 29, 2016.
  31. [Wainwright et al., 2002] Martin J Wainwright, Tommi Jaakkola, and Alan Willsky. Exact map estimates by (hy- per) tree agreement. Advances in Neural Information Pro- cessing Systems, 15, 2002.
  32. [Wainwright et al., 2004] Martin Wainwright, Tommi Jaakkola, and Alan Willsky. Tree consistency and bounds on the performance of the max-product algorithm and its generalizations. Statistics and computing, 14(2):143-166, 2004.
  33. [Wang et al., 2019] Tonghan Wang, Jianhao Wang, Chongyi Zheng, and Chongjie Zhang. Learning nearly decom- posable value functions via communication minimization. In International Conference on Learning Representations, 2019.
  34. [Wang et al., 2020] Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjie Zhang. Qplex: Duplex dueling multi-agent q-learning. In International Conference on Learning Representations, 2020.
  35. [Wang et al., 2022] Tonghan Wang, Liang Zeng, Weijun Dong, Qianlan Yang, Yang Yu, and Chongjie Zhang. Context-aware sparse deep coordination graphs. In Inter- national Conference on Learning Representations, 2022.
  36. [Wen et al., 2022] Muning Wen, Jakub Kuba, Runji Lin, Weinan Zhang, Ying Wen, Jun Wang, and Yaodong Yang. Multi-agent reinforcement learning is a sequence model- ing problem. Advances in Neural Information Processing Systems, 35:16509-16521, 2022.
  37. [Yang et al., 2022] Qianlan Yang, Weijun Dong, Zhizhou Ren, Jianhao Wang, Tonghan Wang, and Chongjie Zhang. Self-organized polynomial-time coordination graphs. In International Conference on Machine Learning, pages 24963-24979. PMLR, 2022.
  38. [Yu et al., 2021] Yue Yu, Tian Gao, Naiyu Yin, and Qiang Ji. Dags with no curl: An efficient dag structure learning approach. In International Conference on Machine Learn- ing, pages 12156-12166. PMLR, 2021.
  39. [Yu et al., 2022] Chao Yu, Akash Velu, Eugene Vinitsky, Ji- axuan Gao, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of ppo in cooperative multi-agent games. Advances in Neural Information Processing Sys- tems, 35:24611-24624, 2022.
  40. [Yuan et al., 2022] Lei Yuan, Jianhao Wang, Fuxiang Zhang, Chenghe Wang, Zongzhang Zhang, Yang Yu, and Chongjie Zhang. Multi-agent incentive communication via decentralized teammate modeling. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 36(9):9466-9474, 2022.
  41. [Zhang and Lesser, 2013] Chongjie Zhang and Victor Lesser. Coordinating multi-agent reinforcement learning with limited communication. In International Conference on Autonomous Agents and Multi-Agent Systems, pages 1101-1108, 2013.
  42. [Zhang et al., 2019a] Huichu Zhang, Siyuan Feng, Chang Liu, Yaoyao Ding, Yichen Zhu, Zihan Zhou, Weinan Zhang, Yong Yu, Haiming Jin, and Zhenhui Li. Cityflow: A multi-agent reinforcement learning environment for large scale city traffic scenario. In The world wide web Conference, pages 3620-3624, 2019.
  43. [Zhang et al., 2019b] Sai Qian Zhang, Qi Zhang, and Jieyu Lin. Efficient communication in multi-agent reinforce- ment learning via variance based control. Advances in Neural Information Processing Systems, 32:3230-3239, 2019.
  44. [Zheng et al., 2018] Xun Zheng, Bryon Aragam, Pradeep K Ravikumar, and Eric P Xing. Dags with no tears: Continu- ous optimization for structure learning. Advances in Neu- ral Information Processing Systems, 31:9492-9503, 2018.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards