Abstract
This paper introduces RS-MAA (Recursive Small-Step Multi-Agent A), an exact algorithm for solving Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs). By decomposing massive joint decision rules into incremental "small steps" and employing a tight, recursive heuristic computed on-the-fly, RS-MAA* significantly extends the solvability of these NEXP-hard problems, reaching horizons previously considered unreachable for exact solvers.
Introduction
Dec-POMDPs model cooperative scenarios where multiple agents must achieve a shared goal despite having only partial, local observations and no free communication. The primary challenge in solving these optimally using the classical Multi-Agent A (MAA) approach is the search tree's "outdegree." A single node expansion requires choosing a joint decision rule—a mapping of every possible observation history for every agent to an action—leading to a double-exponential explosion in children per node. This typically causes solvers to exhaust memory or time as the horizon ($h$) increases.
Methodology
RS-MAA* addresses the complexity of Dec-POMDPs through three core innovations:
1. Small-Step Search Tree
Instead of deciding actions for all agents and histories simultaneously, RS-MAA makes incremental decisions: picking a single action for one agent for one specific observation history. This transforms a shallow tree with a massive outdegree into a much deeper tree with a constant outdegree, allowing the A algorithm to prune sub-optimal branches far more effectively.
2. Recursive On-the-Fly Heuristics ($Q_d$)
Unlike solvers that rely on expensive precomputed heuristics, RS-MAA* computes heuristic values dynamically. This heuristic uses a "communication relaxation," assuming agents can share observations starting at a future time step $d$. This provides a tight, admissible upper bound that is more effective than standard MDP or POMDP approximations.
3. Optimization Techniques
To maintain efficiency, the algorithm can terminate heuristic calculations early if a path is clearly sub-optimal. It also utilizes "lossless clustering" to group observation histories requiring the same action, and dynamically adjusts the depth of the communication relaxation to balance heuristic tightness with computational overhead.
Evaluation and Key Results
The algorithm was evaluated on standard Dec-POMDP benchmarks, including DECTIGER, BOXPUSHING, GRID, HOTEL, RECYCLING, and BROADCAST.
RS-MAA demonstrated a massive leap in performance over the previous state-of-the-art (GMAA-ICE):
- Horizon Scaling: In the RECYCLING domain, RS-MAA* scaled to a horizon of 1500, a vast improvement over the previous limit of 80. In DECTIGER, it reached a horizon of 12, doubling the previous record.
- Computational Efficiency: On the MARS benchmark at horizon 9, RS-MAA* found the optimal solution in 160 seconds, while competing solvers timed out or ran out of memory.
- Memory Management: By computing heuristics on-the-fly and avoiding the massive memory overhead of precomputation, RS-MAA* remains robust where other solvers fail due to memory constraints.
Conclusion
RS-MAA effectively shifts the challenge of Dec-POMDP solving from managing breadth to managing depth. By stretching the decision process into smaller steps, the algorithm leverages its recursive heuristic to prune the search space much earlier. While performance is most dramatic in domains where observation histories can be clustered, RS-MAA sets a new benchmark for exact solvers. Future research may involve integrating approximate solvers into the heuristic computation to further push scalability boundaries.
Summary updated