Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysis
Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysis
复制标题
DOI：
--
复制
发表时间：
2021-09
期刊：
影响因子：
--
通讯作者：
Ziyi Chen;Yi Zhou;Rongrong Chen;Shaofeng Zou
中科院分区：
文献类型：
--
作者：
Ziyi Chen;Yi Zhou;Rongrong Chen;Shaofeng Zou
Actor-Critic（AC）算法被广泛应用于分散多智能体系统中学习最优联合控制策略。然而，现有的分散式AC算法要么不保护代理的隐私，要么不是样本和通信效率。在这项工作中，我们开发了两个分散的AC和自然AC（NAC）算法，它们是私有的，样本和通信效率高。在这两种算法中，代理共享噪声信息以保护隐私，并采用小批量更新来提高样本和通信效率。特别是对于分散的NAC，我们开发了一个分散的马尔可夫SGD算法，具有自适应的小批量大小，以有效地计算自然的政策梯度。在马尔可夫采样和线性函数近似下，我们证明了所提出的分散AC和NAC算法达到了最先进的样本复杂度$\mathcal{O}\big（\n ^{-2}\ln（\n ^{-1}）\big）$和$\mathcal{O}\big（\mathcal {O}\big（\mathcal {-1}\ln（\mathcal {-1}）\big））$，以及相同的小通信复杂度$\mathcal{O}\big（\mathcal {-1}\ln（\mathcal {-1}\big）$。数值实验表明，所提出的算法实现了较低的采样和通信复杂度比现有的分散AC算法。
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(\epsilon^{-2}\ln(\epsilon^{-1})\big)$ and $\mathcal{O}\big(\epsilon^{-3}\ln(\epsilon^{-1})\big)$, respectively, and the same small communication complexity $\mathcal{O}\big(\epsilon^{-1}\ln(\epsilon^{-1})\big)$. Numerical experiments demonstrate that the proposed algorithms achieve lower sample and communication complexities than the existing decentralized AC algorithm.