# Approximate Dec-POMDP Solving Using Multi-Agent A*

arXiv: https://arxiv.org/abs/2405.05662 · HTML: https://mlsanity.com/paper/2405.05662/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 34 references that are in the map.
- First posted on arXiv 9 May 2024.

## Builds on (most cited first, 3 of 3)

- [The Complexity of Decentralized Control of Markov Decision Processes](https://mlsanity.com/paper/1301.3836/) (2013)
- [Information State Embedding in Partially Observable Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2004.01098/) (2020)
- [Incremental Clustering and Expansion for Faster Optimal Planning in Dec-POMDPs](https://mlsanity.com/paper/1402.0566/) (2014)

## Built on by (most cited first, 1 of 1)

- [The Curious Case of Exploding DecPOMDPs: Containing the Fire through Policy Counting](https://mlsanity.com/paper/2608.17749/) (2026)

## Abstract (arXiv)

We present an A*-based algorithm to compute policies for finite-horizon Dec-POMDPs. Our goal is to sacrifice optimality in favor of scalability for larger horizons. The main ingredients of our approach are (1) using clustered sliding window memory, (2) pruning the A* search tree, and (3) using novel A* heuristics. Our experiments show competitive performance to the state-of-the-art. Moreover, for multiple benchmarks, we achieve superior performance. In addition, we provide an A* algorithm that finds upper bounds for the optimum, tailored towards problems with long horizons. The main ingredient is a new heuristic that periodically reveals the state, thereby limiting the number of reachable beliefs. Our experiments demonstrate the efficacy and scalability of the approach.