Scaling Up Decentralized MDPs Through Heuristic Search

Jilles S. Dibangoye, Christopher Amato, Arnoud Doniec
Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, PMLR R10:215-224, 2012.

Abstract

Decentralized partially observable Markov decision processes (Dec-POMDPs) are rich models for cooperative decision-making under uncertainty, but are often intractable to solve optimally (NEXP-complete). The transition and observation independent Dec-MDP is a general subclass that has been shown to have complexity in NP, but optimal algorithms for this subclass are still inefficient in practice. In this paper, we first provide an updated proof that an optimal policy does not depend on the histories of the agents, but only the local observations. We then present a new algorithm based on heuristic search that is able to expand search nodes by using constraint optimization. We show experimental results comparing our approach with the state-of-the-art DecMDP and Dec-POMDP solvers. These results show a reduction in computation time and an increase in scalability by multiple orders of magnitude in a number of benchmarks.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR10-dibangoye12a, title = {Scaling Up Decentralized MDPs Through Heuristic Search}, author = {Dibangoye, Jilles S. and Amato, Christopher and Doniec, Arnoud}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {215--224}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/dibangoye12a/dibangoye12a.pdf}, url = {https://proceedings.mlr.press/r10/dibangoye12a.html}, abstract = {Decentralized partially observable Markov decision processes (Dec-POMDPs) are rich models for cooperative decision-making under uncertainty, but are often intractable to solve optimally (NEXP-complete). The transition and observation independent Dec-MDP is a general subclass that has been shown to have complexity in NP, but optimal algorithms for this subclass are still inefficient in practice. In this paper, we first provide an updated proof that an optimal policy does not depend on the histories of the agents, but only the local observations. We then present a new algorithm based on heuristic search that is able to expand search nodes by using constraint optimization. We show experimental results comparing our approach with the state-of-the-art DecMDP and Dec-POMDP solvers. These results show a reduction in computation time and an increase in scalability by multiple orders of magnitude in a number of benchmarks.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Scaling Up Decentralized MDPs Through Heuristic Search %A Jilles S. Dibangoye %A Christopher Amato %A Arnoud Doniec %B Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2012 %E Nando de Freitas %E Kevin Murphy %F pmlr-vR10-dibangoye12a %I PMLR %P 215--224 %U https://proceedings.mlr.press/r10/dibangoye12a.html %V R10 %X Decentralized partially observable Markov decision processes (Dec-POMDPs) are rich models for cooperative decision-making under uncertainty, but are often intractable to solve optimally (NEXP-complete). The transition and observation independent Dec-MDP is a general subclass that has been shown to have complexity in NP, but optimal algorithms for this subclass are still inefficient in practice. In this paper, we first provide an updated proof that an optimal policy does not depend on the histories of the agents, but only the local observations. We then present a new algorithm based on heuristic search that is able to expand search nodes by using constraint optimization. We show experimental results comparing our approach with the state-of-the-art DecMDP and Dec-POMDP solvers. These results show a reduction in computation time and an increase in scalability by multiple orders of magnitude in a number of benchmarks. %Z Reissued by PMLR on 04 October 2026.
APA
Dibangoye, J.S., Amato, C. & Doniec, A.. (2012). Scaling Up Decentralized MDPs Through Heuristic Search. Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R10:215-224 Available from https://proceedings.mlr.press/r10/dibangoye12a.html. Reissued by PMLR on 04 October 2026.

Related Material