mlsanityData to 7 Oct 2026

Tree Search for Simultaneous Move Games via Equilibrium Approximation

arXiv 2406.10411 ↗First posted 14 Jun 2024cs.MA cs.AIcited by 0

Not on the map. Why?

Abstract (arXiv)

Neural network supported tree-search has shown strong results in a variety of perfect information multi-agent tasks. However, the performance of these methods on partial information games has generally been below competing approaches. Here we study the class of simultaneous-move games, which are a subclass of partial information games which are most similar to perfect information games: both agents know the game state with the exception of the opponent's move, which is revealed only after each agent makes its own move. Simultaneous move games include popular benchmarks such as Google Research Football and Starcraft. In this study we answer the question: can we take tree search algorithms trained through self-play from perfect information settings and adapt them to simultaneous move games without significant loss of performance? We answer this question by deriving a practical method that attempts to approximate a coarse correlated equilibrium as a subroutine within a tree search. Our algorithm works on cooperative, competitive, and mixed tasks. Our results are better than the current best MARL algorithms on a wide range of accepted baseline environments.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 18 of its 26 references that are in the map. First posted on arXiv 14 Jun 2024.

Builds on

18 of 26 references.

References · 18

  1. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,519
  2. 2021The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Gamescited by 903
  3. 2018QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learningcited by 697
  4. 2019The StarCraft Multi-Agent Challengecited by 589
  5. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  6. 2020Is Independent Learning All You Need in the StarCraft Multi-Agent Challenge?cited by 281
  7. 2017A Unified Game-Theoretic Approach to Multiagent Reinforcement Learningcited by 265
  8. 2017Emergence of Grounded Compositional Language in Multi-Agent Populationscited by 257
  9. 2019Google Research Football: A Novel Reinforcement Learning Environmentcited by 257
  10. 2015Multiagent Cooperation and Competition with Deep Reinforcement Learningcited by 180
  11. 2019OpenSpiel: A Framework for Reinforcement Learning in Gamescited by 180
  12. 2016Deep Reinforcement Learning from Self-Play in Imperfect-Information Gamescited by 153
6 more
  1. 2015Explore no more: Improved high-probability regret bounds for non-stochastic banditscited by 120
  2. 2020Game-Theoretic Multiagent Reinforcement Learningcited by 92
  3. 2017Online Reinforcement Learning in Stochastic Gamescited by 67
  4. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
  5. 2021Investigation of Independent Reinforcement Learning Algorithms in Multi-Agent Environmentscited by 5
  6. 2014Empirically Evaluating Multiagent Learning Algorithmscited by 3

Built on by

Not cited yet.