Multi-Agent Off-Policy TDC with Near-Optimal Sample and Communication Complexity
Ziyi Chen, Yi Zhou, Rong‐Rong Chen · 2021 55th Asilomar Conference on Signals, Systems, and Computers · 2021
The finite-time convergence of off-policy TD learning has been comprehensively studied recently. However, such a type of convergence has not been well established for off-policy TD learning in the multi-agent setting, which covers broader applications and is fundamentally more challenging. This work develops a decentralized TD with correction (TDC) algorithm for multi-agent off-policy TD learning under Markovian sampling. In particular, our algorithms preserve full privacy of the actions, policies and rewards of the agents, and adopt mini-batch sampling to reduce the sampling variance and communication frequency. Under Markovian sampling and linear function approximation, we proved that the finite-time sample complexity of the algorithm for achieving an ϵ-accurate solution is in the order of ${\mathcal{O}}\left({{ \in ^{ - 1}}\ln { \in ^{ - 1}}}\right)$, matching the near-optimal sample complexity of centralized TD(0) and TDC. Importantly, the communication complexity of our algorithm is in the order of ${\mathcal{O}}\left({\ln { \in ^{ - 1}}}\right)$, which is significantly lower than the communication complexity ${\mathcal{O}}\left({{ \in ^{ - 1}}\ln { \in ^{ - 1}}}\right)$ of the existing decentralized TD(0). Experiments corroborate our theoretical findings.