Finite-Time Analysis of Distributed TD(0) with Linear Function Approximation for Multi-Agent Reinforcement Learning

Abstract

We study the policy evaluation problem in multi-agent reinforcement learning. In this problem, a group of agents works cooperatively to evaluate the value function for the global discounted accumulative reward problem, which is composed of local rewards observed by the agents. 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 consensus-based variant of the popular temporal difference learning algorithm TD(0). While distributed reinforcement learning algorithms have been presented in the literature, almost nothing is known about their convergence rate. Our main contribution is providing a finite-time analysis for the convergence of the distributed TD(0) algorithm. We do this when the communication network between the agents is time-varying in general. We obtain an explicit upper bound on the rate of convergence of this algorithm as a function of the network topology and the discount factor. Our results mirror what we would expect from using distributed stochastic gradient descent for solving convex optimization problems.

Cited by in corpus (21)

• A Tutorial on Ultra-Reliable and Low-Latency Communications in 6G: Integrating Domain Knowledge into Deep Learning
• Decentralized Multi-Agent Reinforcement Learning with Networked Agents: Recent Advances
• Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning
• Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopes
• Fast Multi-Agent Temporal-Difference Learning via Homotopy Stochastic Primal-Dual Optimization
• Multi-Agent Trust Region Policy Optimization
• A Decentralized Policy Gradient Approach to Multi-task Reinforcement Learning
• A Multi-Agent Off-Policy Actor-Critic Algorithm for Distributed Reinforcement Learning
• Finite-Sample Analysis of Decentralized Temporal-Difference Learning with Linear Function Approximation
• MARL with General Utilities via Decentralized Shadow Reward Actor-Critic
• Finite-Sample Analysis For Decentralized Batch Multi-Agent Reinforcement Learning With Networked Agents
• Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysis
• Distributed TD(0) with Almost No Communication
• Finite-Time Error Bounds for Distributed Linear Stochastic Approximation
• Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexity
• Finite-Time Performance of Distributed Two-Time-Scale Stochastic Approximation
• Programming and Deployment of Autonomous Swarms using Multi-Agent Reinforcement Learning
• Distributed Policy Gradient with Variance Reduction in Multi-Agent Reinforcement Learning
• H-TD2: Hybrid Temporal Difference Learning for Adaptive Urban Taxi Dispatch
• A Law of Iterated Logarithm for Multi-Agent Reinforcement Learning