Improved Memory-Bounded Dynamic Programming for Decentralized POMDPs
arXiv:1206.5295
Abstract
Memory-Bounded Dynamic Programming (MBDP) has proved extremely effective in solving decentralized POMDPs with large horizons. We generalize the algorithm and improve its scalability by reducing the complexity with respect to the number of observations from exponential to polynomial. We derive error bounds on solution quality with respect to this new approximation and analyze the convergence behavior. To evaluate the effectiveness of the improvements, we introduce a new, larger benchmark problem. Experimental results show that despite the high complexity of decentralized POMDPs, scalable solution techniques such as MBDP perform surprisingly well.
Appears in Proceedings of the Twenty-Third Conference on Uncertainty in Artificial Intelligence (UAI2007)
References in corpus (3)
Cited by in corpus (13)
- Optimal and Approximate Q-value Functions for Decentralized POMDPs
- OpenSpiel: A Framework for Reinforcement Learning in Games
- Policy Iteration for Decentralized Control of Markov Decision Processes
- Monte Carlo Sampling Methods for Approximating Interactive POMDPs
- Incremental Clustering and Expansion for Faster Optimal Planning in Dec-POMDPs
- Rollout Sampling Policy Iteration for Decentralized POMDPs
- Macro-Action-Based Deep Multi-Agent Reinforcement Learning
- Uncertain Congestion Games with Assorted Human Agent Populations
- Online Planning for Decentralized Stochastic Control with Partial History Sharing
- Information State Embedding in Partially Observable Cooperative Multi-Agent Reinforcement Learning
- Team Behavior in Interactive Dynamic Influence Diagrams with Applications to Ad Hoc Teams
- Distribution over Beliefs for Memory Bounded Dec-POMDP Planning
- Partially Observed, Multi-objective Markov Games