Skip to Main content Skip to Navigation
Conference papers

Error-Bounded Approximations for Infinite-Horizon Discounted Decentralized POMDPs

Jilles Steeve Dibangoye 1 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 : We address decentralized stochastic control problems represented as decentralized partially observable Markov decision processes (Dec-POMDPs). This formalism provides a general model for decision-making under uncertainty in cooperative, decentralized settings, but the worst-case complexity makes it difficult to solve optimally (NEXP-complete). Recent advances suggest recasting Dec-POMDPs into continuous-state and deterministic MDPs. In this form, however, states and actions are embedded into high-dimensional spaces, making accurate estimate of states and greedy selection of actions intractable for all but trivial-sized problems. The primary contribution of this paper is the first framework for error-monitoring during approximate estimation of states and selection of actions. Such a framework permits us to convert state-of-the-art exact methods into error-bounded algorithms, which results in a scalability increase as demonstrated by experiments over problems of unprecedented sizes.
Document type :
Conference papers
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/hal-01096610
Contributor : Olivier Buffet <>
Submitted on : Wednesday, December 17, 2014 - 5:32:39 PM
Last modification on : Tuesday, December 18, 2018 - 4:40:21 PM
Long-term archiving on: : Monday, March 23, 2015 - 4:05:35 PM

File

ecml14.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Jilles Steeve Dibangoye, Olivier Buffet, François Charpillet. Error-Bounded Approximations for Infinite-Horizon Discounted Decentralized POMDPs. European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML/PKDD), Sep 2014, Nancy, France. pp.338 - 353, ⟨10.1007/978-3-662-44848-9_22⟩. ⟨hal-01096610⟩

Share

Metrics

Record views

348

Files downloads

620