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

Thanks to its generality, RL has been widely studied in many areas, such as control theory, game theory, operations research, multi-agent systems, machine learning, artificial intelligence, and statistics [23]. In recent years, combining with deep learning, RL has demonstrated its great potential in addressing challenging practical control and optimization problems [17, 21]. Among all possible algorithms, the temporal difference (TD) learning has arguably become one of the most popular RL algorithms so far, which is further dominated by the celebrated TD(0) algorithm [22]. TD learning provides an iterative process to update an estimate of the so-termed value function v π(s) with respect to a given policy π based on temporally successive samples. Dealing with a finite state space, the classical version of the TD(0) algorithm adopts a tabular representation for v π(s), which stores entry-wise value estimates on a per state basis. J. Sun and Q. Yang are with the College of Control Science and Engineering, and the State Key Laboratory of Industrial Control Technology, Zhejiang University, Hangzhou, China. G. Wang and G. B. Giannakis are with the Digital Technology Center and the Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455, USA. Z. Yang is with the Department of Mechanical and Energy Engineering, Southern University of Science and Technology, Shenzhen, China.