# MALinZero: Efficient Low-Dimensional Search for Mastering Complex Multi-Agent Planning

arXiv: https://arxiv.org/abs/2511.06142 · HTML: https://mlsanity.com/paper/2511.06142/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 61 references that are in the map.
- First posted on arXiv 8 Nov 2025.

## Builds on (most cited first, 30 of 33)

- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games](https://mlsanity.com/paper/2103.01955/) (2021)
- [The StarCraft Multi-Agent Challenge](https://mlsanity.com/paper/1902.04043/) (2019)
- [Value-Decomposition Networks For Cooperative Multi-Agent Learning](https://mlsanity.com/paper/1706.05296/) (2017)
- [Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2003.08839/) (2020)
- [QTRAN: Learning to Factorize with Transformation for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1905.05408/) (2019)
- [Mastering Atari Games with Limited Data](https://mlsanity.com/paper/2111.00210/) (2021)
- [Weighted QMIX: Expanding Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2006.10800/) (2020)
- [A Survey and Critique of Multiagent Deep Reinforcement Learning](https://mlsanity.com/paper/1810.05587/) (2018)
- [SMACv2: An Improved Benchmark for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2212.07489/) (2022)
- [Off-Policy Multi-Agent Decomposed Policy Gradients](https://mlsanity.com/paper/2007.12322/) (2020)
- [Learning Nearly Decomposable Value Functions Via Communication Minimization](https://mlsanity.com/paper/1910.05366/) (2019)
- [Learning and Planning in Complex Action Spaces](https://mlsanity.com/paper/2104.06303/) (2021)
- [Every Parameter Matters: Ensuring the Convergence of Federated Learning with Dynamic Heterogeneous Models Reduction](https://mlsanity.com/paper/2310.08670/) (2023)
- [MAC-PO: Multi-Agent Experience Replay via Collective Priority Optimization](https://mlsanity.com/paper/2302.10418/) (2023)
- [Deep Generative Models for Offline Policy Learning: Tutorial, Survey, and Perspectives on Future Directions](https://mlsanity.com/paper/2402.13777/) (2024)
- [Modeling Other Players with Bayesian Beliefs for Games with Incomplete Information](https://mlsanity.com/paper/2405.14122/) (2024)
- [Decentralized Monte Carlo Tree Search for Partially Observable Multi-agent Pathfinding](https://mlsanity.com/paper/2312.15908/) (2023)
- [Monte Carlo Tree Search with Boltzmann Exploration](https://mlsanity.com/paper/2404.07732/) (2024)
- [Bayes Adaptive Monte Carlo Tree Search for Offline Model-based Reinforcement Learning](https://mlsanity.com/paper/2410.11234/) (2024)
- [Efficient Multi-agent Reinforcement Learning by Planning](https://mlsanity.com/paper/2405.11778/) (2024)
- [Optimizing Prompt Sequences using Monte Carlo Tree Search for LLM-Based Optimization](https://mlsanity.com/paper/2508.05995/) (2025)
- [Learning from Random Demonstrations: Offline Reinforcement Learning with Importance-Sampled Diffusion Models](https://mlsanity.com/paper/2405.19878/) (2024)
- [Lipschitz Lifelong Monte Carlo Tree Search for Mastering Non-Stationary Tasks](https://mlsanity.com/paper/2502.00633/) (2025)
- [Coordinate-Aligned Multi-Camera Collaboration for Active Multi-Object Tracking](https://mlsanity.com/paper/2202.10881/) (2022)
- [Efficient Monte Carlo Tree Search via On-the-Fly State-Conditioned Action Abstraction](https://mlsanity.com/paper/2406.00614/) (2024)
- [Scalable Anytime Planning for Multi-Agent MDPs](https://mlsanity.com/paper/2101.04788/) (2021)
- [An MCTS-DRL Based Obstacle and Occlusion Avoidance Methodology in Robotic Follow-Ahead Applications](https://mlsanity.com/paper/2309.16884/) (2023)
- [Bayesian Optimization through Gaussian Cox Process Models for Spatio-temporal Data](https://mlsanity.com/paper/2401.14544/) (2024)

## Built on by (most cited first, 5 of 5)

- [Agent Alpha: Tree Search Unifying Generation, Exploration and Evaluation for Computer-Use Agents](https://mlsanity.com/paper/2602.02995/) (2026)
- [Cochain Perspectives on Temporal-Difference Signals for Learning Beyond Markov Dynamics](https://mlsanity.com/paper/2602.06939/) (2026)
- [Operator-Guided Invariance Learning for Continuous Reinforcement Learning](https://mlsanity.com/paper/2605.06500/) (2026)
- [Metric-Gradient Projection for Stable Multi-Agent Policy Learning](https://mlsanity.com/paper/2605.18809/) (2026)
- [ACDZero: MCTS Agent for Mastering Automated Cyber Defense](https://mlsanity.com/paper/2601.02196/) (2026)

## Abstract (arXiv)

Monte Carlo Tree Search (MCTS), which leverages Upper Confidence Bound for Trees (UCTs) to balance exploration and exploitation through randomized sampling, is instrumental to solving complex planning problems. However, for multi-agent planning, MCTS is confronted with a large combinatorial action space that often grows exponentially with the number of agents. As a result, the branching factor of MCTS during tree expansion also increases exponentially, making it very difficult to efficiently explore and exploit during tree search. To this end, we propose MALinZero, a new approach to leverage low-dimensional representational structures on joint-action returns and enable efficient MCTS in complex multi-agent planning. Our solution can be viewed as projecting the joint-action returns into the low-dimensional space representable using a contextual linear bandit problem formulation. We solve the contextual linear bandit problem with convex and μ-smooth loss functions -- in order to place more importance on better joint actions and mitigate potential representational limitations -- and derive a linear Upper Confidence Bound applied to trees (LinUCT) to enable novel multi-agent exploration and exploitation in the low-dimensional space. We analyze the regret of MALinZero for low-dimensional reward functions and propose an (1-tfrac1e)-approximation algorithm for the joint action selection by maximizing a sub-modular objective. MALinZero demonstrates state-of-the-art performance on multi-agent benchmarks such as matrix games, SMAC, and SMACv2, outperforming both model-based and model-free multi-agent reinforcement learning baselines with faster learning speed and better performance.