Finite-Time Analysis of Decentralized Temporal-Difference Learning with Linear Function Approximation

Sun, Jun1; Wang, Gang2; Giannakis, Georgios B.2; Yang, Qinmin1; Yang, Zaiyue3

2020

INTERNATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AND STATISTICS, VOL 108

108

75 ARLINGTON ST, STE 300, BOSTON, MA 02116-3936 USA

ADDISON-WESLEY PUBL CO

Motivated by the emerging use of multi-agent reinforcement learning (MARL) in various engineering applications, we investigate the policy evaluation problem in a fully decentralized setting, using temporal-difference (TD) learning with linear function approximation to handle large state spaces in practice. The goal of a group of agents is to collaboratively learn the value function of a given policy from locally private rewards observed in a shared environment, through exchanging local estimates with neighbors. Despite their simplicity and widespread use, our theoretical understanding of such decentralized TD learning algorithms remains limited. Existing results were obtained based on i.i.d. data samples, or by imposing an 'additional' projection step to control the 'gradient' bias incurred by the Markovian observations. In this paper, we provide a finite-sample analysis of the fully decentralized TD(0) learning under both i.i.d. as well as Markovian samples, and prove that all local estimates converge linearly to a neighborhood of the optimum. The resultant error bounds are the first of its type-in the sense that they hold under the most practical assumptions - which is made possible by means of a novel multi-step Lyapunov analysis.

其他

英语

CPCI

NSFC[61873118][61673347][U1609214][61751205] ; Dept. of Science and Technology of Guangdong Province[2018A050506003] ; NSF[1711471][1901134] ; Key R&D Program of Zhejiang Province[2019C01050]

Computer Science ; Mathematics

Computer Science, Artificial Intelligence ; Statistics & Probability

WOS:000559931303034

Web of Science

1.Zhejiang Univ, Hangzhou, Zhejiang, Peoples R China
2.Univ Minnesota, Minneapolis, MN 55455 USA
3.Southern Univ Sci & Technol, Shenzhen, Peoples R China

Sun, Jun,Wang, Gang,Giannakis, Georgios B.,et al. Finite-Time Analysis of Decentralized Temporal-Difference Learning with Linear Function Approximation[C]. 75 ARLINGTON ST, STE 300, BOSTON, MA 02116-3936 USA:ADDISON-WESLEY PUBL CO,2020.