Proceedings

Monte-Carlo Expectation Maximization for Decentralized POMDPs

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 397-402.

© 2013 International Joint Conferences on Artificial Intelligence

Abstract

We address two significant drawbacks of state-of-the-art solvers of decentralized POMDPs (DEC-POMDPs): the reliance on complete knowledge of the model and limited scalability as the complexity of the domain grows. We extend a recently proposed approach for solving DEC-POMDPs via a reduction to the maximum likelihood problem, which in turn can be solved using EM. We introduce a model-free version of this approach that employs Monte-Carlo EM(MCEM). While a naive implementation of MCEM is inadequate in multi-agent settings, we introduce several improvements in sampling that produce high-quality results on a variety of DEC-POMDP benchmarks, including large problems with thousands of agents.

  1. [Aras et al., 2007] Raghav Aras, Alain Dutech, and Franc ¸ois Charpillet. Mixed integer linear programming for exact finite- horizon planning in decentralized POMDPs. In Proc. of the 17th Int'l Conf. on Automated Planning and Scheduling, pages 18-25, 2007.
  2. [Auer et al., 2002] Peter Auer, Nicolò Cesa-Bianchi, and Paul Fis- cher. Finite-time analysis of the multiarmed bandit problem. Ma- chine Learning, 47(2):235-256, 2002.
  3. [Banerjee et al., 2012] Bikramjit Banerjee, Jeremy Lyle, Landon Kraemer, and Rajesh Yellamraju. Sample bounded distributed reinforcement learning for decentralized POMDPs. In Proc. of the 26th AAAI Conf. on Artificial Intelligence, pages 1256-1262, 2012.
  4. [Bernstein et al., 2002] Daniel S. Bernstein, Robert Givan, Neil Im- merman, and Shlomo Zilberstein. The complexity of decentral- ized control of Markov decision processes. Mathematics of Op- erations Research, 27(4):819-840, 2002.
  5. [Bernstein et al., 2009] Daniel S. Bernstein, Christopher Amato, Eric A. Hansen, and Shlomo Zilberstein. Policy iteration for decentralized control of Markov decision processes. Journal of Artificial Intelligence Research, 34:89-132, 2009.
  6. [Bertsekas, 1999] Dimitri P. Bertsekas. Nonlinear programming. Athena Scientific, 1999.
  7. [Dean and Ghemawat, 2008] Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified data processing on large clusters. Com- munications of the ACM, 51(1):107-113, 2008.
  8. [Dempster et al., 1977] Arthur P. Dempster, Nan M. Laird, and Donald B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society. Series B, pages 1-38, 1977.
  9. [Dibangoye et al., 2011] Jilles S. Dibangoye, Abdel-Illah Mouad- dib, and Brahim Chaib-draa. Toward error-bounded algorithms for infinite-horizon DEC-POMDPs. In Proc. of the 10th Int'l Conf. on Autonomous Agents and Multiagent Systems, pages 947-954, 2011.
  10. [Hansen et al., 2004] Eric A. Hansen, Daniel S. Bernstein, and Shlomo Zilberstein. Dynamic programming for partially observ- able stochastic games. In Proc. of the 19th National Conf. on Artificial Intelligence, pages 709-715, 2004.
  11. [Kumar and Zilberstein, 2010] Akshat Kumar and Shlomo Zilber- stein. Anytime planning for decentralized POMDPs using expec- tation maximization. In Proc. of the 26th Conf. on Uncertainty in Artificial Intelligence, pages 294-301, 2010.
  12. [Kumar et al., 2011] Akshat Kumar, Shlomo Zilberstein, and Marc Toussaint. Scalable multiagent planning using probabilistic in- ference. In Proc. of the 22nd Int'l Joint Conf. on Artificial Intel- ligence, pages 2140-2146, 2011. IJCAI
  13. [Nair et al., 2003] Ranjit Nair, Milind Tambe, Makoto Yokoo, David V. Pynadath, and Stacy Marsella. Taming decentralized POMDPs: Towards efficient policy computation for multiagent settings. In Proc. of the 18th Int'l Joint Conf. on Artificial Intel- ligence, pages 705-711, 2003. IJCAI
  14. [Nair et al., 2005] Ranjit Nair, Pradeep Varakantham, Milind Tambe, and Makoto Yokoo. Networked distributed POMDPs: A synthesis of distributed constraint optimization and POMDPs. In Proc. of the 20th National Conf. on Artificial Intelligence, pages 133-139, 2005.
  15. [Neath, 2012] Ronald C. Neath. On convergence properties of the Monte Carlo EM algorithm. arXiv preprint arXiv:1206.4768, 2012.
  16. [Pajarinen and Peltonen, 2011a] Joni Pajarinen and Jaakko Pelto- nen. Efficient planning for factored infinite-horizon DEC- POMDPs. In Proc. of the 22nd Int'l Joint Conf. on Artificial Intelligence, pages 325-331, 2011. IJCAI
  17. [Pajarinen and Peltonen, 2011b] Joni Pajarinen and Jaakko Pelto- nen. Periodic finite state controllers for efficient POMDP and DEC-POMDP planning. In Proc. of the 25th Annual Conf. on Neural Information Processing Systems, pages 2636-2644, 2011.
  18. [Seuken and Zilberstein, 2007] Sven Seuken and Shlomo Zilber- stein. Memory-bounded dynamic programming for DEC- POMDPs. In Proc. of the 20th Int'l Joint Conf. on Artificial In- telligence, pages 2009-2015, 2007.
  19. [Spaan et al., 2011] Matthijs T. J. Spaan, Frans A. Oliehoek, and Christopher Amato. Scaling up optimal heuristic search in Dec- POMDPs via incremental expansion. In Proc. of the 22nd Int'l Joint Conf. on Artificial Intelligence, pages 2027-2032, 2011. IJCAI
  20. [Sutton and Barto, 1998] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, Cam- bridge, MA, USA, 1998.
  21. [Szer et al., 2005] Daniel Szer, Franc ¸ois Charpillet, and Shlomo Zilberstein. MAA*: A heuristic search algorithm for solving de- centralized POMDPs. In Proc. of the 21st Conf. on Uncertainty in Artificial Intelligence, pages 576-590, 2005.
  22. [Toussaint and Storkey, 2006] Marc Toussaint and Amos Storkey. Probabilistic inference for solving discrete and continuous state Markov decision processes. In Proc. of the 23rd Int'l Conf. on Machine learning, pages 945-952, 2006.
  23. [Toussaint et al., 2008] Marc Toussaint, Laurent Charlin, and Pas- cal Poupart. Hierarchical POMDP controller optimization by likelihood maximization. In Proc. of the 24th Conf. on Uncer- tainty in Artificial Intelligence, pages 562-570, 2008.
  24. [Vlassis and Toussaint, 2009] Nikos Vlassis and Marc Toussaint. Model-free reinforcement learning as mixture learning. In Proc. of the 26th Int'l Conf. on Machine Learning, pages 1081-1088, 2009.
  25. [Vlassis et al., 2009] Nikos Vlassis, Marc Toussaint, Georgios Kontes, and Savas Piperidis. Learning model-free robot con- trol by a Monte Carlo EM algorithm. Autonomous Robots, 27(2):123-130, 2009.
  26. [Wei and Tanner, 1990] Greg C. G. Wei and Martin A. Tanner. A Monte Carlo implementation of the EM algorithm and the poor man's data augmentation algorithms. Journal of the American Statistical Association, 85(411):699-704, 1990.
  27. [Wu et al., 2010] Feng Wu, Shlomo Zilberstein, and Xiaoping Chen. Rollout sampling policy iteration for decentralized POMDPs. In Proc. of the 26th Conf. on Uncertainty in Artifi- cial Intelligence, pages 666-673, 2010.
  28. [Zhang and Lesser, 2011] Chongjie Zhang and Victor Lesser. Co- ordinated multi-agent reinforcement learning in networked dis- tributed POMDPs. In Proc. of the 25th AAAI Conf. on Artificial Intelligence, pages 764-770, 2011.
  29. [Zhang et al., 2007] Xinhua
  30. Zhang, Douglas Aberdeen, and S.V.N. Vishwanathan. Conditional random fields for multi-agent rein- forcement learning. In Proc. of the 24th Int'l Conf. on Machine learning, pages 1143-1150, 2007.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards