← Back to papers
2009 NIPS NeurIPS 2009

Complexity of Decentralized Control: Special Cases

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.

🌉 Interdisciplinary Bridge — Artificial Intelligence and Machine Learning and Reinforcement Learning
📈 Trend Setter — Multi-Agent Systems
🧭 Keyword Pioneer — complexity analysis
🐣 Hot Topic Early Bird — multi-agent system
🐝 Cross-Pollinator — Artificial Intelligence, Computer Science, Deep Learning, Healthcare & Medicine, Interdisciplinary, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Robotics

Authors

Martin Allen , Shlomo Zilberstein

Topics

Artificial Intelligence > Core AI > Multi-Agent Systems Machine Learning > Optimization & Theory > Theory Reinforcement Learning > Methods > Multi-Agent Systems Machine Learning > Learning Types > Multi-Agent Systems Mathematics & Optimization > Optimization > Game Theory

Keywords

game theory partially observable markov decision processes partially observable markov decision process decentralized control complexity analysis stochastic game multi-agent system partial observable markov decision process
Download PDF

Related papers

Solving Stochastic Games 2009
Bilinear classifiers for visual recognition 2009
Zero-shot Learning with Semantic Output Codes 2009
Matrix Completion from Power-Law Distributed Samples 2009
Heavy-Tailed Symmetric Stochastic Neighbor Embedding 2009