Skip to Main content Skip to Navigation

Optimally solving Dec-POMDPs as Continuous-State MDPs: Theory and Algorithms

Jilles Steeve Dibangoye 1 Christopher Amato 2 Olivier Buffet 1 François Charpillet 1 
1 MAIA - Autonomous intelligent machine
Inria Nancy - Grand Est, LORIA - AIS - Department of Complex Systems, Artificial Intelligence & Robotics
Abstract : Decentralized partially observable Markov decision processes (Dec-POMDPs) provide a general model for decision-making under uncertainty in cooperative decentralized settings, but are difficult to solve optimally (NEXP-Complete). As a new way of solving these problems, we introduce the idea of transforming a Dec-POMDP into a continuous-state deterministic MDP with a piecewise-linear and convex value function. This approach makes use of the fact that planning can be accomplished in a centralized offline manner, while execution can still be distributed. This new Dec-POMDP formulation, which we call an occupancy MDP, allows powerful POMDP and continuous-state MDP methods to be used for the first time. When the curse of dimensionality becomes too prohibitive, we refine this basic approach and present ways to combine heuristic search and compact representations that exploit the structure present in multi-agent domains, without losing the ability to eventually converge to an optimal solution. In particular, we introduce feature-based heuristic search that relies on feature-based compact representations, point-based updates and efficient action selection. A theoretical analysis demonstrates that our feature-based heuristic search algorithms terminate in finite time with an optimal solution. We include an extensive empirical analysis using well known benchmarks, thereby demonstrating our approach provides significant scalability improvements compared to the state of the art.
Document type :
Complete list of metadata

Cited literature [67 references]  Display  Hide  Download
Contributor : Olivier Buffet Connect in order to contact the contributor
Submitted on : Wednesday, April 9, 2014 - 11:38:06 AM
Last modification on : Saturday, June 25, 2022 - 7:44:53 PM
Long-term archiving on: : Wednesday, July 9, 2014 - 11:50:54 AM


Files produced by the author(s)


  • HAL Id : hal-00975802, version 1


Jilles Steeve Dibangoye, Christopher Amato, Olivier Buffet, François Charpillet. Optimally solving Dec-POMDPs as Continuous-State MDPs: Theory and Algorithms. [Research Report] RR-8517, INRIA. 2014, pp.77. ⟨hal-00975802⟩



Record views


Files downloads