Conference Proceeding Article
Decentralized POMDP is an expressive model for multi-agent planning. Finite-state controllers (FSCs)---often used to represent policies for infinite-horizon problems---offer a compact, simple-to-execute policy representation. We exploit novel connections between optimizing decentralized FSCs and the dual linear program for MDPs. Consequently, we describe a dual mixed integer linear program (MIP) for optimizing deterministic FSCs. We exploit the Dec-POMDP structure to devise a compact MIP and formulate constraints that result in policies executable in partially-observable decentralized settings. We show analytically that the dual formulation can also be exploited within the expectation maximization (EM) framework to optimize stochastic FSCs. The resulting EM algorithm can be implemented by solving a sequence of linear programs, without requiring expensive message-passing over the Dec-POMDP DBN. We also present an efficient technique for policy improvement based on a weighted entropy measure. Compared with state-of-the-art FSC methods, our approach offers over an order-of-magnitude speedup, while producing similar or better solutions.
Intelligent Systems and Decision Analytics
AAAI Publications, Twenty-Sixth International Conference on Automated Planning and Scheduling
City or Country
Akshat KUMAR; MOSTAFA, Hala; and ZILBERSTEIN, Shlomo.
Dual formulations for optimizing Dec-POMDP controllers. (2016). AAAI Publications, Twenty-Sixth International Conference on Automated Planning and Scheduling. 202-210. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/3395
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.