Complexity of Decentralized Control: Special Cases

Martin Allen and Shlomo Zilberstein. Complexity of Decentralized Control: Special Cases. Proceedings of the Twenty-Third Neural Information Processing Systems Conference (NIPS), 19-27, Vancouver, British Columbia, Canada, 2009.

Abstract

The worst-case complexity of general decentralized POMDPs, which are equivalent to partially observable stochastic games (POSGs) is very high, both for the cooperative and competitive cases. Some reductions in complexity have been achieved by exploiting independence relations in some models. We show that these results are somewhat limited: when these independence assumptions are relaxed in very small ways, complexity returns to that of the general case.

Bibtex entry:

@inproceedings{AZnips09,
  author	= {Martin Allen and Shlomo Zilberstein},
  title		= {Complexity of Decentralized Control: Special Cases},
  booktitle     = {Proceedings of the Twenty-Third Neural Information Processing 
                   Systems Conference},
  year		= {2009},
  pages		= {19-27},
  address       = {Vancouver, British Columbia, Canada},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/AZnips09.html}
}

shlomo@cs.umass.edu