Proceedings

Asynchronous Credit Assignment for Multi-Agent Reinforcement Learning

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 170-178.

https://doi.org/10.24963/ijcai.2025/20

Abstract

Credit assignment is a critical problem in multi-agent reinforcement learning (MARL), aiming to identify agents' marginal contributions for optimizing cooperative policies. Current credit assignment methods typically assume synchronous decision-making among agents. However, many real-world scenarios require agents to act asynchronously without waiting for others. This asynchrony introduces conditional dependencies between actions, which pose great challenges to current methods. To address this issue, we propose an asynchronous credit assignment framework, incorporating a Virtual Synchrony Proxy (VSP) mechanism and a Multiplicative Value Decomposition (MVD) algorithm. VSP enables physically asynchronous actions to be virtually synchronized during credit assignment. We theoretically prove that VSP preserves both task equilibrium and algorithm convergence. Furthermore, MVD leverages multiplicative interactions to effectively model dependencies among asynchronous actions, offering theoretical advantages in handling asynchronous tasks. Extensive experiments show that our framework consistently outperforms state-of-the-art MARL methods on challenging tasks while providing improved interpretability for asynchronous cooperation.

  1. [Amato et al., 2019] Christopher Amato, George Konidaris, Leslie P Kaelbling, and Jonathan P How. Modeling and planning with macro-actions in decentralized pomdps. Journal of Artificial Intelligence Research, 64:817-859, 2019.
  2. [Arulkumaran et al., 2019] Kai Arulkumaran, Antoine Cully, and Julian Togelius. Alphastar: An evolutionary computation perspective. In Proceedings of the genetic and evolutionary computation conference companion, pages 314-315, 2019.
  3. [Chen et al., 2021] Yuxin Chen, Hejun Wu, Yongheng Liang, and Guoming Lai. Varlenmarl: A framework of variable-length time-step multi-agent reinforcement learn- ing for cooperative charging in sensor networks. In 2021 18th Annual IEEE International Conference on Sensing, Communication, and Networking, pages 1-9. IEEE, 2021.
  4. [Daganzo and Ouyang, 2019] Carlos F Daganzo and Yan- feng Ouyang. Public transportation systems: Principles of system design, operations planning and real-time con- trol. World Scientific, 2019.
  5. [de Witt et al., 2020] Christian Schroeder de Witt, Tarun Gupta, Denys Makoviichuk, Viktor Makoviychuk, Philip H. S. Torr, Mingfei Sun, and Shimon Whiteson. Is inde- pendent learning all you need in the starcraft multi-agent challenge?, 2020.
  6. [Dolev et al., 2018] Shlomi Dolev, Chryssis Georgiou, Ioan- nis Marcoullis, and Elad M. Schiller. Practically-self- stabilizing virtual synchrony. Journal of Computer and System Sciences, 96:50-73, 2018.
  7. [Foerster et al., 2018] Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Proceedings of the AAAI conference on artificial intelli- gence, volume 32, 2018.
  8. [Ha et al., 2017] David Ha, Andrew M. Dai, and Quoc V. Le. Hypernetworks. In International Conference on Learning Representations, 2017.
  9. [Hastie, 2017] Trevor J Hastie. Generalized additive mod- els. In Statistical models in S, pages 249-307. Routledge, 2017.
  10. [Jayakumar et al., 2020] Siddhant M. Jayakumar, Woj- ciech M. Czarnecki, Jacob Menick, Jonathan Schwarz, Jack Rae, Simon Osindero, Yee Whye Teh, Tim Harley, and Razvan Pascanu. Multiplicative interactions and where to find them. In International Conference on Learning Representations, 2020.
  11. [Jia et al., 2020] Hangtian Jia, Yujing Hu, Yingfeng Chen, Chunxu Ren, Tangjie Lv, Changjie Fan, and Chongjie Zhang. Fever basketball: A complex, flexible, and asyn- chronized sports game environment for multi-agent rein- forcement learning, 2020.
  12. [Li et al., 2022] Jiahui Li, Kun Kuang, Baoxiang Wang, Fu- rui Liu, Long Chen, Changjie Fan, Fei Wu, and Jun Xiao. Deconfounded value decomposition for multi-agent rein- forcement learning. In International Conference on Ma- chine Learning, pages 12843-12856. PMLR, 2022.
  13. [Li et al., 2024] Xinran Li, Zifan Liu, Shibo Chen, and Jun Zhang. Individual contributions as intrinsic exploration scaffolds for multi-agent reinforcement learning. In Inter- national Conference on Machine Learning, 2024.
  14. [Liang et al., 2022] Yongheng Liang, Hejun Wu, and Haitao Wang. ASM-PPO: Asynchronous and scalable multi-agent ppo for cooperative charging. In Proceedings of the 21st International Conference on Autonomous Agents and Mul- tiagent Systems, pages 798-806, 2022.
  15. [Liang et al., 2023] Yongheng Liang, Hejun Wu, and Haitao Wang. Asynchronous multi-agent reinforcement learning for collaborative partial charging in wireless rechargeable sensor networks. IEEE Transactions on Mobile Comput- ing, 2023.
  16. [Liu et al., 2023] Zichuan Liu, Yuanyang Zhu, and Chunlin Chen. NA 2 Q: Neural attention additive model for inter- pretable multi-agent q-learning. In International Confer- ence on Machine Learning, pages 22539-22558. PMLR, 2023.
  17. [Oliehoek et al., 2008] Frans A Oliehoek, Matthijs TJ Spaan, and Nikos Vlassis. Optimal and approximate q- value functions for decentralized pomdps. Journal of Ar- tificial Intelligence Research, 32:289-353, 2008.
  18. [Oliehoek et al., 2016] Frans A Oliehoek, Christopher Am- ato, et al. A concise introduction to decentralized POMDPs, volume 1. Springer, 2016.
  19. [Oroojlooy and Hajinezhad, 2023] Afshin Oroojlooy and Davood Hajinezhad. A review of cooperative multi-agent deep reinforcement learning. Applied Intelligence, 53(11):13677-13722, 2023.
  20. [Rashid et al., 2020] Tabish Rashid, Mikayel Samvelyan, Christian Schroeder De Witt, Gregory Farquhar, Jakob Fo- erster, and Shimon Whiteson. Monotonic value function factorisation for deep multi-agent reinforcement learning. Journal of Machine Learning Research, 21(178):1-51, 2020.
  21. [Rumelhart and McClelland, 1987] David E. Rumelhart and James L. McClelland. A General Framework for Parallel Distributed Processing, pages 45-76. 1987.
  22. [Samvelyan et al., 2019] Mikayel Samvelyan, Tabish Rashid, Christian Schröder de Witt, Gregory Farquhar, Nantas Nardelli, Tim G. J. Rudner, Chia-Man Hung, Philip H. S. Torr, Jakob N. Foerster, and Shimon White- son. The starcraft multi-agent challenge. In Proceedings of the International Conference on Autonomous Agents and MultiAgent Systems, pages 2186-2188, 2019.
  23. [Shapley, 1953] Lloyd S Shapley. A value for n-person games. 1953.
  24. [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.
  25. [Sundararajan et al., 2017] Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep net- works. In International conference on machine learning, pages 3319-3328. PMLR, 2017.
  26. [Sunehag et al., 2018] Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinicius Zam- baldi, Max Jaderberg, Marc Lanctot, Nicolas Son- nerat, Joel Z. Leibo, Karl Tuyls, and Thore Grae- pel. Value-decomposition networks for cooperative multi- agent learning based on team reward. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, page 2085-2087, 2018.
  27. [Theocharous and Kaelbling, 2003] Georgios Theocharous and Leslie Kaelbling. Approximate planning in pomdps with macro-actions. Advances in neural information pro- cessing systems, 16, 2003.
  28. [Wang and Sun, 2021] Jiawei Wang and Lijun Sun. Re- ducing bus bunching with asynchronous multi-agent rein- forcement learning. In Proceedings of the Thirtieth Inter- national Joint Conference on Artificial Intelligence,, pages 426-433, 2021. IJCAI
  29. [Wang et al., 2016] Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Hasselt, Marc Lanctot, and Nando Freitas. Duel- ing network architectures for deep reinforcement learning. In International conference on machine learning, pages 1995-2003. PMLR, 2016.
  30. [Wang et al., 2020a] Jianhong Wang, Yuan Zhang, Tae- Kyun Kim, and Yunjie Gu. Shapley q-value: A local re- ward approach to solve global reward games. In Proceed- ings of the AAAI Conference on Artificial Intelligence, vol- ume 34, pages 7285-7292, 2020.
  31. [Wang et al., 2020b] Rose E Wang, Sarah A Wu, James A Evans, Joshua B Tenenbaum, David C Parkes, and Max Kleiman-Weiner. Too many cooks: Coordinating multi- agent collaboration through inverse planning. 2020.
  32. [Wang et al., 2021] Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjie Zhang. QPLEX: Duplex duel- ing multi-agent q-learning. In International Conference on Learning Representations, 2021.
  33. [Wang et al., 2022] Jianhong Wang, Yuan Zhang, Yunjie Gu, and Tae-Kyun Kim. Shaq: Incorporating shapley value theory into multi-agent q-learning. Advances in Neural Information Processing Systems, 35:5941-5954, 2022.
  34. [Wen et al., 2019] Ying Wen, Yaodong Yang, Rui Luo, Jun Wang, and Wei Pan. Probabilistic recursive reasoning for multi-agent reinforcement learning. In International Con- ference on Learning Representations, 2019.
  35. [Wolpert and Tumer, 2001] David H Wolpert and Kagan Tumer. Optimal payoff functions for members of collec- tives. Advances in Complex Systems, 4(02n03):265-279, 2001.
  36. [Xiao et al., 2022] Yuchen Xiao, Weihao Tan, and Christo- pher Amato. Asynchronous actor-critic for multi-agent reinforcement learning. Advances in Neural Information Processing Systems, 35:4385-4400, 2022.
  37. [Yang et al., 2020a] Yaodong Yang, Jianye Hao, Guangy- ong Chen, Hongyao Tang, Yingfeng Chen, Yujing Hu, Changjie Fan, and Zhongyu Wei. Q-value path decompo- sition for deep multiagent reinforcement learning. In Inter- national Conference on Machine Learning, pages 10706- 10715. PMLR, 2020.
  38. [Yang et al., 2020b] Yaodong Yang, Jianye Hao, Ben Liao, Kun Shao, Guangyong Chen, Wulong Liu, and Hongyao Tang. Qatten: A general framework for cooperative multi- agent reinforcement learning, 2020.
  39. [Yao et al., 2021] Meng Yao, Qiyue Yin, Jun Yang, Tong- tong Yu, Shengqi Shen, Junge Zhang, Bin Liang, and Kaiqi Huang. The partially observable asynchronous multi-agent cooperation challenge, 2021.
  40. [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.
  41. [Zhou et al., 2020] Meng Zhou, Ziyu Liu, Pengwei Sui, Yix- uan Li, and Yuk Ying Chung. Learning implicit credit as- signment for cooperative multi-agent reinforcement learn- ing. Advances in neural information processing systems, 33:11853-11864, 2020.
  42. [Zhou et al., 2023] Xiaobo Zhou, Zhihui Ke, and Tie Qiu. Recommendation-driven multi-cell cooperative caching: A multi-agent reinforcement learning approach. IEEE Transactions on Mobile Computing, 2023.

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

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