Bounded Dynamic Programming for Decentralized POMDPs

Christopher Amato, Alan Carlin, and Shlomo Zilberstein. Bounded Dynamic Programming for Decentralized POMDPs. Proceedings of the AAMAS Workshop on Multi-Agent Sequential Decision Making in Uncertain Domains (MSDM), Honolulu, Hawaii, May, 2007.

Abstract

Solving decentralized POMDPs (DEC-POMDPs) optimally is a very hard problem. As a result, several approximate algorithms have been developed, but these do not have satisfactory error bounds. In this paper, we first discuss optimal dynamic programming and some approximate finite horizon DEC-POMDP algorithms. We then present a bounded dynamic programming algorithm. Given a problem and an error bound, the algorithm will return a solution within that bound when it is able to solve the problem. We give a proof of this bound and provide some experimental results showing high quality solutions to large DEC-POMDPs for large horizons.

Bibtex entry:

@inproceedings{ACZmsdm07,
  author	= {Christopher Amato and Alan Carlin and Shlomo Zilberstein},
  title		= {Bounded Dynamic Programming for Decentralized {POMDP}s},
  booktitle     = {Proceedings of the {AAMAS} Workshop on Multi-Agent 
Sequential Decision Making in Uncertain Domains},
  year		= {2007},
  pages		= {},
  address       = {Honolulu, Hawaii},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/ACZmsdm07.html}
}

shlomo@cs.umass.edu