Transition-Independent Decentralized Markov Decision Processes
Raphen Becker
Shlomo Zilberstein
Victor Lesser
Claudia V. Goldman
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.
Download
[pdf]