  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.
