Abstract
Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs) provide a robust framework for modeling multi-agent coordination under uncertainty. However, finding optimal solutions is computationally intensive—NEXP-complete for finite horizons—and typically requires explicit transition and observation models. This paper introduces MC-JESP (Monte-Carlo Joint Equilibrium-based Search for Policies), a simulation-based algorithm that seeks a Nash Equilibrium by combining Monte-Carlo Tree Search (MCTS) with iterative best-response planning. By representing policies as Finite State Controllers (FSCs), MC-JESP generates interpretable, high-performing strategies using only a black-box simulator. Experimental results across standard benchmarks demonstrate that MC-JESP rivals state-of-the-art explicit-model solvers and significantly outperforms existing simulation-based methods in complex tasks.
Introduction
In multi-agent systems such as robotic teams or warehouse logistics, agents must collaborate to achieve common goals while possessing only partial information about the environment and each other. These scenarios are formally modeled as Dec-POMDPs. While theoretically powerful, Dec-POMDPs are notoriously difficult to solve. Most high-performance solvers rely on an explicit model, requiring exact probability tables for every possible state transition and observation. In many real-world applications, such models are unavailable, leaving researchers to rely on generative models or simulators.
Previous simulation-based approaches often struggled to scale to large state spaces or failed to match the performance of explicit-model counterparts. MC-JESP addresses this gap by leveraging the efficiency of Monte-Carlo sampling to construct structured policies without needing the underlying mathematical matrices.
Methodology
MC-JESP operates through an iterative refinement process designed to reach a Nash Equilibrium, where each agent’s policy is a best response to the fixed policies of all other agents. The algorithm consists of four primary components:
1. Best-Response Generative Model ($G_{BR}$)
To optimize a single agent's policy, the algorithm creates a "wrapper" around the Dec-POMDP simulator. By fixing the policies of all agents except Agent $i$, the multi-agent problem is reduced to a single-agent POMDP simulator for that specific agent. This allows the use of established single-agent planning techniques.
2. Node-by-Node FSC Construction
Rather than generating a massive, unmanageable policy tree, MC-JESP represents policies as Finite State Controllers (FSCs). It utilizes POMCP (Partially Observable Monte-Carlo Planning) to determine the optimal action for specific nodes within the controller. Each node represents a belief state or a history of observations.
3. Belief-Based Merging
To maintain computational efficiency and keep the controller size manageable, the algorithm employs a merging strategy. When a new observation is received, the algorithm maps it to an existing FSC node if the resulting belief state is sufficiently similar to one previously encountered. If the controller reaches a predefined maximum size ($N_{max-fsc}$), new beliefs are merged into the closest existing node, preventing the state space from exploding.
4. Heuristic Initialization
To mitigate the risk of converging to poor local optima, the authors implement a "Multi-agent POMDP" relaxation. This phase assumes agents can share observations during a "mental rehearsal," providing a reasonable initial strategy that the iterative process then refines.
Experimental Evaluation
The authors evaluated MC-JESP on five classic Dec-POMDP benchmarks of varying complexity:
- DecTiger: A foundational coordination problem.
- Recycling Robots: Focuses on energy management and task prioritization.
- Meeting in a 3x3 Grid: A spatial coordination challenge.
- Cooperative Box Pushing: Requires synchronized actions in a large state space.
- Mars Rover: A complex, large-scale benchmark with 256 states.
Results and Discussion
MC-JESP demonstrates a significant advancement in simulation-based planning. In the Mars Rover and Box Pushing benchmarks, MC-JESP(M-20) achieved values nearly identical to FB-HSVI, which is considered the gold standard for solvers with access to explicit models.
When compared to other simulation-based baselines like oSARSA and Dec-SBPR, MC-JESP showed superior scalability. While previous methods often failed to find meaningful solutions in larger environments, MC-JESP consistently produced high-performing policies. Furthermore, the resulting FSCs offer a level of interpretability absent in deep reinforcement learning; the controllers function as flowcharts, allowing human observers to trace the logic behind an agent's actions based on specific observations.
Limitations and Future Work
Despite its performance, MC-JESP is computationally demanding, requiring millions of simulations to converge. This results in longer execution times compared to matrix-based solvers (e.g., 349s vs 122s on the Mars Rover task). Additionally, the algorithm's effectiveness is sensitive to the max FSC size parameter; setting this limit too low can lead to a significant performance degradation in complex environments.
Future research may focus on extending MC-JESP to continuous action and observation spaces using variants like POMCPOW. There is also potential for improving the node-merging process through more sophisticated data structures, such as space-partitioning trees, to accelerate the search for nearest-neighbor belief states.
Conclusion
MC-JESP successfully bridges the gap between simulation-based planning and explicit-model solvers in the Dec-POMDP domain. By combining the flexibility of Monte-Carlo sampling with the structured approach of Finite State Controllers, it provides a scalable and interpretable solution for complex multi-agent coordination problems.
Summary updated