DASA: 遅延適応型マルチエージェント確率近似
DASA: Delay-Adaptive Multi-Agent Stochastic Approximation
非同期で無制限の遅延がある環境で、複数エージェントが並列に確率近似問題を解くための遅延適応アルゴリズムを提案し、マルコフ連鎖サンプリング下でN倍の収束加速を達成する有限時間解析を与えた。
著者: Nicolò Dal Fabbro, Arman Adibi, H. Vincent Poor, Sanjeev R. Kulkarni, Aritra Mitra, George J. Pappas
分類: cs.AI, cs.RO, cs.SY, eess.SY, math.OC, stat.ML
原文アブストラクト
We consider a setting in which $N$ agents aim to speedup a common Stochastic Approximation (SA) problem by acting in parallel and communicating with a central server. We assume that the up-link transmissions to the server are subject to asynchronous and potentially unbounded time-varying delays. To mitigate the effect of delays and stragglers while reaping the benefits of distributed computation, we propose \texttt{DASA}, a Delay-Adaptive algorithm for multi-agent Stochastic Approximation. We provide a finite-time analysis of \texttt{DASA} assuming that the agents' stochastic observation processes are independent Markov chains. Significantly advancing existing results, \texttt{DASA} is the first algorithm whose convergence rate depends only on the mixing time $\tau_{mix}$ and on the average delay $\tau_{avg}$ while jointly achieving an $N$-fold convergence speedup under Markovian sampling. Our work is relevant for various SA applications, including multi-agent and distributed temporal difference (TD) learning, Q-learning and stochastic optimization with correlated data.
