nips nips2007 nips2007-52 nips2007-52-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Judy Goldsmith, Martin Mundhenk
Abstract: It is known that determinining whether a DEC-POMDP, namely, a cooperative partially observable stochastic game (POSG), has a cooperative strategy with positive expected reward is complete for NEXP. It was not known until now how cooperation affected that complexity. We show that, for competitive POSGs, the complexity of determining whether one team has a positive-expected-reward strategy is complete for NEXPNP .
[1] Daniel S. Bernstein, Robert Givan, Neil Immerman, and Shlomo Zilberstein. The complexity of decentralized control of Markov decision processes. Math. Oper. Res., 27(4):819–840, 2002.
[2] E. Hansen, D. Bernstein, and S. Zilberstein. Dynamic programming for partially observable stochastic games. In Proceedings of the Nineteenth National Conference on Artificial Intelligence (AAAI-04), pages 709–715, 2004.
[3] Hao Wang. Proving theorems by pattern recognition II. Bell Systems Technical Journal, 40:1– 42, 1961.
[4] M. Savelsbergh and P. van Emde Boas. Bounded tiling, an alternative to satisfiability. In Gerd Wechsung, editor, 2nd Frege Conference, volume 20 of Mathematische Forschung, pages 354– 363. Akademie Verlag, Berlin, 1984.
[5] C.H. Papadimitriou and J.N. Tsitsiklis. The complexity of Markov decision processes. Mathematics of Operations Research, 12(3):441–450, 1987.
[6] Martin Mundhenk, Judy Goldsmith, Christopher Lusena, and Eric Allender. Complexity results for finite-horizon Markov decision process problems. Journal of the ACM, 47(4):681–720, 2000. 8