Policy evaluation problems in multi-agent reinforcement learning (MARL) have attracted growing interest recently. In this setting, agents collaborate to learn the value of a given policy with private local rewards and jointly observed state-action pairs. However, existing fully decentralized algorithms treat each agent equally, without considering the communication structure of the agents over a given network, and the corresponding effects on communication and computation efficiency. In this paper, we propose a hierarchical distributed algorithm that differentiates the roles of each of the agents during the evaluation process. This method allows us to freely choose various mixing schemes (and corresponding mixing matrices that are not necessarily symmetric or doubly stochastic), in order to reduce the communication and computation cost, while still maintaining convergence at rates as fast as or even faster than the previous distributed algorithms. Theoretically, we show the proposed method, which contains existing distributed methods as a special case, achieves the same order of convergence rate as state-of-the-art methods. Extensive numerical experiments on real datasets verify that the performance of our approach indeed improves – sometimes significantly – over other advanced algorithms in terms of convergence and total communication efficiency.
Bibliographical noteFunding Information:
This work was partially supported by the DARPA Young Faculty Award N66001-14-1-4047, the Beijing Institute of Technology Research Fund Program for Young Scholars, and the Natural Science Foundation of China (under Grant 62002019).
© 2020 Elsevier B.V.
- Communication efficiency
- Distributed algorithm
- Multi-agent policy evaluation
- Optimization algorithm