Finite-time Performance Of Distributed Temporal Difference Learning With Linear Function Approximation

Abstract

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

Stats

• citations18
• S2 citations—
• github stars0
• HF likes0
• heat score9.59
• arxiv keydoan2019finite

Related papers

• Finite-sample Analysis Of Decentralized Temporal-difference Learning With Linear Function Approximation (2019)0.00
• Adaptive Temporal Difference Learning With Linear Function Approximation (2020)0.00
• A Finite Time Analysis Of Temporal Difference Learning With Linear Function Approximation (2018)0.00
• Exact Formulas For Finite-time Estimation Errors Of Decentralized Temporal Difference Learning With Linear Function Approximation (2022)0.00
• Accelerated Distributional Temporal Difference Learning With Linear Function Approximation (2025)0.00
• Fast Multi-agent Temporal-difference Learning Via Homotopy Stochastic Primal-dual Optimization (2019)0.00
• Distributed Value Function Approximation For Collaborative Multi-agent Reinforcement Learning (2020)8.60
• A Finite Sample Analysis Of Distributional TD Learning With Linear Function Approximation (2025)0.00