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.

我们提出了适用于合作多智能体有限和无限时域折扣马尔可夫决策过程的逼近策略迭代算法，其中使用近似线性规划计算近似值函数并实施分散策略改进。

合作多智能体马尔可夫决策过程中的近似线性规划和分散策略改进

Approximate Linear Programming and Decentralized Policy Improvement in  Cooperative Multi-agent Markov Decision Processes

We consider finite and infinite horizon dynamic programming problems, where
the control at each stage consists of several distinct decisions, each one made
by one of several agents. We introduce an approach, whereby at every stage,
each agent's decision is made by executing a local rollout algorithm that uses
a base policy, together with some coordinating information from the other
agents. The amount of local computation required at every stage by each agent
is independent of the number of agents, while the amount of total computation
(over all agents) grows linearly with the number of agents. By contrast, with
the standard rollout algorithm, the amount of total computation grows
exponentially with the number of agents. Despite the drastic reduction in
required computation, we show that our algorithm has the fundamental cost
improvement property of rollout: an improved performance relative to the base
policy. We also discuss possibilities to improve further the method's
computational efficiency through limited agent coordination and parallelization
of the agents' computations. Finally, we explore related approximate policy
iteration algorithms for infinite horizon problems, and we prove that the cost
improvement property steers the algorithm towards convergence to an
agent-by-agent optimal policy.

本文介绍了一种基于本地回滚算法的多智能体决策方法，该方法通过配合其他智能体的协调信息，在每个阶段使每个智能体的决策都能够独立计算，并且与智能体数量无关。此外，我们探讨了并行化智能体计算和近似策略迭代算法等方法来进一步提高本方法的计算效率，并证明了本文算法可以收敛到智能体的最优策略。