[2603.02154] Boltzmann-based Exploration for Robust Decentralized Multi-Agent Planning

Computer Science > Multiagent Systems arXiv:2603.02154 (cs) [Submitted on 2 Mar 2026] Title:Boltzmann-based Exploration for Robust Decentralized Multi-Agent Planning Authors:Nhat Nguyen, Duong Nguyen, Gianluca Rizzo, Hung Nguyen View a PDF of the paper titled Boltzmann-based Exploration for Robust Decentralized Multi-Agent Planning, by Nhat Nguyen and 2 other authors View PDF HTML (experimental) Abstract:Decentralized Monte Carlo Tree Search (Dec-MCTS) is widely used for cooperative multi-agent planning but struggles in sparse or skewed reward environments. We introduce Coordinated Boltzmann MCTS (CB-MCTS), which replaces deterministic UCT with a stochastic Boltzmann policy and a decaying entropy bonus for sustained yet focused exploration. While Boltzmann exploration has been studied in single-agent MCTS, applying it in multi-agent systems poses unique challenges. CB-MCTS is the first to address this. We analyze CB-MCTS in the simple-regret setting and show in simulations that it outperforms Dec-MCTS in deceptive scenarios and remains competitive on standard benchmarks, providing a robust solution for multi-agent planning. Comments: Subjects: Multiagent Systems (cs.MA); Artificial Intelligence (cs.AI) Cite as: arXiv:2603.02154 [cs.MA]   (or arXiv:2603.02154v1 [cs.MA] for this version)   https://doi.org/10.48550/arXiv.2603.02154 Focus to learn more arXiv-issued DOI via DataCite (pending registration) Submission history From: Nhat Nguyen [view email] [v1] Mon, 2 Mar 2026 18...