Dynamic Programming Approximations for Partially Observable Stochastic Games

Akshat Kumar and Shlomo Zilberstein. Dynamic Programming Approximations for Partially Observable Stochastic Games. Proceedings of the Twenty-Second International FLAIRS Conference, 547-552, Sanibel Island, Florida, 2009.

Abstract

Partially observable stochastic games (POSGs) provide a rich mathematical framework for planning under uncertainty by a group of agents. However, this modeling advantage comes with a price, namely a high computational cost. Solving POSGs optimally quickly becomes intractable after a few decision cycles. Our main contribution is to provide bounded approximation techniques, which enable us to scale POSG algorithms by several orders of magnitude. We study both the POSG model and its cooperative counterpart, DEC-POMDP. Experiments on a number of problems confirm the scalability of our approach while still providing useful policies.

Bibtex entry:

@inproceedings{KZflairs09,
  author	= {Akshat Kumar and Shlomo Zilberstein},
  title		= {Dynamic Programming Approximations for Partially Observable 
                   Stochastic Games},
  booktitle     = {Proceedings of the Twenty-Second International {FLAIRS} Conference},
  year		= {2009},
  pages		= {547-552},
  address       = {Sanibel Island, Florida},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/CZmsdm09.html}
}

shlomo@cs.umass.edu
UMass Amherst