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