Simultaneous AlphaZero: Extending Tree Search to Markov Games

2025/12/13 by Becker, Tyler, Sunberg, Zachary
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2512.12486

Abstract

Simultaneous AlphaZero extends the AlphaZero framework to multistep, two-player zero-sum deterministic Markov games with simultaneous actions. At each decision point, joint action selection is resolved via matrix games whose payoffs incorporate both immediate rewards and future value estimates. To handle uncertainty arising from bandit feedback during Monte Carlo Tree Search (MCTS), Simultaneous AlphaZero incorporates a regret-optimal solver for matrix games with bandit feedback. Simultaneous AlphaZero demonstrates robust strategies in a continuous-state discrete-action pursuit-evasion game and satellite custody maintenance scenarios, even when evaluated against maximally exploitative opponents.

Citations

• Stop Regressing: Training Value Functions via Classification for Scalable Deep RL
• Matrix games with bandit feedback
• Improving Regression Performance with Distributional Losses

Related

• Multiplayer AlphaZero
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium
• Multiple Tree for Partially Observable Monte-Carlo Tree Search
• Dual Monte Carlo Tree Search
• MCTS Based on Simple Regret