One of the challenges for multi-agent reinforcement learning (MARL) is
designing efficient learning algorithms for a large system in which each agent
has only limited or partial information of the entire system. While exciting
progress has been made to analyze decentralized MARL with the network of agents
for social networks and team video games, little is known theoretically for
decentralized MARL with the network of states for modeling self-driving
vehicles, ride-sharing, and data and traffic routing.
This paper proposes a framework of localized training and decentralized
execution to study MARL with network of states. Localized training means that
agents only need to collect local information in their neighboring states
during the training phase; decentralized execution implies that agents can
execute afterwards the learned decentralized policies, which depend only on
agents' current states.
The theoretical analysis consists of three key components: the first is the
reformulation of the MARL system as a networked Markov decision process with
teams of agents, enabling updating the associated team Q-function in a
localized fashion; the second is the Bellman equation for the value function
and the appropriate Q-function on the probability measure space; and the third
is the exponential decay property of the team Q-function, facilitating its
approximation with efficient sample efficiency and controllable error.
The theoretical analysis paves the way for a new algorithm LTDE-Neural-AC,
where the actor-critic approach with over-parameterized neural networks is
proposed. The convergence and sample complexity is established and shown to be
scalable with respect to the sizes of both agents and states. To the best of
our knowledge, this is the first neural network based MARL algorithm with
network structure and provably convergence guarantee.

提出了基于 LTDE-Neural-AC 和演员 - 评论家方法的多智能体强化学习算法，应用于自驾车、拼车、数据和交通路由模型的图网络，其解决了分散式多智能体强化学习网络结构的问题，并具有收敛保证的优势。