Finite-Time Performance of Distributed Temporal-Difference Learning with Linear Function Approximation

We study the policy evaluation problem in multi-agent reinforcement learning, modeled by a Markov decision process. In this problem, the agents operate in a common environment under a fixed control policy, working together to discover the value (global discounted accumulative reward) associated with each environmental state. Over a series of time steps, the agents act, get rewarded, update their local estimate of the value function, then communicate with their neighbors. The local update at each agent can be interpreted as a distributed variant of the popular temporal difference learning methods {\sf TD}$ (\lambda)$. Our main contribution is to provide a finite-analysis on the performance of this distributed {\sf TD}$(\lambda)$ algorithm for both constant and time-varying step sizes. The key idea in our analysis is to use the geometric mixing time $\tau$ of the underlying Markov chain, that is, although the "noise" in our algorithm is Markovian, its dependence is very weak at samples spaced out at every $\tau$. We provide an explicit upper bound on the convergence rate of the proposed method as a function of the network topology, the discount factor, the constant $\lambda$, and the mixing time $\tau$. Our results also provide a mathematical explanation for observations that have appeared previously in the literature about the choice of $\lambda$. Our upper bound illustrates the trade-off between approximation accuracy and convergence speed implicit in the choice of $\lambda$. When $\lambda=1$, the solution will correspond to the best possible approximation of the value function, while choosing $\lambda = 0$ leads to faster convergence when the noise in the algorithm has large variance.