Transition-Independent Decentralized Markov Decision Processes

Raphen Becker, Shlomo Zilberstein, Victor Lesser, and Claudia V. Goldman. Transition-Independent Decentralized Markov Decision Processes. Proceedings of the Second International Conference on Autonomous Agents and Multi Agent Systems (AAMAS), 41-48, Melbourne, Australia, 2003.

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 NEXPhard, provides a partial explanation. To overcome this complexity barrier, we identify a general class of transitionindependent 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 rst e ective 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.

Bibtex entry:

@inproceedings{BZLGaamas03,
  author	= {Raphen Becker and Shlomo Zilberstein and Victor Lesser
                   and Claudia V. Goldman},
  title		= {Transition-Independent Decentralized {M}arkov Decision Processes},
  booktitle     = {Proceedings of the Second International Conference on Autonomous
                   Agents and Multi Agent Systems},
  year		= {2003},
  pages		= {41-48},
  address       = {Melbourne, Australia},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/BZLGaamas03.html}
}

shlomo@cs.umass.edu