The Complexity of Decentralized Control of Markov Decision Processes

Abstract

Planning for distributed agents with partial state information is considered from a decision- theoretic perspective. We describe generalizations of both the MDP and POMDP models that allow for decentralized control. For even a small number of agents, the finite-horizon problems corresponding to both of our models are complete for nondeterministic exponential time. These complexity results illustrate a fundamental difference between centralized and decentralized control of Markov processes. In contrast to the MDP and POMDP problems, the problems we consider provably do not admit polynomial-time algorithms and most likely require doubly exponential time to solve in the worst case. We have thus provided mathematical evidence corresponding to the intuition that decentralized planning problems cannot easily be reduced to centralized problems and solved exactly using established techniques.

Appears in Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence (UAI2000)

References in corpus (5)

• Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes
• Learning to Cooperate via Policy Search
• Solving POMDPs by Searching in Policy Space
• Solving POMDPs by Searching the Space of Finite Policies
• My Brain is Full: When More Memory Helps

Cited by in corpus (20)

• Human-level performance in first-person multiplayer games with population-based deep reinforcement learning
• Learning a Generic Value-Selection Heuristic Inside a Constraint Programming Solver
• Cooperative Inverse Reinforcement Learning
• The Communicative Multiagent Team Decision Problem: Analyzing Teamwork Theories and Models
• Learning to Cooperate via Policy Search
• Improved Memory-Bounded Dynamic Programming for Decentralized POMDPs
• Belief and Truth in Hypothesised Behaviours
• Shapley Counterfactual Credits for Multi-Agent Reinforcement Learning
• A Bilinear Programming Approach for Multiagent Planning
• Rollout Sampling Policy Iteration for Decentralized POMDPs
• Quantifying the Impact of Non-Stationarity in Reinforcement Learning-Based Traffic Signal Control
• Applications of Multi-Agent Reinforcement Learning in Future Internet: A Comprehensive Survey
• Cross-layer design of distributed sensing-estimation with quality feedback, Part I: Optimal schemes
• Reinforcement Learning for Heterogeneous Teams with PALO Bounds
• Planning for Decentralized Control of Multiple Robots Under Uncertainty
• School of hard knocks: Curriculum analysis for Pommerman with a fixed computational budget
• Filtered Fictitious Play for Perturbed Observation Potential Games and Decentralised POMDPs
• Optimal Decision-Making in Mixed-Agent Partially Observable Stochastic Environments via Reinforcement Learning
• A Framework for Rate Efficient Control of Distributed Discrete Systems
• A Strong Duality Result for Constrained POMDPs with Multiple Cooperative Agents