Proceedings

Average-Reward Decentralized Markov Decision Processes

Download BibTeX Cite

Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 1997-2001.

© 2007 International Joint Conferences on Artificial Intelligence

Abstract

Formal analysis of decentralized decision making has become a thriving research area in recent years, producing a number of multi-agent extensions of Markov decision processes. While much of the work has focused on optimizing discounted cumulative reward, optimizing average reward is sometimes a more suitable criterion. We formalize a class of such problems and analyze its characteristics, showing that it is NP complete and that optimal policies are deterministic. Our analysis lays the foundation for designing two optimal algorithms. Experimental results with a standard problem from the literature illustrate the applicability of these solution techniques.

  1. [Arapostathis et al., 1993] A. Arapostathis, V. S. Borkar, E. Fernandez-Gaucherand, M. K. Ghosh, and S. Markus. Discrete time controlled Markov processes with average cost criterion -a survey. SIAM Journal of Control and Op- timization, 31:282-344, 1993.
  2. [Becker et al., 2004] Raphen Becker, Shlomo Zilberstein, Victor Lesser, and Claudia V. Goldman. Solving transition independent decentralized Markov decision processes. Journal of Artificial Intelligence Research, 22:423-455, 2004.
  3. [Bernstein et al., 2000] Daniel S. Bernstein, Shlomo Zilber- stein, and Neil Immerman. The complexity of decentral- ized control of Markov decision processes. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, pages 32-37, 2000.
  4. [Bertsekas, 2003] Dimitri P. Bertsekas. Nonlinear program- ming. Athena Scientific, 2003.
  5. [Filar and Vrieze, 1996] Jerzy Filar and Koos Vrieze. Com- petitive Markov decision processes. Springer, 1996.
  6. [Hajek, 1984] Bruce Hajek. Optimal control of two interact- ing service stations. In IEEE Transactions on Automatic Control, volume 29, pages 491-499, 1984.
  7. [Madani, 2000] Omid Madani. Complexity results for infinite-horizon Markov decision processes. PhD thesis, University of Washington, 2000.
  8. [Mahadevan, 1996] Sridhar Mahadevan. Average reward re- inforcement learning: Foundations, algorithms, and em- pirical results. Machine Learning, 22(1-3):159-195, 1996.
  9. [Nair et al., 2003] R. Nair, M. Tambe, M. Yokoo, D. Pyna- dath, and S. Marsella. Taming decentralized POMDPs: Towards efficient policy computation for multiagent set- tings. In Proceedings of the International Joint Conference on Artificial Inteligence, pages 705-711, 2003. IJCAI
  10. [Ooi and Wornell, 1996] J. M. Ooi and G. W. Wornell. De- centralized control of a multiple access broadcast channel: performance bounds. In Proceeding of the IEEE Confer- ence on Decision and Control, volume 1, pages 293-298, 1996.
  11. [Puterman, 2005] Martin L. Puterman. Markov decision pro- cesses: Discrete stochastic dynamic programming. John Wiley & Sons, Inc., 2005.
  12. [Rosberg, 1983] Z. Rosberg. Optimal decentralized control in a multiaccess channel with partial information. IEEE Transactions on Automatic Control, 28:187-193, 1983.
  13. [Sandholm et al., 2005] Tuomas Sandholm, Andrew Gilpin, and Vincent Conitzer. Mixed-integer programming meth- ods for finding Nash equilibria. In Proceedings of the National Conference on Aritifical Intelligence, pages 495- 501, 2005.
  14. [Tangamchit et al., 2002] Poj Tangamchit, John M. Dolan, and Pradeep K. Koshla. The necessity of average rewards in cooperative multirobot learning. In Proceedings of the IEEE International Conference on Robotics and Automa- tion, pages 1296-1301, 2002.

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

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