Approximate Linear Programming and Decentralized Policy Improvement in
  Cooperative Multi-agent Markov Decision Processes
Lakshmi Mandal Chandrashekar Lakshminarayanan Shalabh Bhatnagar
In this work, we consider a `cooperative' multi-agent Markov decision process
(MDP) involving m greater than 1 agents, where all agents are aware of the
system model. At each decision epoch, all the m agents cooperatively select
actions in order to maximize a common long-term objective. Since the number of
actions grows exponentially in the number of agents, policy improvement is
computationally expensive. Recent works have proposed using decentralized
policy improvement in which each agent assumes that the decisions of the other
agents are fixed and it improves its decisions unilaterally. Yet, in these
works, exact values are computed. In our work, for cooperative multi-agent
finite and infinite horizon discounted MDPs, we propose suitable approximate
policy iteration algorithms, wherein we use approximate linear programming to
compute the approximate value function and use decentralized policy
improvement. Thus our algorithms can handle both large number of states as well
as multiple agents. We provide theoretical guarantees for our algorithms and
also demonstrate the performance of our algorithms on some numerical examples.