Publication - Transition-Independent Decentralized Markov Decision Processes

Authors: Becker, Raphen; Zilberstein, Shlomo; Lesser, Victor; Goldman, Claudia V.
Title: Transition-Independent Decentralized Markov Decision Processes
Abstract: There has been substantial progress with formal models for sequential decision making by individual agents using the Markov decision process (MDP). However, similar treatment of multi-agent systems is lacking. A recent complexity result, showing that solving decentralized MDPs is NEXP-hard, provides a partial explanation. To overcome this complexity barrier, we identify a general class of transition-independent decentralized MDPs that is widely applicable. The class consists of independent collaborating agents that are tied together through a global reward function that depends upon both of their histories. We present a novel algorithm for solving this class of problems and examine its properties. The result is the first effective technique to solve optimally a class of decentralized MDPs. This lays the foundation for further work in this area on both exact and approximate solutions.
Keywords: Coordination, Distributed MDP, MDP, Multi-Agent Systems, Planning
Publication: Proceedings of the Second International Joint Conference on Autonomous Agents and Multi Agent Systems, pp. 41 - 48
Location: Melbourne, Australia
Publisher: ACM Press
Date: July 2003
Sources: PDF: http://mas.cs.umass.edu/~raphen/Papers/AAMAS-03/p470-becker.pdf
PDF: /Documents/raphen/AAMAS-03/p470-becker.pdf
PDF: http://cs.umass.edu/~raphen/publications/p470-becker.pdf
Notes: Received BEST PAPER AWARD.
Reference: Becker, Raphen; Zilberstein, Shlomo; Lesser, Victor; Goldman, Claudia V.. Transition-Independent Decentralized Markov Decision Processes. Proceedings of the Second International Joint Conference on Autonomous Agents and Multi Agent Systems, ACM Press, pp. 41-48. July 2003. Received BEST PAPER AWARD.
bibtex: 
@inproceedings{Becker-253,
  author    = "Raphen Becker and Shlomo Zilberstein and Victor
               Lesser and Claudia V. Goldman",
  title     = "{Transition-Independent Decentralized Markov
               Decision Processes}",
  booktitle = "Proceedings of the Second International Joint
               Conference on Autonomous Agents and Multi Agent
               Systems",
  publisher = "ACM Press",
  pages     = "41-48",
  month     = "July",
  year      = "2003",
  address   = "Melbourne, Australia",
  url       = "http://mas.cs.umass.edu/paper/253",
}