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.
Figures & tables
Figure 1: Simple regret of CB-MCTS and Dec-MCTS in the multi-agent D-chain problem with D=10 and 2 agents.
Figure 2: Performance comparison on the Frozen Lake benchmark.
Figure 3: Performance comparison in the Oil Rigs Inspection problem.
Figure 4: An illustration of the D-chain problem on a m-ary tree for multi-agent. Blue nodes are decision states, which can have at most m children; and gray nodes are terminal states with corresponding rewards.
Figure 5: Results of Dec-MCTS on the D-chain problem with D=10 and 2 agents for varying exploration bias ε and discount factor γ .
Figure 6: Results of CB-MCTS on the D-chain problem with D=10 and 2 agents for varying exploration bias ε , discount factor γ , and search temperature α .
Figure 7: Results of Dec-MCTS on the D-chain problem with D=10 and 3 agents for varying exploration bias ε and discount factor γ .
Figure 8: Results of CB-MCTS on the D-chain problem with D=10 and 3 agents for varying exploration bias ε and discount factor γ , and search temperature α .
Figure 9: Results of Dec-MCTS on the D-chain problem with D=20 and 2 agents for varying exploration bias ε and discount factor γ .
Figure 10: Results of CB-MCTS on the D-chain problem with D=20 and 2 agents for varying exploration bias ε and discount factor γ , and search temperature α .
Figure 11: Results of Dec-MCTS on the modified D-chain problem with D=20 and 2 agents for varying exploration bias ε and discount factor γ .
Figure 12: Results of CB-MCTS on the modified D-chain problem with D=20 and 2 agents for varying exploration bias ε and discount factor γ , and search temperature α .
Algorithm
ε
γ
αinit
Dec-MCTS
100
0.99
-
CB-MCTS
0.5
0.9
1
CAR-DENTS
0.5
-
1
Table 1: Parameters used for the experiments in the main paper.
Figure 13: Environment maps used for the Frozen Lake experiments.
Figure 14: Environment used for parameter search for the Oil Rigs Inspection problem. Yellow star is the starting location of all agents, grey dots are the locations of the oil rigs, and red circles are observation ranges of the oil rigs requiring inspection.
Figure 15: Performance of CAR-DENTS across different numbers of planning iterations. Results are with a 95% confidence interval.
Algorithm
ε
γ
αinit
Dec-MCTS
100
0.6
-
CB-MCTS
0.5
0.8
0.01
CAR-DENTS
0.5
-
10
Table 2: Parameters used for the experiments in the main paper.
Figure 16: Results of FA-MCTS on the D-chain problem with D=10 and 2 agents for varying exploration bias ε and discount factor γ .
Figure 17: Results of NE-MCTS on the D-chain problem with D=10 and 2 agents for varying exploration bias ε , discount factor γ , and search temperature α .
Figure 18: Results of FA-MCTS on the D-chain problem with D=10 and 3 agents for varying exploration bias ε and discount factor γ .
Figure 19: Results of NE-MCTS on the D-chain problem with D=10 and 3 agents for varying exploration bias ε and discount factor γ , and search temperature α .
Figure 20: Results of FA-MCTS on the D-chain problem with D=20 and 2 agents for varying exploration bias ε and discount factor γ .
Figure 21: Results of NE-MCTS on the D-chain problem with D=20 and 2 agents for varying exploration bias ε and discount factor γ , and search temperature α .
Figure 22: Results of FA-MCTS on the modified D-chain problem with D=20 and 2 agents for varying exploration bias ε and discount factor γ .
Figure 23: Results of NE-MCTS on the modified D-chain problem with D=20 and 2 agents for varying exploration bias ε and discount factor γ , and search temperature α .
Figure 24: Performances of different algorithms in the Frozen Lake problem: Joint scores (a), Probability that at least one goal is reached by any agent (b), and Probability that both goals are reached (c). Results are with 95% confidence interval.
Figure 25: Impact of different system parameters on the algorithms’ performances in the Oil Rigs Inspection problem: Planning iterations (a), Number of agents (b), and Travel budget (c). Results are with 95% confidence interval.
Efficient coordination under limited communication remains a key challenge in decentralized multi-robot exploration. While centralized approaches benefit from global information sharing, they are often impractical in large-scale or communication-constrained environments. Existing Monte Carlo Tree Search (MCTS)-based approaches, such as Decentralized Monte Carlo Exploration (DMCE), enable decentralized planning by taking peer intent into account. This peer intent is obtained by communicating sequences of planned waypoints with robots within direct communication range. In this work, we extend this idea by introducing Probabilistic Peer Intent (PPI), which converts peer trajectories into a continuous spatial representation of predicted intent and incorporates it into local MCTS action evaluation. We additionally study the effects of sharing peer intent beyond direct communication range by propagating plans over multiple hops. Experiments across multiple simulated environments and team sizes show that PPI and Multi-hop propagation can each improve decentralized exploration, with their relative benefits depending on environment structure and team size. We also demonstrate the real-world deployment of our method on three robots operating in different environment types.
Monte Carlo Tree Search (MCTS) scales poorly in cooperative multi-agent domains because expansion must consider an exponentially large set of joint actions, severely limiting exploration under realistic search budgets. We propose NonZero, which keeps multi-agent MCTS tractable by running surrogate-guided selection over a low-dimensional nonlinear representation using an interaction-guided proposal rule, instead of directly exploring the full joint-action space. Our exploration uses an interaction score: single-agent deviations are ranked by predicted gain, while two-agent deviations are scored by a mixed-difference measure that reveals coordination benefits even when no single agent can improve alone. We formalize candidate proposal as a bandit problem over local deviations and derive a proposal rule, NonZero, with a sublinear local-regret guarantee for reaching approximate graph-local optima without enumerating the joint-action space. Empirically, NonZero improves sample efficiency and final performance on MatGame, SMAC, and SMACv2 relative to strong model-based and model-free baselines under matched search budgets.
Sizhe Tang, Zuyuan Zhang, Mahdi Imani +1
The George Washington University · Northeastern University
Monte Carlo Tree Search (MCTS) is a powerful framework for solving complex decision-making problems, yet it often relies on the assumption that the simulator and the real-world dynamics are identical. Although this assumption helps achieve the success of MCTS in games like Chess, Go, and Shogi, the real-world scenarios incur ambiguity due to their modeling mismatches in low-fidelity simulators. In this work, we present a new robust variant of MCTS that mitigates dynamical model ambiguities. Our algorithm addresses transition dynamics and reward distribution ambiguities to bridge the gap between simulation-based planning and real-world deployment. We incorporate a robust power mean backup operator and carefully designed exploration bonuses to ensure finite-sample convergence at every node in the search tree. We show that our algorithm achieves a convergence rate of O(n−1/2) for the value estimation at the root node, comparable to that of standard MCTS. Finally, we provide empirical evidence that our method achieves robust performance in planning problems even under significant ambiguity in the underlying reward distribution and transition dynamics.
Tuan Dam, Kishan Panaganti, Brahim Driss +1
Hanoi University of Science and Technology, Hanoi, Vietnam · Department of Computing and Mathematical Sciences, California Institute of Technology, Pasadena, CA, USA · Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189-CRIStAL