Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysis
This work addresses privacy and efficiency issues in decentralized multi-agent reinforcement learning, representing an incremental improvement over existing methods.
The paper tackles the problem of inefficient sample and communication usage in decentralized actor-critic algorithms for multi-agent systems, achieving state-of-the-art sample complexities of O(ε^{-2} ln(ε^{-1})) for AC and O(ε^{-3} ln(ε^{-1})) for NAC with communication complexity O(ε^{-1} ln(ε^{-1})).
Actor-critic (AC) algorithms have been widely adopted in decentralized multi-agent systems to learn the optimal joint control policy. However, existing decentralized AC algorithms either do not preserve the privacy of agents or are not sample and communication-efficient. In this work, we develop two decentralized AC and natural AC (NAC) algorithms that are private, and sample and communication-efficient. In both algorithms, agents share noisy information to preserve privacy and adopt mini-batch updates to improve sample and communication efficiency. Particularly for decentralized NAC, we develop a decentralized Markovian SGD algorithm with an adaptive mini-batch size to efficiently compute the natural policy gradient. Under Markovian sampling and linear function approximation, we prove the proposed decentralized AC and NAC algorithms achieve the state-of-the-art sample complexities $\mathcal{O}\big(ε^{-2}\ln(ε^{-1})\big)$ and $\mathcal{O}\big(ε^{-3}\ln(ε^{-1})\big)$, respectively, and the same small communication complexity $\mathcal{O}\big(ε^{-1}\ln(ε^{-1})\big)$. Numerical experiments demonstrate that the proposed algorithms achieve lower sample and communication complexities than the existing decentralized AC algorithm.