### Abstract

This paper considers a novel multi-agent linear stochastic approximationalgorithm driven by Markovian noise and general consensus-type interaction, inwhich each agent evolves according to its local stochastic approximationprocess which depends on the information from its neighbors. Theinterconnection structure among the agents is described by a time-varyingdirected graph. While the convergence of consensus-based stochasticapproximation algorithms when the interconnection among the agents is describedby doubly stochastic matrices (at least in expectation) has been studied, lessis known about the case when the interconnection matrix is simply stochastic.For any uniformly strongly connected graph sequences whose associatedinteraction matrices are stochastic, the paper derives finite-time bounds onthe mean-square error, defined as the deviation of the output of the algorithmfrom the unique equilibrium point of the associated ordinary differentialequation. For the case of interconnection matrices being stochastic, theequilibrium point can be any unspecified convex combination of the localequilibria of all the agents in the absence of communication. Both the caseswith constant and time-varying step-sizes are considered. In the case when theconvex combination is required to be a straight average and interaction betweenany pair of neighboring agents may be uni-directional, so that doublystochastic matrices cannot be implemented in a distributed manner, the paperproposes a push-sum-type distributed stochastic approximation algorithm andprovides its finite-time bound for the time-varying step-size case byleveraging the analysis for the consensus-type algorithm with stochasticmatrices and developing novel properties of the push-sum algorithm.