Local Stochastic Approximation: A Unified View of Federated Learning and Distributed Multi-Task Reinforcement Learning Algorithms

Abstract

Motivated by broad applications in reinforcement learning and federated learning, we study local stochastic approximation over a network of agents, where their goal is to find the root of an operator composed of the local operators at the agents. Our focus is to characterize the finite-time performance of this method when the data at each agent are generated from Markov processes, and hence they are dependent. In particular, we provide the convergence rates of local stochastic approximation for both constant and time-varying step sizes. Our results show that these rates are within a logarithmic factor of the ones under independent data. We then illustrate the applications of these results to different interesting problems in multi-task reinforcement learning and federated learning.

References in corpus (9)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures
• Massively Parallel Methods for Deep Reinforcement Learning
• An Analysis of Reinforcement Learning with Function Approximation
• Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization
• Gradient Surgery for Multi-Task Learning
• A Finite Time Analysis of Two Time-Scale Actor Critic Methods
• Convergence Rates of Accelerated Markov Gradient Descent with Applications in Reinforcement Learning
• A Decentralized Policy Gradient Approach to Multi-task Reinforcement Learning

Cited by in corpus (1)

• The Gradient Convergence Bound of Federated Multi-Agent Reinforcement Learning with Efficient Communication