Fast Multi-Agent Temporal-Difference Learning via Homotopy Stochastic Primal-Dual Optimization

Abstract

We study the policy evaluation problem in multi-agent reinforcement learning where a group of agents, with jointly observed states and private local actions and rewards, collaborate to learn the value function of a given policy via local computation and communication over a connected undirected network. This problem arises in various large-scale multi-agent systems, including power grids, intelligent transportation systems, wireless sensor networks, and multi-agent robotics. When the dimension of state-action space is large, the temporal-difference learning with linear function approximation is widely used. In this paper, we develop a new distributed temporal-difference learning algorithm and quantify its finite-time performance. Our algorithm combines a distributed stochastic primal-dual method with a homotopy-based approach to adaptively adjust the learning rate in order to minimize the mean-square projected Bellman error by taking fresh online samples from a causal on-policy trajectory. We explicitly take into account the Markovian nature of sampling and improve the best-known finite-time error bound from $O(1/\sqrt{T})$ to~$O(1/T)$, where $T$ is the total number of iterations.

29 pages, 4 figures

References in corpus (11)

• Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents
• Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization
• Finite-Sample Analysis of Proximal Gradient TD Algorithms
• Finite-Sample Analysis for SARSA with Linear Function Approximation
• Finite-Time Analysis of Distributed TD(0) with Linear Function Approximation for Multi-Agent Reinforcement Learning
• Characterizing the Exact Behaviors of Temporal Difference Learning Algorithms Using Markov Jump Linear System Theory
• Convergent Tree Backup and Retrace with Function Approximation
• Finite Sample Analysis of the GTD Policy Evaluation Algorithms in Markov Setting
• Decentralized Multi-Agent Reinforcement Learning with Networked Agents: Recent Advances
• Solving Non-smooth Constrained Programs with Lower Complexity than $\mathcal{O}(1/\epsilon )$: A Primal-Dual Homotopy Smoothing Approach
• Primal-Dual Distributed Temporal Difference Learning

Cited by in corpus (1)

• Primal-Dual Distributed Temporal Difference Learning