Optimizing Fixed-Size Stochastic Controllers for POMDPs and Decentralized POMDPs

Christopher Amato, Daniel S. Bernstein, and Shlomo Zilberstein. Optimizing Fixed-Size Stochastic Controllers for POMDPs and Decentralized POMDPs. Autonomous Agents and Multi-Agent Systems, 21(3):293-320, 2010.


POMDPs and their decentralized multiagent counterparts, DEC-POMDPs, offer a rich framework for sequential decision making under uncertainty. Their high computational complexity, however, presents an important research challenge. One way to address the intractable memory requirements of current algorithms is based on representing agent policies as finite-state controllers. Using this representation, we propose a new approach that formulates the problem as a nonlinear program, which defines an optimal policy of a desired size for each agent. This new formulation allows a wide range of powerful nonlinear programming algorithms to be used to solve POMDPs and DEC-POMDPs. Although solving the NLP optimally is often intractable, the results we obtain using an off-the-shelf optimization method are competitive with state-of-the-art POMDP algorithms and outperform state-of-the-art DEC-POMDP algorithms. Our approach is easy to implement and it opens up promising research directions for solving POMDPs and DEC-POMDPs using nonlinear programming methods.

Bibtex entry:

  author	= {Christopher Amato and Daniel S. Bernstein and Shlomo Zilberstein},
  title		= {Optimizing Fixed-Size Stochastic Controllers for {POMDP}s and 
                   Decentralized {POMDP}s},
  journal	= {Autonomous Agents and Multi-Agent Systems},
  volume	= {21},
  number	= {3},
  year		= {2010},
  pages		= {293-320},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/ABZjaamas10.html}

UMass Amherst