Decentralized Actor-Critic (AC) algorithms have been widely utilized for
multi-agent reinforcement learning (MARL) and have achieved remarkable success.
Apart from its empirical success, the theoretical convergence property of
decentralized AC algorithms is largely unexplored. Most of the existing
finite-time convergence results are derived based on either double-loop update
or two-timescale step sizes rule, and this is the case even for centralized AC
algorithm under a single-agent setting. In practice, the
\emph{single-timescale} update is widely utilized, where actor and critic are
updated in an alternating manner with step sizes being of the same order. In
this work, we study a decentralized \emph{single-timescale} AC
algorithm.Theoretically, using linear approximation for value and reward
estimation, we show that the algorithm has sample complexity of
$\tilde{\mathcal{O}}(\varepsilon^{-2})$ under Markovian sampling, which matches
the optimal complexity with a double-loop implementation (here,
$\tilde{\mathcal{O}}$ hides a logarithmic term). When we reduce to the
single-agent setting, our result yields new sample complexity for centralized
AC using a single-timescale update scheme. The central to establishing our
complexity results is \emph{the hidden smoothness of the optimal critic
variable} we revealed. We also provide a local action privacy-preserving
version of our algorithm and its analysis. Finally, we conduct experiments to
show the superiority of our algorithm over the existing decentralized AC
algorithms.

本文研究了分散式单时间尺度的演员 - 评论家算法，并利用线性近似展示了其样本复杂度为 $\tilde {\mathcal {O}}(\varepsilon^{-2})$, 与双循环实现相匹配。此外，我们提供了一种本地化的算法及其分析，并通过实验表明了我们的算法优于现有的分散式演员评论家算法。