--- title: "Finite-Time Convergence Rates of Decentralized Local Markovian Stochastic Approximation" authors: - "Pengfei Wang" - "Nenggan Zheng" doi: "10.24963/ijcai.2024/562" url: "https://ijcai.org/proceedings/2024/562" pdf: "https://ijcai.org/proceedings/2024/0562.pdf" venue: "Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence" year: 2024 pages: "5082-5090" track: "Main Track" keywords: - "Machine Learning: ML: Optimization" --- # Finite-Time Convergence Rates of Decentralized Local Markovian Stochastic Approximation Pengfei Wang, Nenggan Zheng *Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence*, pages 5082-5090. DOI: [10.24963/ijcai.2024/562](https://doi.org/10.24963/ijcai.2024/562) ## Abstract Markovian stochastic approximation has recently aroused a great deal of interest in many fields; however, it is not well understood in decentralized settings. Decentralized Markovian stochastic approximation is far more challenging than its single-agent counterpart due to the complex coupling structure between decentralized communication and Markovian noise-corrupted local updates. In this paper, a decentralized local markovian stochastic approximation (DLMSA) algorithm has been proposed and attains a near-optimal convergence rate. Specifically, we first provide a local variant of decentralized Markovian stochastic approximation so that each agent performs multiple local updates and then periodically communicate with its neighbors. Furthermore, we propose DLMSA with compressed communication (C-DLMSA) for further reducing the communication overhead. In this way, each agent only needs to communicate compressed information (e.g., sign compression) with its neighbors. We show that C-DLMSA enjoys the same convergence rate as that of the original DLMSA. Finally, we verify our theoretical results by applying our methods to solve multi-task reinforcement learning problems over multi-agent systems. ## Full text ## 1 Introduction Stochastic approximation (SA) is a class of iterative approaches for solving fixed-point equations in the presence of noise. Since its introduction in [Robbins and Monro, 1951], this type of method has received great interests due to its broad applications in many areas including stochastic optimization [Bottou et al., 2018] and reinforcement learning [Sutton and Barto, 2018]. In stochastic optimization, the stochastic gradient descent (SGD) algorithm is regarded as a SA method to find an optimal solution of a target objective function. In reinforcement learning (RL), Q-learning and TD-learning are popular SA algorithms used to solve the Bellman equations ∗Corresponding author [Bhandari et al., 2018; Srikant and Ying, 2019]. In RL, the SA algorithms naturally involve Markovian noise. Markovian SA, which is characterized by sampling data from Markov processes, has also found applications in many other fields, such as robust optimization [Duchi et al., 2012] and stochastic optimization over ergodic data [Dorfman and Levy, 2022; Alacaoglu and Lyu, 2023], where many existing algorithms can be viewed as different variants of Markovian SA. Distributed SA has emerged as a powerful class of algorithms, when training data are collected and stored at multiple agents. This distributed training paradigm primarily arises in many real-world applications, including multi-agent reinforcement learning [Zeng et al., 2021b; Sun et al., 2020], decentralized decision making [Lakshmanan and De Farias, 2008], distributed and parallel computing [Kushner and Yin, 1987; Jiang and Xu, 2008], etc. Although distributed training paradigm has been actively applied in various fields [Dean et al., 2012; Mnih et al., 2016], Markovian SA has not been well-studied in decentralized settings. As its name suggests, "decentralized" implies a more challenging setting where all agents must rely on communications to reach a consensus without any coordination from a central server. In this paper, we consider the Markovian SA problem on multi-agent systems: where ∀i ∈ {1, 2, · · · , n}, Hi(x, ξi) : Rd × Y → Rd is a general nonlinear operator, ξi ∈ Y is a random variable, and Hi(x) = Eξi∼µi [Hi(x, ξi)] is the expectation operator. We are interested in the case that ξi is sampled from a Markov process, whose stationary distribution is µi. In multi-agent systems, agents can interact with each other through an undirected connected network G = (V, E), where V = {1, 2, · · · , n} is the collection of agents and E is the set of communication links (i, j), i, j ∈ V that connect agents. Existing approaches to solving problem (1) typically use a specific "client/server" model for agent interaction where a central server is responsible for updating the global model. Specifically, [Doan, 2020] proposed a local SA algorithm and derived a convergence rate ˜ O(K/T), where K is the communication interval. It is worth noting that the convergence rate depends on the communication frequency. [Khodadadian et al., 2022] proposed a federated SA, and proved that the method achieves a convergence rate of ˜ O(1/T); however, the convergence rate is derived only for ||xout ||2c rather than ||xout-x∗||2c , where xout is the output of the algorithm and x∗ is the optimal solution of the SA problem. Compared to [Doan, 2020; Khodadadian et al., 2022] that restrict their focus on the centralized distributed learning framework, [Wai, 2020] considered Markovian SA in decentralized settings, and showed that the convergence rate of the proposed method is ˜ O(δ-1 /T 1/2 ). [Zeng et al., 2022] proposed a new decentralized SA algorithm DCSA that achieves an ˜ O(δ-2 /T) convergence rate. We see that the existing convergence rates of decentralized SA depend on the spectral gap δ of the communication network. Convergence rates of existing decentralized SA algorithms are worse than the near-optimal O(1/T) and ˜ O(1/T) convergence rates achieved by SA [Chen et al., 2020] and Markovian SA [Chen et al., 2021], respectively. Table 1: Convergence rates of different stochastic approximation algorithms for nonlinear stochastic approximation problems. Possible distributed architectures include 1) Single, the single-agent case, 2) Cen., a central server coordinating multiple agents; and 3) Dec., each agent directly communicating with its neighbors, without the need for a central server. δ is the spectral gap of the communication network (0 < δ ≤ 1). K is the communication interval (K ≥ 1). T is the total number of iterations (T ≥ 1). | Algorithm | Architecture | Local Updates | Markovian Noise | Compressed Communication | Rate | |-------------------------------------------------------------------------------------------------------------------------------------------------------------------------|-----------------------------------|-----------------|-------------------|----------------------------|---------------------------------------------------------------------| | SA [Chen et al., 2020] Markovian SA [Chen et al., 2021] Local SA [Doan, 2020] Federated SA [Khodadadian et al., 2022] Markovian SA [Wai, 2020] DCSA [Zeng et al., 2022] | Single Single Cen. Cen. Dec. Dec. | � � � � � � | � � � � � � | � � � � � � | O(1/T ) ˜ O(1/T ) ˜ O(K/T ) ˜ O(1/T ) ˜ O(δ-1 /T 1/2 ) ˜ O(δ-2 /T ) | | DLMSA (this paper) C-DLMSA (this paper) | Dec. Dec. | � � | � � | � � | ˜ O(1/T ) ˜ O(1/T ) | On the other hand, communication overhead is one of the main bottlenecks in distributed learning framework, which motivates the use of advanced algorithmic strategies to alleviate the communication overhead [Liu et al., 2022]. In particular, [Doan, 2020; Khodadadian et al., 2022] increase the number of local updates between the communication rounds to improve the computation-to-communication ratio. Another strategy is to leveraging compressed communication in which each agent sends the compressed information to its neighbors. These two strategies exhibit superior performance in scenarios where each agent has limited communication capabilities. But as far as we are aware, none of the existing work solves the Markovian SA problem by using multiple local updates or compressed communication in decentralized settings. Then, there exists a natural question: Can we design communication-efficient decentralized Markovian stochastic approximation algorithms with nearoptimal ˜ O(1/T) convergence guarantees? ## 1.1 Contributions In this paper, we give an affirmative answer to the above question by deriving convergence rates for DLMSA and CDLMSA under mild assumptions. The main contributions are briefly described as follows. ## Two New Algorithms We first propose a decentralized local Markovian stochastic approximation algorithm (DLMSA) algorithm. In DLMSA, each agent independently performs multiple local updates corrupted by Markovian noise and periodically communicates with its neighbors over a sparse communication network. DLMSA achieves temporal-spatial communication reduction by simultaneously allowing multiple local updates (i.e., reducing communication frequency) and allowing decentralized communication via a sparse network topology. To further reduce the communication overhead, we further propose DLMSA with compressed communication (C-DLMSA), which covers both unbiased and biased compression operators (e.g., quantization or sparsification). ## Convergence Guarantees We derive finite-time convergence rates of DLMSA involving a contraction mapping with respect to an arbitrary norm rather than the Euclidean norm. We show that despite Markovian noise, multiple local updates, and network connectivity affecting the higher-order terms, the dominated term ˜ O(T -1 )1 in the convergence rate is the same as the centralized baseline with exact communication under i.i.d. samples, differing only by logarithmic factors. Furthermore, we demonstrate that CDLMSA converges at a same rate to DLMSA, suggesting that C-DLMSA gains communication efficiency through compression, essentially for free. Our results and comparisons with existing work are summarized in Table ??. The C-DLMSA algorithm significantly outperforms existing work. Our algorithms converge at a near-optimal rate while allowing multiple local updates, Markovian noise, and arbitrary communication compression in decentralized settings. 1 The ˜ O(·) notation hides all log-terms and universal constants. ## Technical Challenges in Analysis Our analysis faces multiple challenges and requires several new insights. First, a key non-trivial technical ingredient is to identify error bounds for decentralized communication and Markovian noise-corrupted multiple local updates, and to make them compatible with proofs of the SA algorithm. For C-DLMSA, its analysis is more delicate and challenging because the compression operator may be biased. Second, our analysis is derived in the case where the norm of the contraction mapping of SA is arbitrary (e.g., ℓ∞-norm) instead of just being the Euclidean norm || · ||2. To this end, we introduce a potential function obtained by smoothing the norm-squared function with a generalized Moreau envelope. Third, the contraction mapping of SA or the noise is bounded by a constant in prior literature; instead, we only assume that the contraction mapping is bounded at the 0-point (see Assumption 1), and the second-order moment of the noise scales affinely with the current iterate (see Assumption 3). ## Application to Multi-Task Reinforcement Learning We apply our theoretical results to multi-task reinforcement learning over multi-agent systems. In particular, we present for the first time decentralized federated variants of the Qlearning algorithm and establish its finite-time convergence rates. Performing multiple local updates on agents before exchanging information via sparse communication network is adopted in our algorithms to improve communication efficiency. We prove that when the solution accuracy ϵ is small enough, the sample complexity and communication complexity of our algorithms are ˜ O(1/ϵ) and ˜ O(1/√ϵ), respectively. Experiments on standard multi-task reinforcement learning tasks are provided to illustrate our theoretical results. ## 1.2 RelatedWork ## Stochastic Approximation with Markovian Noise Markovian SA relates closely to Markov gradient descent [Benveniste et al., 2012; Doan, 2022] in optimization literature; however, Markovian SA is a more general framework that covers many problems in reinforcement learning that cannot be formulated as optimization problems, e.g., Q-learning [Watkins and Dayan, 1992]. Existing works on Markovian SA mainly focus on the single-agent case. The asymptotic convergence of Markovian SA was established by using the ordinary differential equation (ODE) method [Bertsekas and Tsitsiklis, 1996; Borkar, 2009; Borkar et al., 2021]. The finite-time convergence rates of Markovian SA were studied in [Chen et al., 2021; Chen et al., 2022]. They proved that Markovian SA achieves an ˜ O(1/T) convergence rate. [Doan, 2020; Khodadadian et al., 2022] proposed distributed local Markovian SA, and derived ˜ O(K/T) and ˜ O(1/T ) convergence rates, respectively. [Wai, 2020; Zeng et al., 2022] considered distributed Markovian SA in decentralized settings, but the convergence rates of the proposed methods are dependent on the communication network topology. In sharp contrast, our methods achieve a network topology-independent convergence rate, when the total number of iterations is sufficiently large. ## Federated Learning with I.I.D. Noise Federated learning is a distributed learning paradigm that utilizes local computation of agents to train models without sacrificing data privacy; see the recent survey paper [Li et al., 2020b]. In federated learning, the core algorithm FedAvg, also known as "local SGD", is featured by performing more local updates at each local agent and periodical communication via the central server [McMahan et al., 2017]. The convergence analysis of FedAvg is discussed by [Khaled et al., 2019; Li et al., 2019]. The authors in [Sun et al., 2022] studied the decentralized FedAvg, which is implemented on agents that are connected by an undirected communication network. When agents do not trust a central server to protect their privacy, decentralized federated learning is the learning paradigm of choice [Yang et al., 2019]. Except for [Doan, 2020; Khodadadian et al., 2022] mentioned above, we note that existing federated learning work mainly focuses on the case of sampling data from independent and identically distributed unknown distributions. ## Distributed and Multi-Agent RL Distributed Markovian SA theory has important applications in distributed and multi-agent RL. For example, the nonasymptotic analysis of distributed Q-learning can be seen as a Markovian SA problem [Xu and Gu, 2020]. Recently, there is a large literature on distributed and multi-agent RL. In particular, [Heredia et al., 2020] provided a finite-time analysis of distributed Q-learning in multi-agent systems. [Li et al., 2020a] derived non-asymptotic sample complexity bounds of asynchronous Q-learning. [Wang et al., 2020] provided a non-asymptotic analysis of decentralized TD methods with gradient tracking and linear function approximation. [Zhang et al., 2021] focused on decentralized multi-agent RL policy evaluation with nonlinear function approximation. [Sayin et al., 2021] presented a provably convergent decentralized multi-agent RL learning dynamics for zero-sum discounted Markov games over an infinite horizon. [Chen et al., 2018] proposed a policy gradient method termed lazily aggregated policy gradient to improve communication efficiency via infrequent communication. To our knowledge, all these works do not consider both Markovian noise-corrupted multiple local updates and compressed decentralized communication. In this paper, the proposed C-DLMSA subsumes compressed decentralized federated Q-learning as a special case. ## 2 Preliminaries ## 2.1 Single-Agent Case The SA algorithm is an iterative procedure for finding fixed points of a function when only noisy estimates of the function are observed. Specifically, with contraction mapping H : Rd × Y → Rd and ξ ∈ Y being random variable with distribution µ, Markovian SA seeks to solve the equation by the following update where ξk is a random variable derived from the evolution of a Markov chain, ωk is additive noise, α is step size, and T denotes the number of iterations. Indeed, Q-learning can be viewed as a variant of Markovian SA [Tsitsiklis, 1994]. In [Chen et al., 2020], the authors showed that with an appropriate constant step size α, Markovian SA has the following convergent behavior where C0, C1 and C2 are some problem dependent positive constants and x∗ is a solution of Eq.(2). In Eq.(4), we can reduce the finite-time convergence rate by reducing the step size α. We see that the finite-time convergence rate is dominated by the second termC2α, if α is small enough. ## 2.2 Some Mild Assumptions Throughout this work, denote || · ||c as an arbitrary norm in Rd . We analyze our algorithms under the following assumptions. Assumption 1. There exist ρ ∈ (0, 1) and two positive constants A1 and B1 such that for any agent i ∈ {1, 2, · · · , n}, (1) ||Hi(x1) - Hi(x2)||c ≤ ρ||x1 - x2||c, ∀x1, x2 ∈ Rd ; (2) ||Hi(x1, ξi) -Hi(x2, ξi)||c ≤ A1||x1 -x2||c, ∀x1, x2 ∈ Rd , ξi ∈ Y; (3) ||Hi(0, ξi)||c ≤ B1, ∀ξi ∈ Y. The first property above implies that Hi(x) is a contraction mapping with respect to an arbitrary norm || · ||c. By applying Banach fixed-point theorem [Debnath and Mikusinski, 2005], the first property guarantees that Eq.(1) has a unique solution, which we have denoted by x∗. The second property implies that Hi(x, ξi) is smooth with respect to the input argument x. The last property is weaker than the general boundedness assumption considered in the existing literature; e.g., [Khodadadian et al., 2022; Gao et al., 2022]. ``` Assumption 2. The weighted connectivity matrix M = [Mij] ∈ Rn×n satisfies the following: (1) Doubly Stochastic: ∑ni=1 Mij = ∑nj=1 Mij = 1; (2) Symmetric: Mij =Mji, ∀i, j ∈ {1, 2, · · · , n}; (3) Network Sparsity: Mij > 0 if (i, j) ∈ E; otherwise Mij = 0, ∀i, j ∈ {1, 2, · · · , n}. ``` Assumption 2 is fairly standard in the analysis of decentralized optimization; see e.g., [Xin et al., 2020]. In Assumption 2, M = [Mij] ∈ Rn×n denotes the weighted connectivity matrix of G. The ordered eigenvalues of M are denoted by 1 = |λ1(M)| > |λ2(M)| ≥ · · · ≥ |λn(M)|. We term δ = 1 - |λ2(M)| as the spectral gap of M. For such a symmetric and doubly stochastic, δ ∈ (0, 1] characterizes the connectivity of the network [Nedi´c et al., 2018]. ## 3 Decentralized Local Markovian Stochastic Approximation In the section, we propose decentralized local Markovian stochastic approximation (DLMSA) algorithm and its compressed variant (C-DLMSA) to solve Eq.(1). Figure 1: Schematic representation of DLMSA where agents perform K local updates and reach consensus through information exchange over a sparse communication network. ![Image](https://ijcai.org/proceedings/2024/fulltext/562/image_000000_abf40256b749a4423f498dc1ef0a9c321491d50b3436db7d8d26e5523cf18f17.png) ## Algorithm 1 DLMSA ``` 1: Initialization: α > 0, K ∈ Z+, x0,i = x0 for all agent i ∈ {1, 2, · · · , n} 2: for k = 0, 1, · · · , T -1 do 3: for agent i ∈ {1, 2, · · · , n} do 4: xk+1,i = xk,i + α (Hi(xk,i, ξk,i) - xk,i + ωk,i ) 5: if mod (k +1,K) = 0 then 6: xk+1,i = ∑j∈Ni Mijxk+1,j 7: end if 8: end for 9: end for ``` ## 3.1 DLMSA The key idea of our proposed DLMSA is to perform multiple iterative updates locally on each agent, followed by decentralized communication over a sparse network topology (see Figure 1). The details of DLMSA are shown in Algorithm 1. Specifically, at each iteration k each agent i maintains a local optimization variable xk,i and updates this variable as xk+1,i = xk,i +α (Hi(xk,i, ξk,i) - xk,i + ωk,i ), where ξk,i is a variable which is Markovian along the time k, ωk,i is additive noise, and α is step size. To ensure convergence, at every K iterations, the exchange of information (through a consensus operation) occurs between connected agents (neighbors). Denote Ni = {j ∈ V|(i, j) ∈ E} ∪ {i}. If mod (k + 1,K) = 0, then xk+1,i = ∑j∈Ni Mijxk+1,j. In a practical implementation, each agent only sends its local optimization variable xk+1,i to its neighbors Ni. Here, the communication period K is greater than 1, so that the number of communication rounds is reduced to T/K. ## 3.2 C-DLMSA To further reduce the communication overhead, we propose CDLMSA (see Algorithm 2). The main pillar in C-DLMSA is an error-compensated mechanism for mitigating compression errors. Specifically, at each iteration k each agent i maintains local variables (xk,i, {̂xk,j}j∈Ni , yk,i), and updates the variable y as yk+1,i = xk,i + α (Hi(xk,i, ξk,i) - xk,i + ωk,i ). ## Algorithm 2 C-DLMSA ``` 1: Initialization: α > 0, η > 0, K ∈ Z+, x0,i = x0, ̂x0,i = 0 for all agent i ∈ {1, 2, · · · , n} 2: for k = 0, 1, · · · , T -1 do 3: for agent i ∈ {1, 2, · · · , n} do 4: yk+1,i = xk,i + α (Hi(xk,i, ξk,i) - xk,i + ωk,i ) 5: if mod (k +1,K) = 0 then 6: qk,i = Q[yk+1,i - ̂xk,i] 7: ̂xk+1,i = ̂xk,i + qk,i 8: xk+1,i = yk+1,i + η ∑j∈Ni Mij(̂xk+1,j - ̂xk+1,i) 9: else 10: ̂xk+1,i = ̂xk,i 11: xk+1,i = yk+1,i 12: end if 13: end for 14: end for ``` If mod (k + 1,K) = 0, each agent i sends qk,i = Q[yk+1,i - ̂xk,i] to its neighbors, where Q is the compressed operator. Upon receiving qk,j from its neighbors, the agent i updates ̂xk+1,j = ̂xk,j + qk,j and xk+1,i = yk+1,i + η ∑j∈Ni Mij (̂xk+1,j - ̂xk+1,i). If mod (k + 1,K) ̸= 0, then ̂xk+1,i = ̂xk,i, xk+1,i = yk+1,i, and no information exchange occurs. ## 4 Main Results Define Fk as the Sigma-algebra generated by {(xk′ ,i, ξk′ ,i,ωk′ ,i)}0≤k′≤k-1, i∈{1,2,··· ,n} ∪ {xk,i}. We make the following assumption on the noises {ωk,i}. Assumption 3. For any agent i ∈ {1, 2, · · · , n}, the random process {ωk,i} satisfies the following: (1) E [ωk,i|Fk] = 0 for all k ≥ 0; (2) ||ωk,i||c ≤ A2||xk,i||c +B2 for all k ≥ 0, where A2 and B2 are positive constants. Here, we do not assume that ωk,i are independent among agents i ∈ {1, 2, · · · , n}, which is often assumed when studying the finite-time convergence rates of distributed SA; see for example [Khodadadian et al., 2022]. In this work, we consider the case where the random variable {ξk,i} for each agent i is generated by a Markov process. This Markovian sampling results in correlated and biased data [Kumar et al., 2023]. To this end, we impose the following assumption on the Markov chain {ξk,i}. Assumption 4. For any agent i ∈ {1, 2, · · · , n}, the Markov chain {ξk,i} has a unique stationary distribution µi ∈ ∆|Y| , and there exist constants ζ > 0 and σ ∈ (0, 1) such that maxξi∈Y ||P k (ξi, ·) - µi(·)||TV ≤ ζσk for all k ≥ 0, where ∆|Y| is the probability simplex on R|Y| , and || · ||TV stands for the total variation distance [Levin and Peres, 2017]. We denote by τα = min{k ≥ 0 : maxξi∈Y ||P k (ξi, ·) - µi(·)||TV ≤ α, ∀i ∈ {1, 2, · · · , n}}. The mixing time τα represents the time it takes for the distribution {ξk,i} to get close to the stationary distribution µi. Assumption 4 implies that τα ≤ (log(1/α) + log(ζ/σ)) / log(1/σ), and it follows that limα→0 ατ 2α = 0. When the Markov chain {ξk,i} is irreducible and aperiodic, Assumption 4 holds [Levin and Peres, 2017]. ## 4.1 Finite-Time Convergence Rate of DLMSA We provide a finite-time convergence rate for Algorithm 1 in the following theorem. Theorem 1. Consider the updates of Algorithm 1. Suppose that Assumptions 1, 2, 3, and 4 are satisfied, and α ≤ min { 1 4Aτα , δ4 1 √AK , ϕ8 1 𭟋A2 κντ 2α , 1 32 √ ϕδ2 𭟋A2 κK2 (τα+1)ν } for some positive constants 𭟋, A, κ, ϕ, and ν, which are specified precisely in Appendix A, and are independent of α, δ, τα, n, T , and K. For any T > 2τα, we have Remark 1 (Finite-time convergence analysis): Theorem 1 provides the first finite-time analysis of decentralized federated stochastic approximation under Markovian sampling. Specifically, with respect to an arbitrary norm || · ||c, Theorem 1 establishes the convergence of xout to a ball around the optimal solution x∗ with a radius on the order of α log2 ( 1α ). The first term in Eq.(5) converges geometrically to zero as T grows, and the convergence rate in Eq.(5) is dominated by the second term, being proportional to α log2 ( 1α ) for small enough α. In Theorem 1, the network topology and multiple local updates mildly affect the convergence rate, with δ and K only affecting the highest-order term of α in Eq.(5). Selecting the step size α = O(logT/T) for sufficiently large T, we see that xout converges exactly to the optimal solution with convergence rate ˜ O(1/T). When Hi(x, ξi) is the gradient of some function, we recover the convergence rate of the decentralized federated averaging algorithm in [Sun et al., 2022] for solving strongly convex objective functions under i.i.d. samples, up to logarithmic factors. Remark 2 (Convergence dependence on δ and K): The highest-order term of α in Eq.(5) depends quadratically on the inverse of the spectral gap δ, which shows the impact of the communication network on the convergence of the algorithm. We see that a smaller δ implies that the communication network is sparse and the convergence rate slows down. The highest-order term of α in Eq.(5) depends quadratically on the communication interval K. We see that a larger K indicates less communication between agents, so the highest-order term of α in Eq.(5) becomes larger. Remark 3 (Comparison with the rate of decentralized stochastic approximation): In Theorem 1, the network topology δ only affects the highest-order term of α in Eq.(5). However, the dominated order of bounds in [Zeng et al., 2022] is affected by the network topology. Furthermore, the order of convergence rate in Theorem 1 is independent of the number of agents, i.e., n, which is in contrast to the convergence rate in [Zeng et al., 2022] that gets worse as n increases. Remark 4 (Comparison with the rate of federated stochastic approximation): In Theorem1, we prove that the output xout of DLMSA using a decreasing step size converges to the optimal solution x∗ of the SA problem; however, [Khodadadian et al., 2022] only proves that ||xout ||2c converges to 0. Furthermore, the consensus errors induced by the decentralized network structure in this paper make the analysis more challenging compared to the centralized SA algorithm proposed in [Khodadadian et al., 2022]. ## 4.2 Finite-Time Convergence Rate of C-DLMSA To analyze the convergence rate of C-DLMSA, we impose the following assumption on the compressed operator Q. Assumption 5. The compressed operator Q : Rd → Rd satisfies EQ[||Q[x] - x||2c ] ≤ (1 - ω)||x||2c for a parameter 0 < ω ≤ 1 and ∀x ∈ Rd . Here EQ[·] denotes the expectation on the internal randomness of the compressed operator Q. We provide a finite-time convergence rate for Algorithm 2 in the following theorem. Theorem 2. Consider the updates of Algorithm 2. Suppose that Assumptions 1, 2, 3, 4, and 5 are satisfied, η = δω3 64β2+12β2ω2+2δ2ω2 with β = maxi{1 - λi(M)}, and α ≤ min { 1 4Aτα , δ4 1 √AK , ϕ8 1 𭟋A2 κντ 2α , 18 √ ηδ AK2 C(η,δ,β,ω) , 1 64 √ ϕηδ 𭟋A2 κK2 (τα+1)νC(η,δ,β,ω) } for some positive constants 𭟋, A, κ, ϕ, and ν, which are specified precisely in Appendix B, and are independent of α, δ, τα, n, T, and K, where C(η, δ, β, ω) is a constant defined in Appendix B, being dependent on η, δ, β, and ω. For any T > 2τα, we have where xout = 1 WT ∑Tk=2τα wk n ∑ni=1 xk,i for weights wk = (1 - 14 ϕα)-k , WT = ∑Tk=2τα wk, and 0 < ϕ < 1. Remark 5 (Finite-time convergence analysis): Theorem 2 provides a finite-time analysis of C-DLMSA under Markovian sampling. Similarly, the first term in Eq.(6) converges geometrically to zero as T grows, and the convergence rate in Eq.(6) is dominated by the second term, being proportional to α log2 ( 1α ) for small enough α. The network topology, multiple local updates, and compressed communication mildly affect the convergence rate, with δ, K, and ω only affecting the highest-order term of α in Eq.(6). Remark 6 (Convergence dependence on ω): The highestorder term of α in Eq.(6) depends on the inverse of the compression parameter ω, which shows the impact of compressed communication on the convergence of the algorithm. We see that a smaller ω close to 0 means that the compressing communication loses more information, so the highest-order term of α in Eq.(6) becomes larger. ## 5 Application toMulti-Task Reinforcement Learning In decentralized federated Q-learning, agents collaboratively estimate the optimal Q-function. Specifically, for each k ≥ 0, each agent i maintains a local Q-function estimate Qk,i(s, a). Here, we also consider an MDP consisting of a finite set of states S and a finite set of actions A. Given trajectories {(Sk,i, Ak,i, Rk,i, Sk+1,i)} collected using a suitable behavior policy πb, the iterate Qk,i(s, a) is updated as where we denote by Γ[Qk,i, Sk,i, Ak,i, Rk,i, Sk+1,i] = Rk,i + γmaxa′ Qk,i(Sk+1,i, a′ ) - Qk,i(Sk,i,Ak,i). If mod (k + 1, K) = 0, then Qk+1,i = ∑j∈Ni Mi,jQk+1,j . Similarly, we can use the communication compression in Algorithm 2 to get compressed decentralized federated Q-learning. Specifically, the update (7) in decentralized federated Q-learning can be rewritten as which is in the same form of C-DLMSA by defining ξk,i = (Sk,i, Ak,i, Rk,i, Sk+1,i), ωk,i = 0, and the nonlinear operator Hi(Qk,i, ξk,i) : R|S||A| × Y → R|S||A| : The properties of the operator Hi(Qk,i, ξk,i) and the Markov chain {ξk,i} are established in the following proposition, which guarantee that Assumptions 1, 3, and 4 are satisfied. Proposition 1. Assume the behavior policy πb satisfies πb(a|s) > 0 for all (s, a), and the Markov chains {Sk,i} induced by πb are irreducible and aperiodic, then Assumptions 1, 3, and 4 are satisfied with respect to the || · ||∞ norm. Corollary 1. Consider Qout generated by (compressed) decentralized federated Q-learning. Assume πb satisfies the conditions in Proposition 1. In order to make ||Qout -Q∗||2∞ ≤ ϵ, where ϵ > 0 is a given accuracy and Q∗ is the Q-function associated with an optimal policy, the sample and communication complexities are ˜ O(1/ϵ) and ˜ O(1/√ϵ), respectively. ## 5.1 Experiments In this section, we aim to support our theoretical results by applying (compressed) decentralized federated Q-learning to solve the multi-task GridWorld problem [Zeng et al., 2021a]. We consider the GridWorld problem with n individual environments of size 10 × 10 over n different agents. We assign each agent to an environment where the agent is placed in a grid of cells, each cell having one of three labels {goal, obstacle, empty}. The agent chooses one action of 4 actions {up, down, left, right} to move to the next cell. The reward is -0.1× (distance between agent and goal) ±10, depending on whether the goal is reached or the agent is trapped in an obstacle. By training agents in different environments to obtain a unified policy, it is expected to have better generalization ability. We connect the agents in a ring graph and use centralized Q-learning (Cen. Q-learning), decentralized federated Q-learning (DFed. Q-learning), and compressed decentralized federated Q-learning (Comp. DFed. Q-learning) to train them for 1000 episodes. In centralized Q-learning, consensus operations with exact information are performed at each iteration. We use the same best-tuned learning rate α = 0.5, communication interval K = 10, and discounter factor γ = 0.99 in all experiments. For Comp. DFed. Q-learning, we use top1% [Stich, 2018] as the compression operator. Experimental results are the average over 10 random seeds. Figure 2: 4Agents@2Obstacles: Left: evaluation of learned policy. Right: average return for different algorithms. The Dark green cell represents the starting position of the agents. Red cells represent obstacles. Yellow cells represent goals and white numbers represent the indices of agents. ![Image](https://ijcai.org/proceedings/2024/fulltext/562/image_000001_da7a7b19fa92ede2ef7185a52c9da142144f3de0b15fcae776db549e7abf6526.png) Figure 3: 5Agents@5Obstacles: Left: evaluation of learned policy. Right: average return for different algorithms. ![Image](https://ijcai.org/proceedings/2024/fulltext/562/image_000002_f0177a86b8ca89158a58305b4f7124fe2799dfe28acea8b2ea1004ac2f9093e0.png) Figure 2 considers experiments with 4 agents, while Figures 3 and 4 consider experiments with 5 and 6 agents, respectively. After 1000 episodes of training with DFed. Q-learning, we observe that agents agree on a policy whose performance is tested across all environments. We combine all the results into one grid, as shown on the left side of Figures 2-4. The light green path is the route that the agents visit in these environments. We see that a unified policy finds all targets in all environments. This verifies the effectiveness of DFed. Q-learning. On the right side of Figures 2-4, we compare Fed. Q-learning and Comp. DFed. Q-learning with Cen. Q-learning. We show the results for the average return versus the number of iterations. Figure 4: 6Agents@5Obstacles: Left: evaluation of learned policy. Right: average return for different algorithms. The number i in red cell represents the obstacle of the i-th agent. ![Image](https://ijcai.org/proceedings/2024/fulltext/562/image_000003_4c09d2d469c4cc8537f519cf0f5366faf048c99b133dbfbe832dbf06c839ddd2.png) Figure 5: Left: different choices of the network topology. Right: different choices of the communication interval. ![Image](https://ijcai.org/proceedings/2024/fulltext/562/image_000004_b02944b49b83870f986781a9e0f4ca1431fbec94ff5538f656861a05d82027b5.png) We see that despite consensus errors, local update errors, and compression errors, the Comp. DFed. Q-learning achieves comparable performance to Cen. Q-learning. Figure 5 shows different choices of network topology δ and communication interval K. The results show that the effect of network topology on the convergence rate of DFed. Q-learning is limited, and we observe similar results for DFed. Q-learning when the communication interval K increases from 1, 10 to 20. ## 6 Conclusion In this paper, we proposed decentralized local Markovian stochastic approximation DLMSA algorithm and its compressed variant C-DLMSA. The C-DLMSA algorithm can achieve temporal-spatial communication reduction by allowing multiple local updates, decentralized communication through sparse network topology, and arbitrary communication compression. We established finite-time convergence rates for DLMSA and C-DLMSA, and showed that the algorithms converge at a near-optimal rate ˜ O(1/T). Finally, we applied our algorithms to multi-task reinforcement learning. Future directions of this work include studying DLMSA and C-DLMSA under asynchronous communication as well as time-varying and/or directed communication graphs. ## Acknowledgments This work is supported by the National Natural Science Foundation of China (T2293723), Zhejiang Provincial Natural Science Foundation (Z24F020008), the Key R&D Program of Zhejiang Province (2022C01022, 2022C01119, 2021C03003), and the Fundamental Research Funds for the Central Universities (No. 226-2022-00051). ## References 1. [Alacaoglu and Lyu, 2023] Ahmet Alacaoglu and Hanbaek Lyu. Convergence of first-order methods for constrained nonconvex optimization with dependent data. In Inter- national Conference on Machine Learning, volume 202, pages 458-489. PMLR, 2023. 2. [Benveniste et al., 2012] Albert Benveniste, Michel Métivier, and Pierre Priouret. Adaptive algorithms and stochastic approximations, volume 22. Springer Science & Business Media, 2012. 3. [Bertsekas and Tsitsiklis, 1996] Dimitri Bertsekas and John N Tsitsiklis. Neuro-dynamic programming. Athena Scientific, 1996. 4. [Bhandari et al., 2018] Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal dif- ference learning with linear function approximation. In Conference on learning theory, pages 1691-1692. PMLR, 2018. 5. [Borkar et al., 2021] Vivek Borkar, Shuhang Chen, Adithya Devraj, Ioannis Kontoyiannis, and Sean Meyn. The ode method for asymptotic statistics in stochastic ap- proximation and reinforcement learning. arXiv preprint arXiv:2110.14427, 2021. 6. [Borkar, 2009] Vivek S Borkar. Stochastic approximation: a dynamical systems viewpoint, volume 48. Springer, 2009. 7. [Bottou et al., 2018] Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, 60(2):223-311, 2018. 8. [Chen et al., 2018] Tianyi Chen, Kaiqing Zhang, Geor- gios B Giannakis, and Tamer Basar. Communication- efficient distributed reinforcement learning. arXiv preprint arXiv:1812.03239, 16, 2018. 9. [Chen et al., 2020] Zaiwei Chen, Siva Theja Maguluri, San- jay Shakkottai, and Karthikeyan Shanmugam. Finite- sample analysis of contractive stochastic approximation using smooth convex envelopes. Advances in Neural Infor- mation Processing Systems, 33:8223-8234, 2020. 10. [Chen et al., 2021] Zaiwei Chen, Siva Theja Maguluri, San- jay Shakkottai, and Karthikeyan Shanmugam. A lya- punov theory for finite-sample guarantees of asynchronous q-learning and td-learning variants. arXiv preprint arXiv:2102.01567, 2021. 11. [Chen et al., 2022] Zaiwei Chen, Sheng Zhang, Thinh T Doan, John-Paul Clarke, and Siva Theja Maguluri. Finite- sample analysis of nonlinear stochastic approximation with applications in reinforcement learning. Automatica, 146:110623, 2022. 12. [Dean et al., 2012] Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Marc'aurelio Ran- zato, Andrew Senior, Paul Tucker, Ke Yang, et al. Large scale distributed deep networks. Advances in neural infor- mation processing systems, 25, 2012. 13. [Debnath and Mikusinski, 2005] Lokenath Debnath and Piotr Mikusinski. Introduction to Hilbert spaces with applica- tions. Academic press, 2005. 14. [Doan, 2020] Thinh T Doan. Local stochastic approximation: A unified view of federated learning and distributed multi- task reinforcement learning algorithms. arXiv preprint arXiv:2006.13460, 2020. 15. [Doan, 2022] Thinh T Doan. Finite-time analysis of markov gradient descent. IEEE Transactions on Automatic Control, 68(4):2140-2153, 2022. 16. [Dorfman and Levy, 2022] Ron Dorfman and Kfir Yehuda Levy. Adapting to mixing time in stochastic optimiza- tion with markovian data. In International Conference on Machine Learning, pages 5429-5446. PMLR, 2022. 17. [Duchi et al., 2012] John C Duchi, Alekh Agarwal, Mikael Johansson, and Michael I Jordan. Ergodic mirror descent. SIAM Journal on Optimization, 22(4):1549-1578, 2012. 18. [Gao et al., 2022] Hongchang Gao, Junyi Li, and Heng Huang. On the convergence of local stochastic compo- sitional gradient descent with momentum. In Interna- tional Conference on Machine Learning, pages 7017-7035. 19. PMLR, 2022. 20. [Heredia et al., 2020] Paulo Heredia, Hasan Ghadialy, and Shaoshuai Mou. Finite-sample analysis of distributed q- learning for multi-agent networks. In 2020 American Con- trol Conference, pages 3511-3516. IEEE, 2020. 21. [Jiang and Xu, 2008] Houyuan Jiang and Huifu Xu. Stochas- tic approximation approaches to the stochastic variational inequality problem. IEEE Transactions on Automatic Con- trol, 53(6):1462-1475, 2008. 22. [Khaled et al., 2019] Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. First analysis of local gd on heterogeneous data. arXiv preprint arXiv:1909.04715, 2019. 23. [Khodadadian et al., 2022] Sajad Khodadadian, Pranay Sharma, Gauri Joshi, and Siva Theja Maguluri. Federated reinforcement learning: Linear speedup under markovian sampling. In International Conference on Machine Learning, pages 10997-11057. PMLR, 2022. 24. [Kumar et al., 2023] Harshat Kumar, Alec Koppel, and Ale- jandro Ribeiro. On the sample complexity of actor-critic method for reinforcement learning with function approxi- mation. Machine Learning, pages 1-35, 2023. 25. [Kushner and Yin, 1987] Harold Joseph Kushner and George Yin. Stochastic approximation algorithms for parallel and distributed processing. Stochastics: An International Jour- nal of Probability and Stochastic Processes, 22(3-4):219- 250, 1987. 26. [Lakshmanan and De Farias, 2008] Hariharan Lakshmanan and Daniela Pucci De Farias. Decentralized resource allo- cation in dynamic networks of agents. SIAM Journal on Optimization, 19(2):911-940, 2008. 27. [Levin and Peres, 2017] David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017. 28. [Li et al., 2019] Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. In International Conference on Learning Representations, 2019. 29. [Li et al., 2020a] Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Sample complexity of asynchronous q-learning: Sharper analysis and variance reduction. Ad- vances in neural information processing systems, 33:7031- 7043, 2020. 30. [Li et al., 2020b] Tian Li, Anit Kumar Sahu, Ameet Tal- walkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE signal processing magazine, 37(3):50-60, 2020. 31. [Liu et al., 2022] Wei Liu, Li Chen, and Wenyi Zhang. De- centralized federated learning: Balancing communication and computing costs. IEEE Transactions on Signal and Information Processing over Networks, 8:131-143, 2022. 32. [McMahan et al., 2017] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273-1282. PMLR, 2017. 33. [Mnih et al., 2016] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asyn- chronous methods for deep reinforcement learning. In International conference on machine learning, pages 1928- 1937. PMLR, 2016. 34. [Nedić et al., 2018] Angelia Nedić, Alex Olshevsky, and Michael G Rabbat. Network topology and communication- computation tradeoffs in decentralized optimization. Pro- ceedings of the IEEE, 106(5):953-976, 2018. 35. [Robbins and Monro, 1951] Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400-407, 1951. 36. [Sayin et al., 2021] Muhammed Sayin, Kaiqing Zhang, David Leslie, Tamer Basar, and Asuman Ozdaglar. Decen- tralized q-learning in zero-sum markov games. Advances in Neural Information Processing Systems, 34:18320-18334, 2021. 37. [Srikant and Ying, 2019] Rayadurgam Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation and td learning. In Conference on Learning Theory, pages 2803-2830. PMLR, 2019. 38. [Stich, 2018] Sebastian U Stich. Local sgd converges fast and communicates little. In International Conference on Learning Representations, 2018. 39. [Sun et al., 2020] Jun Sun, Gang Wang, Georgios B Gian- nakis, Qinmin Yang, and Zaiyue Yang. Finite-time analysis of decentralized temporal-difference learning with linear function approximation. In International Conference on Ar- tificial Intelligence and Statistics, pages 4485-4495. PMLR, 2020. 40. [Sun et al., 2022] Tao Sun, Dongsheng Li, and Bao Wang. Decentralized federated averaging. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022. 41. [Sutton and Barto, 2018] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018. 42. [Tsitsiklis, 1994] John N Tsitsiklis. Asynchronous stochastic approximation and q-learning. Machine learning, 16:185- 202, 1994. 43. [Wai, 2020] Hoi-To Wai. On the convergence of consensus algorithms with markovian noise and gradient bias. In 2020 59th IEEE Conference on Decision and Control, pages 4897-4902. IEEE, 2020. 44. [Wang et al., 2020] Gang Wang, Songtao Lu, Georgios Gi- annakis, Gerald Tesauro, and Jian Sun. Decentralized td tracking with linear function approximation and its finite- time analysis. Advances in Neural Information Processing Systems, 33:13762-13772, 2020. 45. [Watkins and Dayan, 1992] Christopher JCH Watkins and Pe- ter Dayan. Q-learning. Machine learning, 8:279-292, 1992. 46. [Xin et al., 2020] Ran Xin, Soummya Kar, and Usman A Khan. Decentralized stochastic optimization and machine learning: A unified variance-reduction framework for ro- bust performance and fast convergence. IEEE Signal Pro- cessing Magazine, 37(3):102-113, 2020. 47. [Xu and Gu, 2020] Pan Xu and Quanquan Gu. A finite-time analysis of q-learning with neural network function approx- imation. In International Conference on Machine Learning, pages 10555-10565. PMLR, 2020. 48. [Yang et al., 2019] Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology (TIST), 10(2):1-19, 2019. 49. [Zeng et al., 2021a] Sihan Zeng, Malik Aqeel Anwar, Thinh T Doan, Arijit Raychowdhury, and Justin Romberg. A decentralized policy gradient approach to multi-task rein- forcement learning. In Uncertainty in Artificial Intelligence, pages 1002-1012. PMLR, 2021. 50. [Zeng et al., 2021b] Sihan Zeng, Thinh T Doan, and Justin Romberg. Finite-time analysis of decentralized stochastic approximation with applications in multi-agent and multi- task learning. In 2021 60th IEEE Conference on Decision and Control (CDC), pages 2641-2646. IEEE, 2021. 51. [Zeng et al., 2022] Sihan Zeng, Thinh T Doan, and Justin Romberg. Finite-time convergence rates of decentralized stochastic approximation with applications in multi-agent and multi-task learning. IEEE Transactions on Automatic Control, 2022. 52. [Zhang et al., 2021] Xin Zhang, Zhuqing Liu, Jia Liu, Zhengyuan Zhu, and Songtao Lu. Taming communica- tion and sample complexities in decentralized policy eval- uation for cooperative multi-agent reinforcement learn- ing. Advances in Neural Information Processing Systems, 34:18825-18838, 2021.