2009
NeurIPS
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 Computer Science and Mathematics & Optimization and Reinforcement Learning
📈
Trend Setter
- Multi-Agent Systems
🐣
Hot Topic Early Bird
- multi-agent system
Authors
Topics
Artificial Intelligence > Core AI > Multi-Agent Systems
Artificial Intelligence > Core AI > Planning
Machine Learning > Optimization & Theory > Theory
Reinforcement Learning > Methods > Multi-Agent Systems
Computer Science > Foundations > Algorithms
Machine Learning > Learning Types > Multi-Agent Systems
Mathematics & Optimization > Optimization > Game Theory