Decision Making in Team-Adversary Games with Combinatorial Action Space
The team-adversary game simulates many real-world scenarios in which a team of agents competes cooperatively against an adversary. However, decision-making in this type of game is a big challenge since the joint action space of the team is combinatorial and exponentially related to the number of tea...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Tsinghua University Press
2023-12-01
|
| Series: | CAAI Artificial Intelligence Research |
| Subjects: | |
| Online Access: | https://www.sciopen.com/article/10.26599/AIR.2023.9150023 |
| _version_ | 1797202636155387904 |
|---|---|
| author | Shuxin Li Youzhi Zhang Xinrun Wang Wanqi Xue Bo An |
| author_facet | Shuxin Li Youzhi Zhang Xinrun Wang Wanqi Xue Bo An |
| author_sort | Shuxin Li |
| collection | DOAJ |
| description | The team-adversary game simulates many real-world scenarios in which a team of agents competes cooperatively against an adversary. However, decision-making in this type of game is a big challenge since the joint action space of the team is combinatorial and exponentially related to the number of team members. It also hampers the existing equilibrium finding algorithms from solving team-adversary games efficiently. To solve this issue caused by the combinatorial action space, we propose a novel framework based on Counterfactual Regret Minimization (CFR) framework: CFR-MIX. Firstly, we propose a new strategy representation to replace the traditional joint action strategy by using the individual action strategies of all the team members, which can significantly reduce the strategy space. To maintain the cooperation between team members, a strategy consistency relationship is proposed. Then, we transform the consistency relationship of the strategy to the regret consistency for computing the equilibrium strategy with the new strategy representation under the CFR framework. To guarantee the regret consistency relationship, a product-form decomposition method over cumulative regret values is proposed. To implement this decomposition method, our CFR-MIX framework employs a mixing layer under the CFR framework to get the final decision strategy for the team, i.e., the Nash equilibrium strategy. Finally, we conduct experiments on games in different domains. Extensive results show that CFR-MIX significantly outperforms state-of-the-art algorithms. We hope it can help the team make decisions in large-scale team-adversary games. |
| first_indexed | 2024-04-24T08:06:35Z |
| format | Article |
| id | doaj.art-e20b4542dfb240c7bef9ffee93792f39 |
| institution | Directory Open Access Journal |
| issn | 2097-194X |
| language | English |
| last_indexed | 2024-04-24T08:06:35Z |
| publishDate | 2023-12-01 |
| publisher | Tsinghua University Press |
| record_format | Article |
| series | CAAI Artificial Intelligence Research |
| spelling | doaj.art-e20b4542dfb240c7bef9ffee93792f392024-04-17T10:29:52ZengTsinghua University PressCAAI Artificial Intelligence Research2097-194X2023-12-012915002310.26599/AIR.2023.9150023Decision Making in Team-Adversary Games with Combinatorial Action SpaceShuxin Li0Youzhi Zhang1Xinrun Wang2Wanqi Xue3Bo An4School of Computer Science and Engineering, Nanyang Technological University, Singapore 639798, SingaporeCentre for Artificial Intelligence and Robotics, Hong Kong Institute of Science & Innovation, Chinese Academy of Sciences, Hong Kong 999077, ChinaSchool of Computer Science and Engineering, Nanyang Technological University, Singapore 639798, SingaporeSchool of Computer Science and Engineering, Nanyang Technological University, Singapore 639798, SingaporeSchool of Computer Science and Engineering, Nanyang Technological University, Singapore 639798, SingaporeThe team-adversary game simulates many real-world scenarios in which a team of agents competes cooperatively against an adversary. However, decision-making in this type of game is a big challenge since the joint action space of the team is combinatorial and exponentially related to the number of team members. It also hampers the existing equilibrium finding algorithms from solving team-adversary games efficiently. To solve this issue caused by the combinatorial action space, we propose a novel framework based on Counterfactual Regret Minimization (CFR) framework: CFR-MIX. Firstly, we propose a new strategy representation to replace the traditional joint action strategy by using the individual action strategies of all the team members, which can significantly reduce the strategy space. To maintain the cooperation between team members, a strategy consistency relationship is proposed. Then, we transform the consistency relationship of the strategy to the regret consistency for computing the equilibrium strategy with the new strategy representation under the CFR framework. To guarantee the regret consistency relationship, a product-form decomposition method over cumulative regret values is proposed. To implement this decomposition method, our CFR-MIX framework employs a mixing layer under the CFR framework to get the final decision strategy for the team, i.e., the Nash equilibrium strategy. Finally, we conduct experiments on games in different domains. Extensive results show that CFR-MIX significantly outperforms state-of-the-art algorithms. We hope it can help the team make decisions in large-scale team-adversary games.https://www.sciopen.com/article/10.26599/AIR.2023.9150023decision makingteam-adversary gamesnash equilibriumcounterfactual regret minimization (cfr) |
| spellingShingle | Shuxin Li Youzhi Zhang Xinrun Wang Wanqi Xue Bo An Decision Making in Team-Adversary Games with Combinatorial Action Space CAAI Artificial Intelligence Research decision making team-adversary games nash equilibrium counterfactual regret minimization (cfr) |
| title | Decision Making in Team-Adversary Games with Combinatorial Action Space |
| title_full | Decision Making in Team-Adversary Games with Combinatorial Action Space |
| title_fullStr | Decision Making in Team-Adversary Games with Combinatorial Action Space |
| title_full_unstemmed | Decision Making in Team-Adversary Games with Combinatorial Action Space |
| title_short | Decision Making in Team-Adversary Games with Combinatorial Action Space |
| title_sort | decision making in team adversary games with combinatorial action space |
| topic | decision making team-adversary games nash equilibrium counterfactual regret minimization (cfr) |
| url | https://www.sciopen.com/article/10.26599/AIR.2023.9150023 |
| work_keys_str_mv | AT shuxinli decisionmakinginteamadversarygameswithcombinatorialactionspace AT youzhizhang decisionmakinginteamadversarygameswithcombinatorialactionspace AT xinrunwang decisionmakinginteamadversarygameswithcombinatorialactionspace AT wanqixue decisionmakinginteamadversarygameswithcombinatorialactionspace AT boan decisionmakinginteamadversarygameswithcombinatorialactionspace |