nips nips2009 nips2009-53 nips2009-53-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Martin Allen, Shlomo Zilberstein
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. 1
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17] Daniel S. Bernstein, Shlomo Zilberstein, and Neil Immerman. The complexity of decentralized control of Markov decision processes. In Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence, pages 32–37, Stanford, California, 2000. Daniel S. Bernstein, Robert Givan, Neil Immerman, and Shlomo Zilberstein. The complexity of decentralized control of Markov decision processes. Mathematics of Operations Research, 27(4):819–840, 2002. Judy Goldsmith and Martin Mundhenk. Competition adds complexity. In J.C. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems 20, pages 561–568. MIT Press, Cambridge, MA, 2008. Harry R. Lewis. Complexity of solvable cases of the decision problem for predicate calculus. In Proceedings of the Nineteenth Symposium on the Foundations of Computer Science, pages 35–47, Ann Arbor, Michigan, 1978. Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, Reading, Massachusetts, 1994. Raphen Becker, Shlomo Zilberstein, Victor Lesser, and Claudia V. Goldman. Transitionindependent decentralized Markov decision processes. In Proceedings of the Second International Joint Conference on Autonomous Agents and Multi-Agent Systems, pages 41–48, Melbourne, Australia, 2003. Raphen Becker, Shlomo Zilberstein, Victor Lesser, and Claudia V. Goldman. Solving transition independent decentralized MDPs. Journal of Artificial Intelligence Research, 22:423–455, November 2004. Claudia V. Goldman and Shlomo Zilberstein. Decentralized control of cooperative systems: Categorization and complexity analysis. Journal of Artificial Intelligence Research, 22:143– 174, 2004. Martin Allen. Agent Interactions in Decentralized Environments. PhD thesis, University of Massachusetts, Amherst, Massachusetts, 2009. Available at http://scholarworks. umass.edu/open_access_dissertations/1/. Raphen Becker, Victor Lesser, and Shlomo Zilberstein. Decentralized Markov decision processes with event-driven interactions. In Proceedings of the Third International Joint Conference on Autonomous Agents and Multi-Agent Systems, pages 302–309, New York, New York, 2004. Keith S. Decker and Victor R. Lesser. Quantitative modeling of complex environments. International Journal of Intelligent Systems in Accounting, Finance and Management, 2:215–234, 1993. V. Lesser, K. Decker, T.Wagner, N. Carver, A. Garvey, B. Horling, D. Neiman, R. Podorozhny, M. Nagendra Prasad, A. Raja, R. Vincent, P. Xuan, and X.Q Zhang. Evolution of the GPGP/TAEMS domain-independent coordination framework. Autonomous Agents and MultiAgent Systems, 9(1):87–143, 2004. Tom Wagner, Valerie Guralnik, and John Phelps. TAEMS agents: Enabling dynamic distributed supply chain management. Journal of Electronic Commerce Research and Applications, 2:114–132, 2003. AnYuan Guo. Planning and Learning for Weakly-Coupled Distributed Agents. PhD thesis, University of Massachusetts, Amherst, 2006. AnYuan Guo and Victor Lesser. Planning for weakly-coupled partially observable stochastic games. In Proceedings of the 19th International Joint Conference on Artificial Intelligence, pages 1715–1716, Edinburgh, Scotland, 2005. AnYuan Guo and Lesser Victor. Stochastic planning for weakly-coupled distributed agents. In Proceedings of the Fifth Joint Conference on Autonomous Agents and Multiagent Systems, pages 326–328, Hakodate, Japan, 2006. Sven Seuken and Shlomo Zilberstein. Formal models and algorithms for decentralized decision making under uncertainty. Autonomous Agents and Multi-Agent Systems, 17(2):190–250, 2008. 9