Finite-Time Convergence Rates of Decentralized Local Markovian Stochastic Approximation

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.

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).

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 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.

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).