  Multi-agent Markov Decision Processes (MMDPs) arise in a variety of
applications including target tracking, control of multi-robot swarms, and
multiplayer games. A key challenge in MMDPs occurs when the state and action
spaces grow exponentially in the number of agents, making computation of an
optimal policy computationally intractable for medium- to large-scale problems.
One property that has been exploited to mitigate this complexity is transition
independence, in which each agent's transition probabilities are independent of
the states and actions of other agents. Transition independence enables
factorization of the MMDP and computation of local agent policies but does not
hold for arbitrary MMDPs. In this paper, we propose an approximate transition
dependence property, called $\delta$-transition dependence and develop a metric
for quantifying how far an MMDP deviates from transition independence. Our
definition of $\delta$-transition dependence recovers transition independence
as a special case when $\delta$ is zero. We develop a polynomial time algorithm
in the number of agents that achieves a provable bound on the global optimum
when the reward functions are monotone increasing and submodular in the agent
actions. We evaluate our approach on two case studies, namely, multi-robot
control and multi-agent patrolling example.
