Solving POMDPs Using Quadratically Constrained Linear Programs

Christopher Amato, Daniel S. Bernstein, Shlomo Zilberstein

IJCAI 2007 pp. 2418-2424

doi:10.1145/1160633.1160694 /ijcai/2007/amato2007ijcai-solving/

Abstract

Since the early 1990's, Markov decision processes (MDPs) and their partially observable counterparts (POMDPs) have been widely used by the AI community for planning under uncertainty. POMDPs offer a rich language to describe situations involving uncertainty about the domain, stochastic actions, noisy observations, and a variety of possible objective functions. Even though an optimal solution may be concise, current exact algorithms that use dynamic programming often require an intractable amount of space. POMDP approximation algorithms can operate with a limited amount of memory, but as a consequence they provide very weak theoretical guarantees. In contrast, we describe a new approach that addresses the space requirement of POMDP algorithms while maintaining well-defined optimality guarantees.

PDF IJCAI Semantic Scholar

Cite

Text

Amato et al. "Solving POMDPs Using Quadratically Constrained Linear Programs." International Joint Conference on Artificial Intelligence, 2007. doi:10.1145/1160633.1160694

Markdown

[Amato et al. "Solving POMDPs Using Quadratically Constrained Linear Programs." International Joint Conference on Artificial Intelligence, 2007.](https://mlanthology.org/ijcai/2007/amato2007ijcai-solving/) doi:10.1145/1160633.1160694

BibTeX

@inproceedings{amato2007ijcai-solving,
  title     = {{Solving POMDPs Using Quadratically Constrained Linear Programs}},
  author    = {Amato, Christopher and Bernstein, Daniel S. and Zilberstein, Shlomo},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2007},
  pages     = {2418-2424},
  doi       = {10.1145/1160633.1160694},
  url       = {https://mlanthology.org/ijcai/2007/amato2007ijcai-solving/}
}