Dual Formulations for Optimizing Dec-POMDP Controllers

Akshat Kumar, Hala Mostafa, and Shlomo Zilberstein. Dual Formulations for Optimizing Dec-POMDP Controllers. Proceedings of the Twenty-Sixth International Conference on Automated Planning and Scheduling (ICAPS), London, UK, 2016.

Abstract

Decentralized POMDP is an expressive model for multiagent 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.

Bibtex entry:

@inproceedings{KMZicaps16,
  author	= {Akshat Kumar and Hala Mostafa and Shlomo Zilberstein},
  title		= {Dual Formulations for Optimizing Dec-POMDP Controllers},
  booktitle     = {Proceedings of the Twenty-Sixth International Conference
                   on Automated Planning and Scheduling},
  year		= {2016},
  pages		= { },
  address       = {London, UK},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/KMZicaps16.html}
}

shlomo@cs.umass.edu