cs.MAMar 2, 2026

Boltzmann-based Exploration for Robust Decentralized Multi-Agent Planning (Extended Version)

Authors: Nhat D. A. Nguyen, Duong D. Nguyen, Gianluca Rizzo, Hung X. Nguyen

Organizations: Adelaide University, Australia · The University of Foggia, Italy · HES-SO Valais, Switzerland, and The University of Turin, Italy

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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.

Figures & tables

Figure 1: Simple regret of CB-MCTS and Dec-MCTS in the multi-agent D-chain problem with D=10D=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 mm children; and gray nodes are terminal states with corresponding rewards.
Figure 5: Results of Dec-MCTS on the D-chain problem with D=10D=10 and 2 agents for varying exploration bias ε\varepsilon and discount factor γ\gamma .
Figure 6: Results of CB-MCTS on the D-chain problem with D=10D=10 and 2 agents for varying exploration bias ε\varepsilon , discount factor γ\gamma , and search temperature α\alpha .
Figure 7: Results of Dec-MCTS on the D-chain problem with D=10D=10 and 3 agents for varying exploration bias ε\varepsilon and discount factor γ\gamma .
Figure 8: Results of CB-MCTS on the D-chain problem with D=10D=10 and 3 agents for varying exploration bias ε\varepsilon and discount factor γ\gamma , and search temperature α\alpha .
Figure 9: Results of Dec-MCTS on the D-chain problem with D=20D=20 and 2 agents for varying exploration bias ε\varepsilon and discount factor γ\gamma .
Figure 10: Results of CB-MCTS on the D-chain problem with D=20D=20 and 2 agents for varying exploration bias ε\varepsilon and discount factor γ\gamma , and search temperature α\alpha .
Figure 11: Results of Dec-MCTS on the modified D-chain problem with D=20D=20 and 2 agents for varying exploration bias ε\varepsilon and discount factor γ\gamma .
Figure 12: Results of CB-MCTS on the modified D-chain problem with D=20D=20 and 2 agents for varying exploration bias ε\varepsilon and discount factor γ\gamma , and search temperature α\alpha .
Algorithmε\varepsilonγ\gammaαinit\alpha_{init}
Dec-MCTS1000.99-
CB-MCTS0.50.91
CAR-DENTS0.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%95\% confidence interval.
Algorithmε\varepsilonγ\gammaαinit\alpha_{init}
Dec-MCTS1000.6-
CB-MCTS0.50.80.01
CAR-DENTS0.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=10D=10 and 2 agents for varying exploration bias ε\varepsilon and discount factor γ\gamma .
Figure 17: Results of NE-MCTS on the D-chain problem with D=10D=10 and 2 agents for varying exploration bias ε\varepsilon , discount factor γ\gamma , and search temperature α\alpha .
Figure 18: Results of FA-MCTS on the D-chain problem with D=10D=10 and 3 agents for varying exploration bias ε\varepsilon and discount factor γ\gamma .
Figure 19: Results of NE-MCTS on the D-chain problem with D=10D=10 and 3 agents for varying exploration bias ε\varepsilon and discount factor γ\gamma , and search temperature α\alpha .
Figure 20: Results of FA-MCTS on the D-chain problem with D=20D=20 and 2 agents for varying exploration bias ε\varepsilon and discount factor γ\gamma .
Figure 21: Results of NE-MCTS on the D-chain problem with D=20D=20 and 2 agents for varying exploration bias ε\varepsilon and discount factor γ\gamma , and search temperature α\alpha .
Figure 22: Results of FA-MCTS on the modified D-chain problem with D=20D=20 and 2 agents for varying exploration bias ε\varepsilon and discount factor γ\gamma .
Figure 23: Results of NE-MCTS on the modified D-chain problem with D=20D=20 and 2 agents for varying exploration bias ε\varepsilon and discount factor γ\gamma , and search temperature α\alpha .
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%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%95\% confidence interval.

Explore similar work

CardsList

  1. Decentralized Multi-Robot Exploration with Probabilistic Peer Intent and Multi-hop Plan Propagation

    Sep 19, 2026Saurbh Singh Jamwal, Nived Chebrolu, Shivaram KalyanakrishnanMulti-Robot ExplorationMulti-Robot Coordination

    Department of Computer Science and Engineering Indian Institute of Technology Bombay

  2. NonZero: Interaction-Guided Exploration for Multi-Agent Monte Carlo Tree Search

    May 1, 2026Sizhe Tang, Zuyuan Zhang, Mahdi Imani +1Multi-Agent System OptimizationMulti-Agent Coordination

    The George Washington University · Northeastern University

  3. Online Robust Reinforcement Learning Through Monte-Carlo Planning

    Sep 16, 2026Tuan Dam, Kishan Panaganti, Brahim Driss +1Monte Carlo Tree SearchDistributionally Robust RL

    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