  We consider the networked multi-agent reinforcement learning (MARL) problem
in a fully decentralized setting, where agents learn to coordinate to achieve
the joint success. This problem is widely encountered in many areas including
traffic control, distributed control, and smart grids. We assume that the
reward function for each agent can be different and observed only locally by
the agent itself. Furthermore, each agent is located at a node of a
communication network and can exchanges information only with its neighbors.
Using softmax temporal consistency and a decentralized optimization method, we
obtain a principled and data-efficient iterative algorithm. In the first step
of each iteration, an agent computes its local policy and value gradients and
then updates only policy parameters. In the second step, the agent propagates
to its neighbors the messages based on its value function and then updates its
own value function. Hence we name the algorithm value propagation. We prove a
non-asymptotic convergence rate 1/T with the nonlinear function approximation.
To the best of our knowledge, it is the first MARL algorithm with convergence
guarantee in the control, off-policy and non-linear function approximation
setting. We empirically demonstrate the effectiveness of our approach in
experiments.
