  Multi-agent actor-critic algorithms are an important part of the
Reinforcement Learning paradigm. We propose three fully decentralized
multi-agent natural actor-critic (MAN) algorithms in this work. The objective
is to collectively find a joint policy that maximizes the average long-term
return of these agents. In the absence of a central controller and to preserve
privacy, agents communicate some information to their neighbors via a
time-varying communication network. We prove convergence of all the 3 MAN
algorithms to a globally asymptotically stable set of the ODE corresponding to
actor update; these use linear function approximations. We show that the
Kullback-Leibler divergence between policies of successive iterates is
proportional to the objective function's gradient. We observe that the minimum
singular value of the Fisher information matrix is well within the reciprocal
of the policy parameter dimension. Using this, we theoretically show that the
optimal value of the deterministic variant of the MAN algorithm at each iterate
dominates that of the standard gradient-based multi-agent actor-critic (MAAC)
algorithm. To our knowledge, it is a first such result in multi-agent
reinforcement learning (MARL). To illustrate the usefulness of our proposed
algorithms, we implement them on a bi-lane traffic network to reduce the
average network congestion. We observe an almost 25\% reduction in the average
congestion in 2 MAN algorithms; the average congestion in another MAN algorithm
is on par with the MAAC algorithm. We also consider a generic $15$ agent MARL;
the performance of the MAN algorithms is again as good as the MAAC algorithm.
