ML Anthology

Error-Bounded Approximations for Infinite-Horizon Discounted Decentralized POMDPs

Jilles Steeve Dibangoye, Olivier Buffet, François Charpillet
ECML-PKDD 2014 pp. 338-353
doi:10.1007/978-3-662-44848-9_22 /ecmlpkdd/2014/dibangoye2014ecmlpkdd-errorbounded/

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.

PDF ECML-PKDD Semantic Scholar

Cite

Text

Dibangoye et al. "Error-Bounded Approximations for Infinite-Horizon Discounted Decentralized POMDPs." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2014. doi:10.1007/978-3-662-44848-9_22

Markdown

[Dibangoye et al. "Error-Bounded Approximations for Infinite-Horizon Discounted Decentralized POMDPs." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2014.](https://mlanthology.org/ecmlpkdd/2014/dibangoye2014ecmlpkdd-errorbounded/) doi:10.1007/978-3-662-44848-9_22

BibTeX

@inproceedings{dibangoye2014ecmlpkdd-errorbounded,
  title     = {{Error-Bounded Approximations for Infinite-Horizon Discounted Decentralized POMDPs}},
  author    = {Dibangoye, Jilles Steeve and Buffet, Olivier and Charpillet, François},
  booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
  year      = {2014},
  pages     = {338-353},
  doi       = {10.1007/978-3-662-44848-9_22},
  url       = {https://mlanthology.org/ecmlpkdd/2014/dibangoye2014ecmlpkdd-errorbounded/}
}