Solving Transition Independent Decentralized
Markov Decision Processes
Raphen Becker
Shlomo Zilberstein
Victor Lesser
Claudia V. Goldman
Abstract
Formal treatment of collaborative multi-agent systems has been lagging
behind the
rapid progress in sequential decision making by individual agents.
Recent work in the area
of decentralized Markov Decision Processes (MDPs) has contributed to
closing this gap,
but the computational complexity of these models remains a serious
obstacle. To overcome
this complexity barrier, we identify a specific class of decentralized
MDPs in which the
agents' transitions are independent. The class consists of
independent collaborating agents
that are tied together through a structured global reward function that
depends on all of
their histories of states and actions. We present a novel algorithm for
solving this class
of problems and examine its properties, both as an optimal algorithm and
as an anytime
algorithm. To the best of our knowledge, this is the first algorithm to
optimally solve a
non-trivial subclass of decentralized MDPs. It lays the foundation for
further work in this
area on both exact and approximate algorithms.
Download
[pdf]