Observation Compression in DEC-POMDP Policy Trees

Alan Carlin and Shlomo Zilberstein. Observation Compression in DEC-POMDP Policy Trees. Proceedings of the AAMAS Workshop on Multi-Agent Sequential Decision Making in Uncertain Domains, (MSDM), 31-45, Estoril, Portugal, 2008

Abstract

Representing agent policies compactly is essential for improving the scalability of multi-agent planning algorithms. In this paper, we focus on developing a pruning technique that allows us to merge certain observations from agent policies, while minimizing the loss of value. This is particularly important for solving finite-horizon decentralized POMDPs, where agent policies are represented as trees, and where the size of policy trees grows exponentially with the number of observations. We introduce a value-based observation compression technique that prunes the least valuable observations while maintaining an error bound on the value lost as a result of pruning. We analyze the characteristics of this pruning strategy and show empirically that it is effective. Thus, we use compact policies to obtain significantly higher values compared with the best existing DEC-POMDP algorithm.

Bibtex entry:

@inproceedings{CZmsdm08,
  author	= {Alan Carlin and Shlomo Zilberstein},
  title		= {Observation Compression in {DEC-POMDP} Policy Trees},
  booktitle     = {Proceedings of the {AAMAS} Workshop on Multi-Agent Sequential
		   Decision Making in Uncertain Domains},
  year		= {2008},
  pages		= {31-45},
  address       = {Estoril, Portugal},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/CZmsdm08.html}
}

shlomo@cs.umass.edu
UMass Amherst