Finite-Time Convergence Rates of Decentralized Stochastic Approximation With Applications in Multi-Agent and Multi-Task Learning

• 成果类型: Article
• 署名作者: Zeng, Sihan; Doan, Thinh T.; Romberg, Justin
• 署名单位: University System of Georgia; Georgia Institute of Technology; Virginia Polytechnic Institute & State University
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2022.3201034
• 发表日期: 2023
• 页码: 2758-2773
• 关键词: Markov processes; CONVERGENCE; Robot sensing systems; Approximation algorithms; Q-learning; multitasking; stability analysis; distributed optimization; Reinforcement Learning; stochastic approximation (SA)

摘要

In this article, we study a decentralized variant of stochastic approximation (SA), a data-driven approach for finding the root of an operator under noisy measurements. A network of agents, each with its own operator and data observations, cooperatively find the fixed point of the aggregate operator over a decentralized communication graph. Our main contribution is to provide a finite-time analysis of this decentralized SA method when the data observed at each agent are sampled from a Markov process; this lack of independence makes the iterates biased and (potentially) unbounded. Under fairly standard assumptions, we show that the convergence rate of the proposed method is essentially the same as if the samples were independent, differing only by a log factor that accounts for the mixing time of the Markov processes. The key idea in our analysis is to introduce a novel Lyapunov-Razumikhin function, motivated by the one used in analyzing the stability of delayed ordinary differential equations. We also discuss applications of the proposed method on a number of interesting learning problems in multiagent systems.