summaries: This paper establishes the first finite-time convergence result of the actor-critic algorithm for fully decentralized multi-agent reinforcement learning (MARL) problems with average reward. It focuses on the practical setting where the rewards and actions of each agent are only known to itself, and the knowledge of joint actions of the agents is not assumed. The established finite-sample complexity matches that of the state-of-the-art single-agent actor-critic algorithms. This paper considers cooperative multi-agent reinforcement learning (MARL) for average reward MDPs with fully decentralized actor-critic methods. In particular, the authors make some progress on top of existing works in this direction, and in particular (Zhang et al., 2018). More precisely, the authors remove the assumption in (Zhang et al., 2018) that the joint actions are observable to all agents, and propose to modify the actor updates with mini-batch TD sharing to accommodate the scenario where each agent only observes its own action. The authors then establish a finite-sample bound for the proposed algorithm in terms of convergence to stationary points under linear value function approximation. Numerical experiments are also provided to showcase the benefits of the modifications over the algorithm in (Zhang et al., 2018).  This paper studies the cooperative average reward fully decentralized multi-agent reinforcement learning (MARL) problems, where the agents interact with their neighbors over a communication network. It proposes a consensus-based actor-critic algorithm and shows its convergence to the stationary point. The convergence rate and sample complexity of this algorithm are provided and comparison with existing algorithm is shown in the numerical experiments.  This paper studies a networked MARL problem based on the model in [Zhang et al 2018], where each agent can observe the global state, take local action and observe local rewards. The key difference in setting from [Zhang et al 2018] is that [Zhang et al 2018] assume the global action can be observed, but in this paper, only local action is known to each agent. To deal with this, an additional consensus loop is added to estimate the average TD error, which can be used to estimate the advantage function. Further, compared to [Zhang et al 2018], a finite time error bound is provided.  
abstractText: In this paper, we establish the first finite-time convergence result of the actor-critic algorithm for fully decentralized multi-agent reinforcement learning (MARL) problems with average reward. In this problem, a set of N agents work cooperatively to maximize the global average reward through interacting with their neighbors over a communication network. We consider a practical MARL setting, where the rewards and actions of each agent are only known to itself, and the knowledge of joint actions of the agents is not assumed. Toward this end, we propose a mini-batch Markovian sampled fully decentralized actor-critic algorithm and analyze its finite-time convergence and sample complexity. We show that the sample complexity of this algorithm is O(N/ǫ log(N/ǫ)). Interestingly, this sample complexity bound matches that of the state-of-the-art single-agent actorcritic algorithms for reinforcement learning.
authors.name: AVERAGE REWARD
references.authors: Rajendra Bhatia
references.title: Matrix analysis, volume
references.venue: of. Graduate texts in mathematics,
references.authors: Tianyi Chen Georgios B Giannakis Tao Sun Wotao Yin
references.title: Lag: Lazily aggregated gradient for communication-efficient distributed learning
references.venue: arXiv preprint arXiv:1805.09965,
references.authors: Ziyi Chen Yi Zhou Rongrong Chen Shaofeng Zou
references.title: Sample and communication-efficient decentralized actor-critic algorithms with finite-time analysis
references.venue: arXiv preprint arXiv:2109.03699,
references.authors: Thinh Doan Siva Maguluri Justin Romberg
references.title: Finite-time analysis of distributed td (0) with linear function approximation on multi-agent reinforcement learning
references.venue: In International Conference on Machine Learning,
references.authors: Jakob Foerster Gregory Farquhar Triantafyllos Afouras Nantas Nardelli Shimon Whiteson
references.title: Counterfactual multi-agent policy gradients
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: Zuyue Fu Zhuoran Yang Zhaoran Wang
references.title: Single-timescale actor-critic provably finds globally optimal policy
references.venue: arXiv preprint arXiv:2008.00483,
references.authors: Xin Guo Anran Hu Junzi Zhang
references.title: Theoretical guarantees of fictitious discount algorithms for episodic reinforcement learning and global convergence of policy gradient methods
references.venue: arXiv preprint arXiv:2109.06362,
references.authors: Sham Machandranath Kakade
references.title: On the sample complexity of reinforcement learning
references.venue: University of London, University College London (United Kingdom),
references.authors: Donghwan Lee Niao He Parameswaran Kamalaruban Volkan Cevher
references.title: Optimization for reinforcement learning: From a single agent to cooperative agents
references.venue: IEEE Signal Processing Magazine,
references.authors: David A Levin Yuval Peres
references.title: Markov chains and mixing times, volume 107
references.authors: Angelia Nedic Asuman Ozdaglar
references.title: Distributed subgradient methods for multi-agent optimization
references.venue: IEEE Transactions on Automatic Control,
references.authors: Shuang Qiu Zhuoran Yang Jieping Ye Zhaoran Wang
references.title: On finite-time convergence of actorcritic algorithm
references.venue: IEEE Journal on Selected Areas in Information Theory,
references.authors: Martin Riedmiller Andrew Moore Jeff Schneider
references.title: Reinforcement learning for cooperating and communicating reactive agents in electrical power grids
references.venue: In Workshop on Balancing Reactivity and Social Deliberation in Multi-Agent Systems,
references.authors: Shai Shalev-Shwartz Shaked Shammah Amnon Shashua
references.title: Safe, multi-agent, reinforcement learning for autonomous driving
references.venue: arXiv preprint arXiv:1610.03295,
references.authors: David Silver Thomas Hubert Julian Schrittwieser Ioannis Antonoglou Matthew Lai Arthur Guez Marc Lanctot Laurent Sifre Dharshan Kumaran Thore Graepel
references.title: A general reinforcement learning algorithm that masters chess, shogi, and go through self-play
references.authors: John N Tsitsiklis Benjamin Van Roy
references.title: On average versus discounted reward temporal-difference learning
references.venue: Machine Learning,
references.authors: Yue Wu Weitong Zhang Pan Xu Quanquan Gu
references.title: A finite time analysis of two time-scale actor critic methods
references.venue: arXiv preprint arXiv:2005.01350,
references.authors: Tengyu Xu Zhe Wang Yingbin Liang
references.title: Improving sample complexity bounds for (natural) actor-critic algorithms
references.venue: arXiv preprint arXiv:2004.12956,
references.authors: Zhuoran Yang Yongxin Chen Mingyi Hong Zhaoran Wang
references.title: On the global conver
references.authors: Xin Zhang Zhuqing Liu Jia Liu Zhengyuan Zhu Songtao Lu
references.title: Taming communication and
references.venue: Conference on Computer Communications,
references.authors: Zhang
references.title: There are N agents, each has a binary-valued action space, i.e. A = {0, 1}, for all i ∈ N . In addition, in all the results shown here, we set |S| = 5 states. The elements in the transition matrix are uniformly sampled from the interval
references.authors: Xu
references.title: The proof follows from verifying the Assumption 3 of Xu et al. (2020), then we can apply the results from Theorem
sections.text: In this paper, we establish the first finite-time convergence result of the actor-critic algorithm for fully decentralized multi-agent reinforcement learning (MARL) problems with average reward. In this problem, a set of N agents work cooperatively to maximize the global average reward through interacting with their neighbors over a communication network. We consider a practical MARL setting, where the rewards and actions of each agent are only known to itself, and the knowledge of joint actions of the agents is not assumed. Toward this end, we propose a mini-batch Markovian sampled fully decentralized actor-critic algorithm and analyze its finite-time convergence and sample complexity. We show that the sample complexity of this algorithm is O(N2/ǫ2 log(N/ǫ)). Interestingly, this sample complexity bound matches that of the state-of-the-art single-agent actorcritic algorithms for reinforcement learning.
sections.heading: 1 INTRODUCTION
sections.text: 1) Background and Motivations: In recent years, multi-agent reinforcement learning (MARL) has found a wide range of applications in networked large-scale systems, such as power grid systems (Riedmiller et al., 2000), autonomous driving (Yu et al., 2019; Shalev-Shwartz et al., 2016) and strategic games (Silver et al., 2018; Foerster et al., 2018), to name just a few. Although empirical successes of MARL applications have been widely observed, the fundamental theoretical understanding of how to develop fast-converging and low sample-complexity MARL algorithms, two of the most important performance metrics for MARL, remains in its infancy so far (see, e.g., (Zhang et al., 2021a) for an excellent survey). In particular, two important aspects of cooperative MARL algorithm designs deserve special attention:
  • First, in the multi-agent collaborative setting, the information structure (i.e., the assumptions of who have the knowledge of what) is far more complex than its single-agent counterpart and care must be taken in MARL problem formulations. In the cooperative MARL literature so far, many existing works assume full knowledge of joint states and joint actions, which often do not hold true in practice. For example, in autonomous driving (Yu et al., 2019), each vehicle can only observe/detect the actions of the surrounding vehicles that are within its communication range. As another example, in power grid networks (Riedmiller et al., 2000), each power distributor generally does not know the resistor values set by other distributors.
  • Second, most MARL theoretical studies in the MARL literature are focused on the discounted total reward setting, where a hyperparameter γ ∈ (0, 1) is introduced as the discount factor in the objective function. Although the discounted total reward setting captures the important aspect of diminishing return in the future, it may not be appropriate for many other applications where the long-term average reward is of interest. For example, in the optimization of distributed communication networks with MARL, the typical and natural performance metrics are long-term average throughput or latency in the steady-state.
  The lack of a fundamental understanding on how to develop efficient cooperative MARL algorithms that consider the above two aspects in terms of information structure, scalability, and communication and sample complexities motivates us to fill this gap by developing a fully decentralized cooperative MARL algorithm in the average reward setting, without assuming joint action knowledge.
  2) Technical Challenges: Developing a fully decentralized cooperative MARL algorithm for the average reward setting without full joint action knowledge is highly non-trivial and several major technical challenges naturally arise. First, it is well-known that, even in the single-agent reinforcement learning (RL) setting, the average reward setting is more challenging to analyze compared to the discounted reward setting, which necessitates different proof techniques (Tsitsiklis & Van Roy, 1999). In MARL, the decentralized nature and the lack of joint action-state information further complicate the algorithm design and analysis in the average reward setting. Second, due to the lack of joint action knowledge, the communication costs among agents in MARL will be significantly increased to achieve a satisfying performance, which implies that low sample and communication complexities are even more challenging and critical for MARL without joint action information.
  3) Main Results and Contributions: The main contribution of this paper is that we overcome the aforementioned challenges and develop a consensus-based Markovian sampled decentralized actorcritic algorithm for MARL. Our key results in this paper are summarized as follows:
  • We propose a batch-sampled actor-critic algorithm that uses consensus updates in TD-sharing among agents. This batch sampling approach enables more efficient communication compared to the classical fully decentralized MARL. Specifically, in order to converge to an ǫ neighborhood of the stationary, we requireO(ǫ−1 log(ǫ−1)) rounds of communication while only needing O(ǫ−2 log(ǫ−1)) samples. By contrast, the state-of-the-art MARL requires a communication round per sampling. Also, our algorithm allows the use of constant step-sizes in both the actor and the critic steps.
  • We provide the first-ever sample complexity analysis in the MARL average reward problem setting without joint action information. Our obtained complexity isO(ǫ−2 log(ǫ−1)), where ǫ is the closeness to the neighborhood of stationary point (treating network size N as a fixed constant). It is worth noting that the order-wise sample complexity of our algorithm matches that of the state-of-the-art single-agent RL algorithms.
sections.heading: 2 RELATED WORK
sections.text: In this section, we provide a quick overview on the closely related work on MARL algorithms and their theoretical results, along with several notable related counterparts in single-agent RL.
  1) MARL Theoretical Analysis and Algorithm Design: For recent advances in MARL algorithms and their theoretical results, Zhang et al. (2021a) provided a comprehensive survey. Also, Lee et al. (2020) highlighted the evolution from single-agent to multi-agent RL from a distributed optimization perspective. In the broader area of MARL, a line of research has been focused on the MARL policy evaluation problem. These works analyzed the convergence Doan et al. (2019) and proposed various variance reduction of policy evaluation in decentralized MARL algorithms Zhang et al. (2021b). Doan et al. (2019) used i.i.d. sampling and has shown the sample complexity of Õ(ǫ−1) for their TD(0) learning algorithm to reach a mean-square error convergence. However, these algorithms do not involve policy improvement and solely focus on the performance evaluation of given policies. In the areas of joint policy evaluation and improvement, Foerster et al. (2018) considered multi-agent actor-critic algorithm that has a centralized critic and decentralized actors, which is different from our fully decentralized actor-critic algorithm. In contrast, Zhang et al. (2018) established asymptotic convergence results for fully decentralized MARL actor-critic algorithms. Concurrent with our work, Chen et al. (2021) has recently studied the mini-batch Markovian sampling actor-critic algorithm for a class of discounted reward MARL problems, where the finite-time convergence result is obtained. They have applied batch sampling for both actor and critic steps and achieved a sample complexity of O(ǫ−2 log(ǫ−1)), which is the same as ours. We note that, together with our work, these are the first finite-time convergence results for MARL. However, there are several key differences between our work and (Chen et al., 2021). First, we focus on the average reward problem, while Chen et al. (2021) studied the discounted reward setting. Second, in (Chen et al., 2021), agents share a noisy version of the rewards with the neighbors, which requires a re-sampling process from every sampled reward instance. In contrast, we allow agents to share local TD-errors with their neighbors and no re-sampling is required.
  2) Related Literature in Single-Agent RL: We note that single-agent RL can be viewed as a centralized approach, where a central controller collects joint actions, rewards and even designs policies for agents. For the single-agent average reward setting, Tsitsiklis & Van Roy (1999) first
  analyzed the asymptotic convergence of TD(λ) algorithm with function approximations in the policy evaluation problem. Also, Tsitsiklis & Van Roy (2002) provided insights in terms of differences and connections between average reward and discounted reward of TD-based learning algorithms with function approximations. Recently, Qiu et al. (2021) analyzed the sample complexity for an actorcritic algorithm for the average reward problem. In their actor-critic algorithm, they used batch sampling for the critic learning and i.i.d. sampling for the actor step, with sample complexity being O(ǫ−3 log2(ǫ−1)). By applying mini-batch sampling update, we are able to improve the sample complexity by a factor of O(ǫ−1). Another closely related work on single-agent RL is (Xu et al., 2020), where the authors studied the discounted reward problem. They used batch sampling for both actor and critic steps in their actor-critic algorithm and developed a new technique to handle bias error in the critic step, which we also adopted for the average approximation parameter analysis in our critic step. This achieved the state-of-the-art sample complexity of O(ǫ−2 log(ǫ−1)) for singleagent RL. In addition, the global convergence of actor-critic algorithm to the optimal policy has been studied in the case of discounted setting with single time scale in (Fu et al., 2020) and linear quadratic regulator in (Yang et al., 2019). However, we note that these settings are fundamentally different from the average reward setting and it will be an interesting future direction to consider global convergence possibility in the average reward setting.
  To conclude this section, we summarize the aforementioned related actor-critic and TD algorithms and their sample complexity results in Table 1.
sections.heading: 3 MULTI-AGENT REINFORCEMENT LEARNING WITH AVERAGE REWARD
sections.heading: 3.1 SYSTEM MODEL
sections.text: Consider a multi-agent system with N agents, denoted by N = {1, · · · , N}, operating in a networked environment. Let E be the edge set for a given network G = (N , E). To formulate our MARL problem and facilitate our subsequent discussions, we first define the notion of networked multi-agent MDP as follows.
  Definition 1 (Networked Multi-Agent MDP). Let G = (N , E) be a communication network that connects N agents. A networked multi-agent MDP is defined by following tuple (S, {Ai}i∈N , P, {R i}i∈N ,G), where S is the global state space observed by all agents, A i is the action set for agent i, and P : S×A×S → [0, 1] is a global state transition function, andRi : S×A is the local reward function for agent i. Let A = ∏
  i∈N A i be the joint action set of all agents.
  In this paper, we assume that the global state space S and action space for agent Ai are finite. As a result, the joint action space A is also finite for finite N . We also note that at time t ≥ 0, all agents can observe the current global state st. However, agent i can only observe its own action ait ∈ A
  i, which is the key difference between our model and that in (Zhang et al., 2018), where it is assumed that the joint actions are observable to all agents. Moreover, each agent can only observe its own reward rit, i.e., agents do not observe or share rewards with other agents at time t. The reward function Ri(s, a) is an expectation given s and a, and the instantaneous reward is denoted by ri(s, a), i.e., Ri(s, a) = E[ri(s, a)].
  We consider policies that are stationary. In our MARL system, each agent chooses its action following its local policy πi that is conditioned on the current global state s, i.e., πi(ai|s) is the probability for agent i to choose an action ai ∈ Ai. Then, the joint policy π : S × A → [0, 1] can be written as π(a|s) = ∏
  i∈N π i(ai|s).
  Moreover, the policies at the agents are parameterized. Specifically, each agent i’s local policy can be written as πi
  θi , where θi ∈ Rmi denotes the parameter. We let θ , [(θ1)T , · · · , (θN )T ]T ∈
  R ∑N i=1mi . Then, we can write the joint policy as follows: πθ(a|s) = ∏ i∈N πθi(a i|s).
sections.heading: 3.2 TECHNICAL ASSUMPTIONS
sections.text: We now state the following assumptions on the positivity and continuity of πi θi (ai|s), which guarantee the stationary distribution of {st} under any given policy. Assumption 1. For any i ∈ N , s ∈ S , ai ∈ Ai and θi ∈ Rmi , the policy function πi θi (ai|s) ≥ 0. Also, πi θi (s, a) is a continuously differentiable with respect to the parameter θi. In addition, for any θ, we assume the induced Markov chain {st}t≥0 is irreducible and aperiodic, and its transition matrix P θ is P θ(s′|s) = ∑
  a∈A πθ(a|s) · P (s ′|s, a), ∀s, s′ ∈ S.
  Assumption 1 guarantees that the states have a stationary distribution dθ(s) over S given any policy πθ. As a result, the Markov chain of state action pair {(st, at)} also has a stationary distribution dθ(s) · πθ(a|s). Assumption 2. The instantaneous reward rit is uniformly bounded by a constant rmax > 0 for any i ∈ N and t ≥ 0.
  Assumption 2 is common in the literature (see, e.g., (Zhang et al., 2018; Xu et al., 2020; Doan et al., 2019)) and easy to be satisfied in many practical MDP models with finite state and action spaces.
  Assumption 3. Let A be a consensus weight matrix for a given communication network G. There exists a positive constant η > 0 such that A ∈ RN×N is doubly stochastic and Aii ≥ η, ∀i ∈ N . Moreover, Aij ≥ η if i, j are connected, otherwise Aij = 0 for all i, j.
  Assumption 3 is standard in the distributed multi-agent optimization literature Nedic & Ozdaglar (2009). We remark that for a practical choice of A, one can use the following form A =
  1 deg(G) (deg(G) · I − L), where deg(G) is the degree of the graph G (i.e. the maximal vertex degree), I is the identity matrix of conforming dimensionality, and L is the Laplacian matrix of the graph. It is easy to verify that this matrix is symmetric, doubly stochastic and η ≥ 1
  deg(G) ≥ 1 N .
  Assumption 4. Each agent i’s value function is parameterized by the class of linear functions, i.e., Vθ(s;w) = φ(s) Tw where φ(s) , [φ1(s), · · · , φK(s)] T ∈ RK is the feature associated with the state s ∈ S and K < |S|. The feature vectors φ(s) are uniformly bounded for any s ∈ S . Without loss of generality, we assume that ‖φ(s)‖ ≤ 1. Furthermore, the feature matrix Φ ∈ R|S|×K has full column rank. Also, for any u ∈ RK , Φu 6= 1, where 1 is an all-one vector.
  This assumption on features is standard and has been widely adopted in the literature, e.g., (Tsitsiklis & Van Roy, 1999; Zhang et al., 2018; Qiu et al., 2021). This assumption implies the following property: for any policy πθ, the inequality w
  TAπθw < 0 holds for any w 6= 0, where Aπθ is defined as
  Aπθ := Es∼dθ(s),s′∼P (·|s)[(φ(s ′)− φ(s))φT (s)]. (1)
  This property further implies that for all θ, Aπθ is invertible and λmax(Aπθ + A T πθ ) < 0 (Qiu et al., 2021), where λmax(·) is the largest eigenvalues of the matrix. Assumption 5. There exists a constant λA > 0 such that λmax(Aπθ + A T πθ ) ≤ −λA holds for all θ ∈ R ∑ i∈N mi .
  Assumption 5 ensures the optimal approximation w∗θ for any given policy πθ is uniformly bounded (see discussion before Theorem 2 and Lemma 4).
  Assumption 6. Let ψθ(s, a) = ∇θ log πθ(a|s) be the score function for any state-action pair (s, a). For any two policy parameters θ, θ′ ∈ R ∑ i∈N mi , and any state-action pair (s, a) ∈ S×A, there exist
  positive constants such that the following hold: 1): ‖ψθ(s, a)‖ ≤ Cψ; 2): ‖∇θJ(θ) −∇θJ(θ ′)‖ ≤ LJ‖θ − θ′‖; where J(θ) is defined in (2) and ‖ · ‖ denotes the ℓ2-norm.
  Assumption 6 says that the score function is uniformly bounded for any policy and the gradient of the objective function has a Lipschitz property with respect to the policy parameter. This assumption has also been adopted in the analysis of the single-agent actor-critic algorithm in (Qiu et al., 2021). We note that for the discounted reward problem, this gradient Lipschitz property can be guaranteed through (Xu et al., 2020, Assumption 2). We note that Assumption 6 can be satisfied by the class of soft-max policy under the Assumption 1, as in (Guo et al., 2021).
sections.heading: 3.3 THE OBJECTIVE FUNCTION
sections.text: The goal of the agents is to find a joint policy πθ to maximize the global average long-term reward. Mathematically, this can be written as:
  maximizeθ J(θ) = lim T→∞
  1 T E
  (
  T−1 ∑
  t=0
  1
  N
  ∑
  i∈N
  rit+1
  )
  = ∑
  s∈S
  dθ(s) ∑
  a∈A
  πθ(a|s) · R̄(s, a), (2)
  where R̄(s, a) = 1 N
  ∑
  i∈N R i(s, a) is the global average reward function. Let r̄t = 1 N
  ∑
  i∈N r i t,
  then we have R̄(s, a) = E[r̄t+1|st = s, at = a]. Next, we define the state-action value function: Qθ(s, a) = E[ ∑∞ t=0 r̄t+1 − J(θ)|s0 = s, a0 = a, πθ], and the state value function Vθ(s) = ∑ a∈AQθ(s, a) · πθ(a|s). The advantage function is defined as follows:
  Advθ(s, a) = Qθ(s, a)− Vθ(s). (3)
sections.heading: 3.4 POLICY GRADIENT THEOREM
sections.text: The gradient of a policy πθ for decentralized policy gradient is stated in the following theorem.
  Theorem 1 (Policy Gradient Theorem for MARL (Zhang et al., 2018)). For any θ, let πθ : S×A → [0, 1] be a policy and let J(θ) be the global average long-term average return defined in (2). Then, the gradient of J(θ) with respect to parameter θi can be computed as:
  ∇θiJ(θ) = Es∼dθ,a∼πθ [∇θi log π i θi(a i|s) ·Aθ(s, a)]. (4)
sections.heading: 4 A CONSENSUS-BASED ACTOR-CRITIC ALGORITHM
sections.text: In this section, we propose a consensus-based actor-critic algorithm that includes two key steps: actor and critic. In the critic step, the algorithm evaluates the value functions for the policy πθt at time t. After the critic step, the algorithm enters the actor step, which improves the policy parameter θt according to the direction from policy gradient as shown in Theorem 1. In both steps, we use constant step-sizes and adopt batch sampling.
  In this paper, we use linear function approximations for the value functions. Specifically, each agent i has a parameter wi ∈ RK to approximate the global value functions Vθ(s;wi) for each state s ∈ S . For linear approximation, we have Vθ(s;w
  i) = φ(s)Twi, where φ(s) ∈ RK denotes the feature for state s. As a result, the gradient of value function at state s with respect to approximation parameter wi is φ(s), i.e. ∇wVθ(s;wi) = φ(s).
  1) The Critic Step: The critic step is achieved through its own oracle, which is summarized in Algorithm 1. In the critic step, we allow the agents to communicate the approximation parameters w(s) with their neighbors via the communication network with consensus weight matrix A. For agent i ∈ N , the parameter is locally updated by following rules:
  µik,τ+1 = (1− β)µ i k,τ + βr i k,τ+1 (5)
  δik,τ = r i k,τ+1 − µ i k,τ + φ T (sk,τ+1)w i k − φ T (sk,τ )w i k (6)
  w̃ik = w i k +
  β
  M
  M−1 ∑
  τ=0
  δik,τ · φ(sk,τ ), (7)
  Algorithm 1: Mini-batch TD learning for Critic
  Input : s0, πθt , φ, step-size β, critic step iteration number K, critic batch size M , the communication network A
  1 for k = 0, · · · ,Kc − 1 do 2 sk,0 = sk−1,M ( when k = 0, sk,0 = s0); 3 for all i ∈ N do 4 for τ = 0, · · · ,M − 1 do 5 Execute action aik,τ ∼ π
  i θit (·|sk,τ );
  6 Observe the state sk,τ+1 and reward r i k,τ+1; 7 Update µik,τ+1 ← (1− β) · µ i k,τ + β · r i k,τ+1; 8 Update δik,τ ← r i k,τ+1 − µ i k,τ + φ T (sk,τ+1)w i k − φ T (sk,τ )w i k; 9 end
  10 Critic Step: w̃ik ← w i k + β M ∑M−1 τ=0 δ i k,τ · φ(sk,τ ); 11 Consensus Update wik+1 ← ∑ j∈Ni A(i, j) · w̃jk; 12 end
  13 end Output: sKc−1,M , wKc
  where β > 0 is the step-size of the critic step, µik,τ is the estimate of the long-term return of agent i, and δik,τ is the local TD-error for agent i at iteration k using sample τ . Here, in each iteration k in the critic step, the approximation parameter is locally updated through a batch of sampling as in (7), where the batch size is M . Then, agent i will further update the approximation parameter wi through a weighted average of its local and neighboring agents’ parameters as follows: wik+1 = ∑ j∈Ni A(i, j)w̃ik. This batched sampling update continues forKc iterations for each given policy πθt .
  2) The Actor Step: As shown in Theorem 1, the advantage function needs to be known to compute the gradient. However, from the definition in (3), the joint action a also has to be known to compute the advantage function, whereas in our model, each agent can only observe its own action. As a result, an estimation of the advantage function is required. Here, we show that the global TD-error is an unbiased estimate of the advantage function.
  At time t, suppose we have samples st, at, st+1 and the rewards {r i t+1}i∈N then the advantage function is as follows: Advθ(st, at) = E[r̄t+1 − J(θ) + Vθ(St+1) − Vθ(st)|st, at], and the global TD-error can be computed as follows: δt = r̄t+1 − µt + Vθ(st+1) − Vθ(st), where µt+1 = (1 − α) · µt +α · r̄t+1 is the estimate for the average long term return, and α is the step-size for the actor step. Hence, we have that the expected global TD-error is the advantage function, i.e., E[δt|st, at] = Aθ(st, at). Thus, we can use this global TD-error as an unbiased estimate of the advantage function. For agent i, the local TD-error can be computed as δit = r i t+1 − µ i t + Vθ(st+1) − Vθ(st), where µit+1 = (1− α)µ i t + αr i t+1. We also note that µt = 1 N ∑ i∈N µ i t .
  Thus, once each agent knows the global TD-error, the policy parameter can be updated according to the policy gradient rule in (4). However, without any communication, each agent only has the knowledge of its own local TD-error. Moreover, we will show that the networked TD-error is actually the average of the local TD-errors. Specifically,
  δt = r̄t+1 − µt + Vθ(st+1)− Vθ(st) = 1
  N
  ∑
  i∈N
  rit+1 − 1
  N
  ∑
  i∈N
  µit + Vθ(st+1)− Vθ(st)
  = 1
  N
  ∑
  i∈N
  [rit+1 − µ i t + Vθ(st+1)− Vθ(st)] =
  1
  N
  ∑
  i∈N
  δit.
  For any time t, the average of the local TD-errors is an unbiased estimate of the advantage function. Therefore, we just need to let each agent communicate with its neighbors so that an average of all local TD-errors can be reached or estimated for all agents.
  Algorithm 2: Minibatch-TD sharing for Actor Critic Algorithm
  Input : state feature matrix Φ, actor step-size α, Initial parameters θi for all i ∈ N
  1 for t = 0, · · · , T − 1 do 2 critic update: wt, st,0 = Minibatch-TD-critic in Algorithm 1; 3 for l = 0, · · · , B − 1 do 4 for all i ∈ N do 5 Execute action ait,l ∼ π
  i θit (·|st,l);
  6 Observe the state st,l+1 and reward r i t,l+1; 7 Update µit,l+1 ← (1− α) · µ i t,l + α · r i t,l+1; 8 Update δit,l ← r i t,l+1 − µ i t,l + φ T (st,l+1)w i t − φ T (st,l)w i t; 9 Update ψit,l ← ∇θi log π i θit (st,l, a i t,l);
  10 end
  11 end
  12 Let ∆0 =
  
   
  δ1t,0 · · · δ N t,0
  ... . . .
  ...
  δ1t,B−1 · · · δ N t,B−1
  
    ;
  13 for i ∈ N do 14 for k = 0 : tgossip − 1 do 15 ∆k+1(:, i)← ∑
  j∈Ni A(i, j) ·∆k(:, j);
  16 end
  17 end 18 for all i ∈ N do 19 Let δ̃it,1:B−1 = ∆tgossip(:, i) ; 20 Actor Step: θit+1 ← θ i t + α B ∑B−1 l=0 δ̃ i t,l · ψ i t,l; 21 end
  22 end
  Output: θT̂ with T̂ chosen uniformly from {1, · · · , T}
  From the results in (Nedic & Ozdaglar, 2009), we have limτ→∞A τ (x1, · · · , xN )T = 1 N ∑ i∈N x i1. However, this convergence is asymptotic, meaning that the exact estimation can only be achieved with infinite iterations (i.e., τ → ∞). In practice, since one can only apply finite iterations, we use δ̃it to denote the estimate of the global TD-error maintained by agent i after tgossip iterations of updates at time t, i.e., δ̃ i t = [A tgossip ]i∆ 0 t , where ∆ 0 t = (δ 1 t , · · · , δ N t )
  T is the N - dimension vector of local TD-errors at time t. We note that agents do not need to know the weight information of other agents. Rather, each agent just needs to exchange updated estimate of the local TD-errors with its neighbors for tgossip rounds as shown in Lines 11-16 of Algorithm 2. This communication among agents is also done in a batch fashion, with batch size being B. This implies that for each outer iteration t ∈ {0 · · · , T − 1}, only tgossip rounds of communication for every B samples are needed.
  Combined with a B-batched Markovian sampling, the parameter θi update for agent i ∈ N can be written as follows: θit+1 = θ i t + α B ∑B−1 l=0 δ̃ i t,l · ψ i t,l where α is the step-size for the actor step and ψit,l = ∇θi log π i θit (st,l, a i t,l) is the local score function for agent i using l-th sample at time t. The actor step of our algorithm is illustrated in Algorithm 2.
sections.heading: 5 THEORETICAL CONVERGENCE ANALYSIS
sections.text: In this section, we present the convergence results for both the critic and actor steps in Theorems 2 and 3, respectively. Due to space limitation, we relegate the proofs to the supplementary material.
sections.heading: 5.1 CONVERGENCE ANALYSIS FOR CRITIC (ALGORITHM 1)
sections.text: For a given policy πθ, we define bπθ = Es∼dθ,a∼πθ [φ(s)(r̄(s, a) − J(θ))], where r̄(s, a) = 1 N ∑ i∈N r i(s, a) and J(θ) are as defined in (2). For all agents, the optimal solution (Wu et al., 2020), (Qiu et al., 2021) of this critic learning is w∗θ = −A −1 πθ bπθ , where Aπθ is defined as in (1). The invertiblity of Aπθ is due to the Assumptions 1 and 4 (see more details in (Qiu et al., 2021; Tsitsiklis & Van Roy, 1999)). Then, the convergence of the critic step is summarized as follows:
  Theorem 2 (Convergence and Sample Complexity of the Critic). Suppose that Assumptions 1-5 hold. For any given policy πθ, consider the iteration generated by Algorithm 1. Recall the definition of λA in the Assumption 5 and let β < min{ ηN−1 2(1−ηN−1) , λA 128 , 4 λA }. It then follows that:
  E[
  N ∑
  i=1
  ||wiKc − w ∗ θ || 2] ≤ κ′1N 4γ2Kc + κ′′2N 6β2 + κ3N 5γKcβ
  + 2N(1− λA 8 β)Kc ||w̄0 − w ∗ θ || 2 2 + κ4 M N, (8)
  where γ := (1−ηN−1)·(1+2β) < 1 and κ′1, κ ′′ 2 , κ3, κ4 are positive constants. If we further letKc ≥ 1 2 max{logγ−1 6κ′1N 4 ǫ , log
  (1− λA 8 β) −1
  12N ||w̄0−w ∗ θ || 2 2
  ǫ }, β ≤ min{ 1 N3
  √
  ǫ 6κ′′2
  , η N−1
  2(1−ηN−1) , λA 128 , 4 λA }
  and M ≥ 6κ4N ǫ , then we have E[ ∑N i=1 ||w i Kc − w∗θ || 2] ≤ ǫ for all i ∈ N with total sample complexity given by KcM = O( N ǫ log(N ǫ )) for a sufficiently large N .
  Theorem 2 establishes a convergence result for the policy evaluation of a given policy πθ. We can see that our constant step-size batch-sampled critic process can achieve the same complexity of Õ(ǫ−1) order-wise as the TD(0) learning in Doan et al. (2019), where diminishing step-sizes were used. On the other hand, in the single agent average reward setting of Qiu et al. (2021), there exists a non-vanishing error term in their critic convergence. In contrast, with proper choices of iteration number Kc and batch size M , our mean-square error can be arbitrarily small.
sections.heading: 5.2 CONVERGENCE ANALYSIS FOR ACTOR-CRITIC ALGORITHM (ALGORITHM 2)
sections.text: Define the approximation error introduced by using linear approximation in the critic step, ξcriticapprox = max θ∈R ∑ i∈N m i Es∼dθ [|Vπθ (s) − Vw∗πθ (s)|2]. For a given policy πθ, this error represents the gap between ground truth value function under such policy and the value function obtained by the best possible linear approximation. Such an error term is standard in the literature where linear approximations are adopted (Qiu et al., 2021; Xu et al., 2020). Let Rw, defined in Lemma 4, be an upper bound on ||wθ|| for all policy parameter θ.
  Theorem 3 (Overall Convergence Rate and Sample Complexity). Suppose that Assumption 1-6 hold. Consider the actor-critic algorithm in Algorithm 2. Let step-size α = 14LJ . It then holds that:
  E[||∇θJ(θT̃ )|| 2] ≤ 16LJrmax T + 72N
  ∑T t=1 ∑N i=1 ||w i t − w ∗ θt ||2
  T + 18κ3N
  2(1− ηN−1)2tgossip
  + 72ξcriticapprox + 288 (rmax +Rw)
  2[1 + (2κ− 1)ρ]
  B(1− ρ) N, (9)
  where κ3 is a positive constant. Furthermore, let T ≥ 64LJrmax ǫ ,B ≥ 576 (rmax+2Rw) 2[1+(2κ−1)ρ] (1−ρ) N ǫ and the communication round among the agents tgossip ≥ 1 2 log(1−ηN−1)−1 64κ3N 2 ǫ . Suppose for the same setting as in Theorem 1 holds so that E[ ∑N i=1 ||w i Kc − w∗θ || 2] ≤ ǫ288N for all 0 ≤ t ≤ T , then we have E[||∇θJ(θt)||2] ≤ ǫ + O(ξcriticapprox), with a total complexity of (B + MKc)T = O(N 2
  ǫ2 log(N ǫ )). And the communication complexity is (Kc + tgossip)T = O( 1 ǫ log(N ǫ )).
  Theorem 3 concludes the overall sample complexity of our proposed actor-critic algorithm. The sample complexity of O(ǫ−2 log(ǫ−1)) matches the state-of-the-art single-agent actor-critic RL by Xu et al. (2020) and the discounted MARL by Chen et al. (2021).
  We note that the overall communication complexity also matches that of (Chen et al., 2021) in the discounted reward setting. However, our work is still an improvement compared to the classical MARL in Zhang et al. (2018) for the average reward setting. Specifically, Zhang et al. (2018) needed a communication round after each sampling. By contrast, in this paper, we only need a communication round per O(ǫ−1) sampling. This is thanks to the use of batch sampling in the actor step. Also because of the batch sampling, we are able to use a constant step-size for both actor and critic steps. Here, the overall communication cost is measured by the number of communication rounds rather than the size of bits transmitted over the network. We follow the standard definition of communication complexity in the literature, which is widely adopted in the literature, see (Chen et al., 2018) (Zhang et al., 2019). However, we note that tgossip, actor step batch size B and critic iteration rounds Kc, scale with O(log 1/ǫ), O(1/ǫ) and O(log 1/ǫ) respectively as indicated in the Theorem 3 and 2. The amount of information (in terms of bits) is (KcNK +BNtgossip)T = O( N ǫ2 log N ǫ ).
sections.heading: 6 EXPERIMENTAL RESULTS
sections.text: In this section, we conduct experiments to compare our proposed consensus-based TD-sharing MARL algorithm with the most related MARL algorithm 1 in Zhang et al. (2018) that also studied average reward. To our knowledge, this is the only work that is directly comparable to ours. The key difference is that the knowledge of joint action is assumed in Zhang et al. (2018), but not in our work. We vary the system size from N = 6, 10 to 15. The blue curve is our TD-sharing algorithm and the red curve is classical MARL algorithm in Zhang et al. (2018). The curves represent the average results of 10 trials and the 95% confidence intervals are also plotted. For the details, see A.1 in Appendix. The results in Figure 1 show that for different system sizes, both algorithms converge to a reasonable objective value. Note that if we use uniformly random policy as the baseline policy, then the objective values will be around 2 due to the setting of our experiments. All simulation results are above this threshold and our TD-sharing algorithm converge to a better objective value. See Section A.2 for addition experiment results. We also note that, for our algorithm, the empirical sample complexity does not scale with respect to the system size N . This may indicate that the system size N in finite-time convergence theorems are likely loose, which is due to the analytical techniques we use rather than the nature of our algorithm.
sections.heading: 7 CONCLUSION AND DISCUSSION
sections.text: In this paper, we studied fully decentralized MARL in average reward setting and proposed a batch-sampled actor-critic algorithm. Our main contribution is to establish the first finite time convergence result for fully decentralized MARL in average reward setting, where the complexity is O(ǫ−2 log(ǫ−1)), which matches that of the state-of-the-art single agent RL. The algorithm reaches such convergence with a better communication efficiency. However, it is still in the preliminary stage of the convergence analysis of the MARL since we only used the vanilla average. The future direction will be how to design a more scalable algorithm in terms of system size.
sections.heading: A APPENDIX
sections.text: In this section, we provide lemmas that lead to the proof of both Theorem 2 and Theorem 3.
  In this paper, we use || · || for 2-norm and || · ||TV for total variance norm. 〈·, ·〉 denotes the inner product. Superscript i in quantity x, i.e. xi, denotes the x quantity correspond to agent i ∈ N . λ(·) and σ(·) denote the eigenvalues and singular values of the corresponding matrix respectively. All vectors are assumed to be column vector, unless specified. (·)T is the transpose of an matrix or vector. We use 1 to denote all-1 vector with a proper dimension. ker{·} and ran{·} denote the kernel and range of a matrix respectively.
  First, we explain the detail of our experiment setup.
  A.1 EXPERIMENT SETUP
  We considered the same setting as in the Section 6.1 of Zhang et al. (2018). There are N agents, each has a binary-valued action space, i.e. Ai = {0, 1}, for all i ∈ N . In addition, in all the results shown here, we set |S| = 5 states. The elements in the transition matrix are uniformly sampled from the interval [0, 1] and normalized to be stochastic. We also added 10−5 onto each element to ensure ergodicity of the MDP such that the Assumption 1 is satisfied. For each agent i and state action pair (s, a), the mean reward Ri(s, a) is sampled uniformly from [0, 4]. The instantaneous rewards rit are sampled from the uniform distribution [Ri(s, a)− 0.5, Ri(s, a) + 0.5]. The policy is parameterized following the Bolzmann policies, i.e.,
  πiθi(s, a i) =
  exp(qT s,ai θi) ∑
  bi∈Ai exp(q T s,bi θi)
  where qT s,bi is the feature vector with the same dimension as θi, for all s ∈ S and i ∈ N . Here, we set m1 = · · · = mN = 5. The elements of qs,bi are uniformly sampled from [0, 1e3]. We set the dimension for state features K = 3. The feature matrix Φ are insured to have full column. The stepsizes for classical MARL are set as βw,t = 1 t0.51 and βθ,t = 1 t0.52 . The network matrix as chosen as a ring network with diagonal elements being 0.4 and off diagonal elements 0.3 .
  For our algorithm, we used step-sizes α = 1 and β = 0.1. The batch sizes are B = 10, M = 10 and the critic iterations are 10 and actor iterations are T = 100.
  A.2 ADDITIONAL EXPERIMENT RESULTS
  We have modified classical MARL into i)constant stepsize MARL, ii)batch MARL and iii)batch constant stepsize MARL. For classical MARL and batch MARL, we chose the stepsizes as βw =
  1 t0.65 and βθ = 1 t0.85 as in the paper (Zhang et al., 2018), and for the constant steptize MARL and batch constant stepsize MARL, we chose stepsizes to be βw = 0.9 and βθ = 0.01. For batch MARL and batch constant stepsize MARL, we used batch size as 10. Other parameters are the same as in the A.1. We vary the system sizes from N = 5 to N = 15 and the empirical comparison results are in Figure 2 (a)-(c). In addition, we provide the comparison between average reward setting with the discounted counterpart of our algorithms for discounting factors ranging from γ = 0.1 to γ = 0.999. As we can see from Figure 2 (a)-(c), our TD-sharing algorithm performs well compared to the baseline algorithms. Among the modified algorithms, batch constant stepsize MARL shows improvement compared to the classical MARL in all three cases. Moreover in (b) and (c), when system size is larger, specifically N = 10 and N = 15, either batch modification or constant stepsize modification seem to improve the classical MARL. Yet in (a), for smaller system size, i.e. N = 5, only modifying to the batch size or constant stepsizes don’t seem to improve the performance. In addition, in (d), for discounted setting, as γ increases and gets closer to 1, the objective value is closer to the average reward setting. It is because as the discounting factor approaches 1, the effective horizon, which scales with O( log ǫ −1
  1−γ ) (Kakade, 2003), to an ǫ close stationary point gets
  larger and larger. As a result, it will get closer to the average reward setting. However, we can see average setting value converges to a significantly higher value. More importantly, one advantage of the average reward setting is that with more samples, the policies can potentially keep updating and so is the objective value. From Figure 2(d), we can see that as the number of sample increases, the average reward setting objective value still evolves, which means the policies are keep updating. However, for the discounted reward case, the extra sample doesn’t affect the objective value.
  In Figure 3, we have shown the results of different network structures on the performance when system size is 10. We compared the ring network, small world network and 2-regular network. The small world network is generated with mean node degrees being 4 and rewiring probability being 0.2. The entries of matrix A, for both small world network and regular network, are set as the way discussed after Assumption 3. Different network structures exhibit different performances, but all are better than baseline value 2. Among these three structures, within given sample numbers, ring network yields the best result.
  A.3 SUPPORTING LEMMAS FOR THEOREM 2
  Because of the Assumption 1, by (Levin & Peres, 2017, Theorem 4.9), for aperiodic and irreducible Makrov chains, we can guarantee the following lemma holds: Lemma 1. For any policy parameter θ ∈ R ∑
  i∈N mi , consider the MDP with policy πθ and transition kernel P (·|s, a). Let dθ be the stationary distribution of the MDP. There exist constants κ > 0 and ρ ∈ (0, 1) such that sups∈S ||P (st|s0 = s)− dθ||TV ≤ κρ t, ∀t ≥ 0.
  This lemma has been adopted directly as an assumption in many related works in theoretical analysis of RL (Xu et al., 2020; Chen et al., 2021; Qiu et al., 2021).
  As a result of the Lemma 1, the Markov chain of state-action pair {st, at}t≥0 for policy πθ also has the property of ergodicity. We state this result as the following lemma.
  Lemma 2. Suppose the Assumption 1 hold, let νθ be the stationary distribution of the state-action pair MDP. Then, we have
  sup s∈S ||P (st, at|s0 = s)− νθ||TV ≤ κρ
  t, ∀t ≥ 0. (10)
  Proof. For any given s0 ∈ S , by definition, we have
  ||P (st, at|s0)− νθ||TV = 1
  2
  ∑
  (s,a)∈S×A
  |P (st = s, at = a|s0)− νθ(s, a)|
  = 1
  2
  ∑
  (s,a)∈S×A
  |P (st = s|s0)πθ(at = a|st = s)− ν s θ(s)πθ(a|s)|
  = 1
  2
  ∑
  (s,a)∈S×A
  |(P (st = s|s0)− ν s θ(s))πθ(a|s)|
  = 1
  2
  ∑
  (s,a)∈S×A
  πθ(a|s)|P (st = s|s0)− ν s θ(s)|
  = 1
  2
  ∑
  s∈S
  |P (st = s|s0)− ν s θ(s)|
  = ||P (st|s0)− ν s θ ||TV ≤ κρ t.
  Since it holds for all s0 ∈ S , equation 10 holds.
  As a result of Assumption 5, we have the following lemmas.
  Lemma 3. For all policy πθ, we have
  〈w,Aπθw〉 ≤ − λA 2 ||w||2 (11)
  where λA is defined in Assumption 5.
  Proof. Because of the fact wTAπθw = w TATπθw, we have
  wTAπθw = 1
  2 (wTAπθw + w TATπθw)
  = 1
  2 wT (Aπθ +A T πθ )w
  ≤ − λA 2 wTw = − λA 2 ||w||2. (12)
  In fact, interestingly enough, the Assumption 5 and Lemma 3 are equivalent in a sense that if the statement in the Lemma 3 is taken as the assumption, the statement in the Assumption 5 can be obtained as a result. And the paper (Xu et al., 2020) used the statement in the Lemma 3 as an assumption, whereas in ours and (Qiu et al., 2021), we assumed Assumption 5.
  Lemma 4. For any given policy πθ, the corresponding optimal value function approximation parameter w∗θ is uniformly bounded, specifically, there exists Rw := 4rmax λA > 0 such that
  ||w∗θ || ≤ Rw. (13)
  Proof. It’s easy to see that J(θ) ≤ rmax from equation 2 and r̄(s, a) ≤ rmax for any (s, a) pair. Then, we have
  ||w∗θ || = || −A −1 πθ bπθ ||
  = || − ( Es∼dθ(s),s′∼P (·|s)[(φ(s ′)− φ(s))φT (s)] )−1 · Es∼dθ,a∼πθ [φ(s)(r̄(s, a)− J(θ))]||
  ≤ || − ( Es∼dθ(s),s′∼P (·|s)[(φ(s ′)− φ(s))φT (s)] )−1 || · ||Es∼dθ,a∼πθ [φ(s)(r̄(s, a)− J(θ))]|| = 1
  σmin ( −Es∼dθ(s),s′∼P (·|s)[(φ(s ′)− φ(s))φT (s)]
  ) · ||Es∼dθ,a∼πθ [φ(s)(r̄(s, a)− J(θ))]||
  ≤ 2||Es∼dθ,a∼πθ [φ(s)(r̄(s, a)− J(θ))]||
  λmin(−Aπθ −A T πθ )
  ≤ 2Es∼dθ,a∼πθ [||φ(s)|| · (|r̄(s, a)|+ |J(θ)|)]
  λ = 4rmax λA
  where the third equality used the fact ||A−1|| = 1 σmin(A) and the second from the last inequality is from Bhatia (1997) (Proposition III 5.1) .
  Note that, for agent i ∈ N , the estimated long term average reward µik,τ at sample τ of iteration k in equation 5 can be written as
  µik,τ = β τ ∑
  l=1
  (1− β)τ−lrik,l + (1− β) τµi0. (14)
  Lemma 5. For any i ∈ N and t ≥ 0, step size 0 < β < 1, for the estimated long term average reward for agent i, we have
  µit+1 = (1− β)µ i t + βr i t (15)
  is bounded by rmax, i.e. |µ i t+1| ≤ rmax.
  Proof. WLOG, we suppose that 0 < µi0 ≤ rmax, we have
  |µit+1| = |(1− β)µ i t + βr i t|
  ≤ (1− β)|µit|+ β|r i t|. (16)
  By the supposition, we have |µi0| ≤ rmax. We assume |µ i t| ≤ rmax holds for iteration t > 0, then for t+ 1, by equation 16
  |µit+1| ≤ (1− β)|µ i t|+ β|r i t| ≤ (1− β)rmax + βrmax = rmax.
  Therefore, Lemma 5 holds by mathematical induction.
  For a given policy πθ, to establish a bound on the difference between the optimal approximation parameter w∗θ , we first derive a bound the difference between parameter w i k and the average among all agents w̄k at time k. Then, we derive a bound for the difference between average w̄k and the optimal w∗θ .
  We have following notations for the analysis. Given an agent i ∈ N , we consider the consensus error at time k and we denote Qik = w i k − w̄k, where w̄k := 1 N ∑ i∈N w i k. Then, we denote the matrix form as Qk = [Q 1 k, · · · , Q N k ] ∈ R K×N Then, we have the following lemma.
  Lemma 6. Suppose the Assumption 2 and 3 hold. For the consensus error matrix, we have
  ||Qk+1|| ≤κ1N 2γk||Q0||+ κ ′ 2N 3β (17)
  where γ := (1− ηN−1) · (1+2β) < 1, κ1 = 2(1+2β)(1+ η−(N−1)) and κ′2 = 4(1+η−(N−1))rmax 1−γ .
  Proof. By equation 7, the parameter update w̃ik for agent i at iteration k can be written as follows
  w̃ik = w i k +
  β
  M
  M ∑
  τ=0
  δik,τ · φ(sk,τ )
  = wik + β
  M
  M−1 ∑
  τ=0
  [rik,τ+1 − β τ ∑
  l=1
  (1− β)τ−lrik,l − (1− β) τµi0
  + φ(sk,τ+1) Twik − φ(sk,τ ) Twik] · φ(sk,τ )
  = wik + β
  M
  M−1 ∑
  τ=0
  φ(sk,τ )[φ(sk,τ+1)− φ(sk,τ )] Twik
  + β
  M
  M−1 ∑
  τ=0
  (rik,τ+1 − β τ ∑
  l=1
  (1− β)τ−lrik,l − (1− β) τµi0)φ(sk,τ ). (18)
  After a consensus step, the update will be
  wik+1 = ∑
  j∈Ni
  A(i, j) · w̃jk
  = ∑
  j∈Ni
  A(i, j) · [wjk + β
  M
  M−1 ∑
  τ=0
  φ(sk,τ )[φ(sk,τ+1)− φ(sk,τ )] Twjk
  + β
  M
  M−1 ∑
  τ=0
  (rjk,τ+1 − β τ ∑
  l=1
  (1− β)τ−lrjk,l − (1− β) τµj0)φ(sk,τ )]
  = ∑
  j∈Ni
  A(i, j) · wjk + β
  M
  M−1 ∑
  τ=0
  φ(sk,τ )[φ(sk,τ+1)− φ(sk,τ )] T ∑
  j∈Ni
  A(i, j) · wjk
  + β
  M
  M−1 ∑
  τ=0
  φ(sk,τ ) ∑
  j∈Ni
  A(i, j) · (rjk,τ+1 − β τ ∑
  l=1
  (1− β)τ−lrjk,l − (1− β) τµj0)
  = wk · (Ai,:) T +
  β
  M
  M−1 ∑
  τ=0
  φ(sk,τ )[φ(sk,τ+1)− φ(sk,τ )] Twk · (Ai,:) T
  + β
  M
  M−1 ∑
  τ=0
  φ(sk,τ )Ai,:(rk,τ+1 − β τ ∑
  l=1
  (1− β)τ−lrk,l − (1− β) τµ0) (19)
  where wk = [w 1 k, w 2 k, · · · , w N k ] ∈ R K×N is the matrix form of all parameters at time k, Ai,: is the i-th row of matrix A and rk,l = (r 1 k,l, · · · , r N k,l). Now we consider the average dynamics of the algorithm. Recall w̄k = 1 N ∑ i∈N w i k, then using equation 19 we have
  w̄k+1 = 1
  N
  ∑
  i∈N
  wik+1
  = 1
  N
  ∑
  i∈N
  (
  wk · (Ai,:) T +
  β
  M
  M−1 ∑
  τ=0
  φ(sk,τ )[φ(sk,τ+1)− φ(sk,τ )] Twk · (Ai,:) T
  + β
  M
  M−1 ∑
  τ=0
  φ(sk,τ )Ai,:(rk,τ+1 − β τ ∑
  l=1
  (1− β)τ−lrk,l − (1− β) τµ0)
  )
  = 1
  N wk · 1+
  β
  M
  M−1 ∑
  τ=0
  φ(sk,τ )[φ(sk,τ+1)− φ(sk,τ )] T 1
  N wk · 1
  + β
  M
  M−1 ∑
  τ=0
  φ(sk,τ ) 1
  N
  ∑
  i∈N
  Ai,:(rk,τ+1 − β τ ∑
  l=1
  (1− β)τ−lrk,l − (1− β) τµ0)
  = w̄k + β
  M
  M−1 ∑
  τ=0
  φ(sk,τ )[φ(sk,τ+1)− φ(sk,τ )] T w̄k
  + β
  M
  M−1 ∑
  τ=0
  φ(sk,τ ) 1
  N 1T (rk,τ+1 − β
  τ ∑
  l=1
  (1− β)τ−lrk,l − (1− β) τµ0)
  = w̄k + β
  M
  M−1 ∑
  τ=0
  φ(sk,τ )[φ(sk,τ+1)− φ(sk,τ )] T w̄k
  + β
  M
  M−1 ∑
  τ=0
  φ(sk,τ )(r̄k,τ+1 − β τ ∑
  l=1
  (1− β)τ−lr̄k,l − (1− β) τµ0) (20)
  where r̄k,l = 1 N
  ∑
  i∈N r i k,l.
  Given an agent i ∈ N , we consider the consensus error at time k and recall Qik = w i k − w̄k. Then, we have
  Qik+1 =w i k+1 − w̄k+1
  =wk · (Ai,:) T − w̄k +
  β
  M
  M−1 ∑
  τ=0
  φ(sk,τ )[φ(sk,τ+1)− φ(sk,τ )] T (wk · (Ai,:) T − w̄k)
  + β
  M
  M−1 ∑
  τ=0
  φ(sk,τ )(Ai,: − 1
  N 1T )(rk,τ+1 − β
  τ ∑
  l=1
  (1− β)τ−lrk,l − (1− β) τµ0). (21)
  Then, for the matrix form Qk = [Q 1 k, · · · , Q N k ] ∈ R K×N , we have
  Qk+1 =QkA T +
  β
  M
  M−1 ∑
  τ=0
  φ(sk,τ )[φ(sk,τ+1)− φ(sk,τ )] TQkA T
  + β
  M
  M−1 ∑
  τ=0
  φ(sk,τ )[(A− 1
  N 11T )(rk,τ+1 − β
  τ ∑
  l=1
  (1− β)τ−lrk,l − (1− β) τµ0)] T
  =QkA T +
  β
  M
  M−1 ∑
  τ=0
  φ(sk,τ )[φ(sk,τ+1)− φ(sk,τ )] TQkA T
  + β
  M
  M−1 ∑
  τ=0
  φ(sk,τ )[rk,τ+1 − β τ ∑
  l=1
  (1− β)τ−lrk,l − (1− β) τµ0] T (A− 1
  N 11T )
  (22)
  where the first equality is due to A being doubly stochastic. For convenience, denote Bk = 1 M ∑M−1 τ=0 φ(sk,τ )[φ(sk,τ+1) − φ(sk,τ )] T and Ck = 1 M ∑M−1 τ=0 φ(sk,τ )[rk,τ+1 − β ∑τ l=1(1 − β)τ−lrk,l − (1− β) τµ0] T . Then, iteratively we have
  Qk+1 =(I + βBk)QkA T + βCk(A−
  1
  N 11T )
  = k ∏
  t=0
  (I + βBt)Q0(A T )k+1 + β
  k ∑
  t=0
  k ∏
  t̃>t
  (I + βBt̃)Ct(A− 1
  N 11T )Ak−t (23)
  Then, the norm of the consensus error is following
  ||Qk+1|| =|| k ∏
  t=0
  (I + βBt)Q0(A T )k+1 + β
  k ∑
  t=0
  k ∏
  t̃>t
  (I + βBt̃)Ct(A− 1
  N 11T )Ak−t||
  ≤|| k ∏
  t=0
  (I + βBt)|| · ||Q0(A T )k+1||+ β
  k ∑
  t=0
  k ∏
  t̃>t
  ||(I + βBt̃)|| · ||Ct|| · ||(A− 1
  N 11T )Ak−t||.
  (24)
  Note that sinceA is doubly stochastic, so isAT . Let (AT )k+1:,i be the i-th column of matrix (A T )k+1. From Nedic & Ozdaglar (2009), we know that
  ||Q0(A T )k+1:,i || = ||Q0(A T )k+1:,i −Q0 1
  N 1||
  = || ∑
  j∈N
  ((AT )k+1j,i − 1
  N )Qj0||
  ≤ ∑
  j∈N
  |(AT )k+1j,i − 1
  N | · ||Qj0||
  ≤ N · 2 1 + η−(N−1)
  1− ηN−1 (1− ηN−1)k+1 ·max j∈N ||Qj0||
  ≤ 2N(1 + η−(N−1))(1− ηN−1)k · ||Q0||. (25)
  Hence, ||Q0A k+1|| ≤ 2N2(1 + η−(N−1))(1− ηN−1)k · ||Q0||. To bound the first term in the RHS of equation 24, we have
  || k ∏
  t=0
  (I + βBt)|| ≤ k ∏
  t=0
  ||I + βBt||
  ≤ k ∏
  t=0
  (||I||+ β||Bt||)
  ≤ k ∏
  t=0
  (1 + 2β) = (1 + 2β)k+1. (26)
  In order to make sure it converges to the neighborhood of a consensus in the limit, the step size has to satisfy γ := (1 − ηN−1) · (1 + 2β) < 1, which results in β < η N−1
  2(1−ηN−1) . Hence, for the first
  term in the RHS of equation 24, we have
  || k ∏
  t=0
  (I + βBt)|| · ||Q0A k+1|| ≤ κ1N 2γk||Q0||
  where κ1 = 2(1 + 2β)(1 + η −(N−1)).
  Furthermore, we have
  ||(A− 1
  N 11T )Ak−t|| = ||Ak−t+1 −
  1
  N 11T || ≤ 2N2(1 + η−(N−1))(1− ηN−1)k−t. (27)
  And ||Ct|| ≤ 2Nrmax, where rmax = supi,s,a r i(s, a). This is because
  ||Ck|| = || 1
  M
  M−1 ∑
  τ=0
  φ(sk,τ )[rk,τ+1 − β τ ∑
  l=1
  (1− β)τ−lrk,l − (1− β) τµ0] T ||
  ≤ 1
  M
  M−1 ∑
  τ=0
  ||φ(sk,τ )[rk,τ+1 − β τ ∑
  l=1
  (1− β)τ−lrk,l − (1− β) τµ0] T ||
  ≤ 1
  M
  M−1 ∑
  τ=0
  ||φ(sk,τ )|| · ||rk,τ+1 − β τ ∑
  l=1
  (1− β)τ−lrk,l − (1− β) τµ0||
  ≤ 1
  M
  M−1 ∑
  τ=0
  [||rk,τ+1||+ β τ ∑
  l=1
  (1− β)τ−l||rk,l||+ (1− β) τ ||µ0||]
  ≤ 1
  M
  M−1 ∑
  τ=0
  [Nrmax + β 1− (1− β)τ
  1− (1− β) Nrmax + (1− β)
  τNrmax] = 2Nrmax.
  Then for the second term of equation 24, we have
  β k ∑
  t=0
  k ∏
  t̃>t
  ||(I + βBt̃)|| · ||Ct|| · ||(A− 1
  N 11T )Ak−t||
  ≤β k ∑
  t=0
  (1 + 2β)k−t · 2Nrmax · 2N 2(1 + η−(N−1))(1− ηN−1)k−t
  =κ2β k ∑
  t=0
  γk−t = κ2N 3β
  1− γk+1
  1− γ (28)
  where κ2 = 4(1 + η −(N−1))rmax. Further, for consensus error equation 24, we have
  ||Qk+1|| ≤ κ1N 2γk||Q0||+ κ2N 3β 1− γk+1
  1− γ ≤κ1N
  2γk||Q0||+ κ ′ 2N 3β (29)
  where κ′2 = κ2 1−γ .
  The corresponding average parameter under the policy πθ will converge to the solution to the following equation w∗θ = A −1 θ bθ, where Aθ = Es∼dθ(s)[φ(s)(φ(s ′) − φ(s))T ], bθ = E(s,a)∼dθ(s,a)[(r̄(s, a)− J(θ))φ(s)] and r̄(s, a) = 1 N ∑ i∈N r i(s, a).
  Now consider ||w̄k − w ∗||. Recall the from the average parameter equation equation 20 and the corresponding ODE is
  ẇθ = Aθwθ + bθ. (30)
  For the difference between average dynamics and the optimal value, we have the following lemma.
  Lemma 7. For β ≤ min{ λA128 , 4 λA } and M ≥ ( 1 λA + β) 6144[1+(κ−1)ρ](1−ρ)λA , we have
  E[||w̄K − w ∗ θ || 2 2] ≤ (1− λA 8 β)K ||w̄0 − w ∗ θ || 2 2 + ( 1 λA + β)
  1536(4R2w + r 2 max)[1 + (κ− 1)ρ]
  (1− ρ)λAM .
  (31)
  Proof. The proof follows from verifying the Assumption 3 of Xu et al. (2020), then we can apply the results from Theorem 4 of Xu et al. (2020).
  1. For item 1 in the assumption, it’s easy to check that ||Aθ|| ≤ CA = 4 by Assumption 4 and bθ ≤ Cb = 2rmax.
  2. For item 2, it holds because of Lemma 3.
  3. For item 3, it holds because of Lemma 1.
  And we recall that the bound on ||w∗θ || is Rw = 4rmax λA . Hence, by Theorem 4 of Xu et al. (2020), β ≤ min{ λA 8C2
  A
  , 4 λA } and M ≥ ( 2 λA + 2β) 192C2A[1+(κ−1)ρ] (1−ρ)λA , equation 31 holds.
  A.4 PROOF OF THEOREM 2
  As a result from Lemma 4 and Lemma 7, we provide the following proof for Theorem 2.
  Proof. Therefore, by equation 17 and equation 31, we have
  E[
  N ∑
  i=1
  ||wiK − w ∗ θ || 2]
  ≤ 2E[ N ∑
  i=1
  ||wiK − w̄K || 2] + 2E[
  N ∑
  i=1
  ||w̄K − w ∗ θ || 2]
  ≤ 2||QK || 2 + 2NE[||w̄K − w ∗ θ || 2]
  ≤ 2(κ1N 2γK ||Q0||+ κ ′ 2N 3β)2 + 2N(1− λA 8 β)K ||w̄0 − w ∗ θ || 2 2
  + 2N( 2
  λA + 2β)
  192(C2AR 2 w + C 2 b )[1 + (κ− 1)ρ]
  (1− ρ)λAM
  ≤ κ′1N 4γ2K + κ′′2N 6β2 + κ3N 5γKβ + 2N(1− λA 8 β)K ||w̄0 − w ∗ θ || 2 2 + κ4 M N
  where κ′1 = 2κ 2 1||Q0|| 2, κ”2 = 2κ ′2 2 , κ3 = 4κ1κ ′ 2||Q0|| and κ4 = ( 1 λA + β) 3072(4R2w+r 2 max)[1+(κ−1)ρ]
  (1−ρ)λA .
  A.5 PROOF OF THEOREM 3
  We use w∗t to denote the optimal value function parameter under policy θt at time t and wt = [(w1t ) T , · · · , (wNt ) T ]T ∈ RN×K . Recall the δ̃it,l generated by Line 18 of algorithm 2. It is the agent i-th estimate of the global TD-error from sample l at time t after consensus. Let vit(wt) = 1 B ∑B−1 l=0 δ̃ i t,l ·ψ i t,l and vt(wt) = [(v 1 t (wt)) T , · · · , (vNt (wt)) T ]T , hit(w ∗ t ) = 1 B ∑B−1 l=0 δt,l(w ∗ t ) ·ψ i t,l
  and ht(w ∗ t ) = [(h 1 t (w ∗ t )) T , · · · , (hNt (w ∗ t )) T ]T , Aw(s, a) = Es′∼P (·|s,a),r∼dr(s,a)[δw(s, a, s ′)|s, a] and gi(w, θ) = E[Aw(s, a)ψθi(s, a i)], where dr(s, a) is the reward distribution of state-action pair (s, a). By the Taylor expansion and the Lipschitz property from Assumption 6, we have
  J(θt+1) ≥ J(θt) + 〈∇θJ(θt), θt+1 − θt〉 − LJ 2 ||θt+1 − θt|| 2
  = J(θt) + α〈∇θJ(θt), vt(wt)−∇θJ(θt) +∇θJ(θt)〉 − LJα
  2
  2 ||vt(wt)||
  2
  = J(θt) + α||∇θJ(θt)|| 2 + α〈∇θJ(θt), vt(wt)−∇θJ(θt)〉 −
  LJα 2
  2 ||vt(wt)
  −∇θJ(θt) +∇θJ(θt)|| 2
  ≥ J(θt) + ( 1
  2 α− LJα
  2)||∇θJ(θt)|| 2 − (
  1 2 α+ LJα 2)||vt(wt)−∇θJ(θt)|| 2
  where the last inequality is because
  〈∇θJ(θt), vt(wt)−∇θJ(θt)〉 ≥ − 1
  2 ||∇θJ(θt)||
  2 − 1
  2 ||vt(wt)−∇θJ(θ)||
  2,
  and
  ||vt(wt)−∇θJ(θt) +∇θJ(θt)|| 2 ≤ 2||vt(wt)−∇θJ(θt)|| 2 + 2||∇θJ(θt)|| 2. (32)
  Taking expectations on both sides conditioned on the filtration Ft and rearranging the terms, we have
  ( 1
  2 α− LJα
  2)E[||∇θJ(θt)|| 2|Ft] ≤ E[J(θt+1)|Ft]− J(θt)
  + ( 1
  2 α+ LJα
  2)E[||vt(wt)−∇θJ(θt)|| 2|Ft]. (33)
  Then, we establish upper bound on the third term of the RHS. By definition, we have
  ||vt(wt)−∇θJ(θt)|| 2
  = ||vt(wt)− vt(w ∗ t ) + vt(w ∗ t )− ht(w ∗ t ) + ht(w ∗ t )− g(w ∗ t , θt) + g(w ∗ t , θt)−∇θJ(θt)|| 2 ≤ 6||vt(wt)− vt(w ∗ t )|| 2 + 6||vt(w ∗ t )− ht(w ∗ t )|| 2 + 6||ht(w ∗ t )− g(w ∗ t , θt)|| 2
  + 6||g(w∗t , θt)−∇θJ(θt)|| 2. (34)
  We note that ||vt(wt)− vt(w ∗ t )|| 2 = ∑ i∈N ||v i t(wt)− v i t(w ∗ t )|| 2 and the other three terms in equation 34 can also be similarly decomposed. For the first term in the RHS of equation 34, we have
  ||vit(wt)− v i t(w ∗ t )|| 2
  = || 1
  B
  B−1 ∑
  l=0
  ∆it,l(wt) · ψ i t,l −
  1
  B
  B−1 ∑
  l=0
  ∆it,l(w ∗ t ) · ψ i t,l|| 2
  = || 1
  B
  B−1 ∑
  l=0
  [∆it,l(wt)−∆ i t,l(w ∗ t )] · ψ i t,l|| 2
  = || 1
  B
  B−1 ∑
  l=0
  [Atgossip ]i(wt − w ∗ t 1 T )T [φ(st,l+1)− φ(st,l)] · ψ i t,l|| 2
  ≤ max l∈{0,··· ,B−1}
  ||[Atgossip ]i(wt − w ∗ t 1 T )T [φ(st,l+1)− φ(st,l)] · ψ i t,l|| 2
  ≤ max l∈{0,··· ,B−1}
  ||[Atgossip ]i|| 2||[φ(st,l+1)− φ(st,l)]|| 2||wt − w ∗ t 1 T ||2 · ||ψit,l|| 2
  ≤ 4 · ||wt − w ∗ t ⊗ 1||
  2 = 4 N ∑
  i=1
  ||wit − w ∗ t || 2 (35)
  where the third equality is from
  ∆it,l(wt)−∆ i t,l(w ∗ t )
  = [Atgossip ]iδt,l(wt)− [A tgossip ]iδt,l(w ∗ t ) = [Atgossip ]i[δt,l(wt)− δt,l(w ∗ t )]
  = [Atgossip ]i
  
   
  φT (st,l+1)(w 1 t − w ∗ t )− φ T (st,l)(w 1 t − w ∗ t )
  ...
  φT (st,l+1)(w N t − w ∗ t )− φ T (st,l)(w N t − w ∗ t )
  
   
  = [Atgossip ]i(wt − w ∗ t 1 T )T [φ(st,l+1)− φ(st,l)].
  For the second term in the RHS of equation 34, we have
  ||vit(w ∗ t )− h i t(w ∗ t )|| 2
  = || 1
  B
  B−1 ∑
  l=0
  ∆it,l(w ∗ t ) · ψ i t,l −
  1
  B
  B−1 ∑
  l=0
  δt,l(w ∗ t ) · ψ i t,l|| 2
  = || 1
  B
  B−1 ∑
  l=0
  [∆it,l(w ∗ t )− δt,l(w ∗ t )] · ψ i t,l|| 2
  = || 1
  B
  B−1 ∑
  l=0
  (
  [Atgossip ]i − 1 N 1T ) ~δt,l(w ∗ t ) · ψ i t,l|| 2
  ≤ max l∈{0,··· ,B−1} ||
  (
  [Atgossip ]i − 1 N 1T ) ~δt,l(w ∗ t ) · ψ i t,l|| 2
  ≤ max l∈{0,··· ,B−1}
  ||[Atgossip ]i − 1
  N 1T ||2 · ||~δt,l(w ∗ t )|| 2 · ||ψit,l|| 2
  ≤ max l∈{0,··· ,B−1}
  N(2 1 + η−(N−1)
  1− ηN−1 (1− ηN−1)tgossip+1)2 · ||~δt,l(w ∗ t )|| 2
  ≤ 16N((1 + η−(N−1))(1− ηN−1)tgossip)2(rmax +Rw) 2 = κ3N(1− η N−1)2tgossip (36)
  where κ3 = 16(1 + η −(N−1))2(rmax +Rw) 2. We note that the second equality is because
  ∆it,l(w ∗ t )− δt,l(w ∗ t )
  = [Atgossip ]iδt,l − 1
  N 1T δt,l
  =
  (
  [Atgossip ]i − 1 N 1T ) δt,l.
  For the last inequality, we note that δt,l(w ∗) is bounded because rewards and feature vectors are bounded, µi is bounded for constant step size and w∗t is bounded from the critic step. That is, for j ∈ N entry in ~δt,l(w∗) by definition,
  δjt,l(w ∗) = rjt,l − µ j t,l + [φ(st,l+1)− φ(st,l)] Tw∗t .
  Hence, its 2-norm bound is
  ||δt,l(w ∗)|| = ||rjt,l − µ j t,l + [φ(st,l+1)− φ(st,l)] Tw∗t ||
  ≤ ||rjt,l||+ ||µ j t,l||+ ||φ(st,l+1)− φ(st,l)|| · ||w ∗ t ||
  ≤ rmax + rmax + [||φ(st,l+1)||+ ||φ(st,l)||] ·Rw ≤ 2rmax + 2Rw. (37)
  For the last term in equation 34, we have
  ||g(w∗t , θt)−∇θJ(θt)|| 2
  = ||Edθt (s,a)[Aw ∗ t (s, a)ψθt(s, a)]− Edθt (s,a)[Aθt(s, a)ψθt(s, a)]||
  2
  = ||Edθt (s,a)[(Aw∗t (s, a)−Aθt(s, a))ψθt(s, a)]|| 2
  ≤ (Edθt (s,a)[||(Aw ∗ t (s, a)−Aθt(s, a))ψθt(s, a)||])
  2
  ≤ (Edθt (s,a)[||Aw ∗ t (s, a)−Aθt(s, a)|| · ||ψθt(s, a)||])
  2
  ≤ (Edθt (s,a)[|Aw ∗ t (s, a)−Aθt(s, a)|])
  2
  = (Edθt (s,a)[|E[Vw ∗ t (s′)|s, a]− Vw∗t (s)− E[Vθ∗t (s ′)|s, a] + Vθ∗t (s)|]) 2 ≤ (Edθt (s,a)[|E[Vw ∗ t (s′)− Vθ∗t (s ′)|s, a]|+ |Vw∗t (s)− Vθ∗t (s)|]) 2 ≤ (Edθt (s,a)[E[|Vw ∗ t (s′)− Vθ∗t (s ′)||s, a] + |Vw∗t (s)− Vθ∗t (s)|]) 2 = (E[|Vw∗t (s)− Vθ∗t (s)|] + E[|Vw∗t (s)− Vθ∗t (s)|]) 2 ≤ 4(E[|Vw∗t (s)− Vθ∗t (s)|]) 2 ≤ 4E[|Vw∗t (s)− Vθ∗t (s)| 2] ≤ 4ξcriticapprox. (38)
  For each i ∈ N , we have
  ||hit(w ∗ t )− g i(w∗t , θ i t)|| 2
  = 〈 1
  B
  B−1 ∑
  l1=0
  δt,l1(w ∗ t )ψθit − Es,a[Aw ∗ t (s, a)ψiθit
  (s, ai)], 1
  B
  B−1 ∑
  l2=0
  δt,l2(w ∗ t )ψθit − Es,a[Aw ∗ t (s, a)ψiθit (s, ai)]〉
  = 1
  B2
  B−1 ∑
  l1=0
  B−1 ∑
  l2=0
  〈δt,l1(w ∗ t )ψθit − Es,a[Aw ∗ t (s, a)ψiθit (s, ai)], δt,l2(w ∗ t )ψθit − Es,a[Aw ∗ t (s, a)ψiθit (s, ai)]〉
  = 1
  B2
  B−1 ∑
  l=0
  ||δt,l(w ∗ t )ψθit − Es,a[Aw ∗ t (s, a)ψiθit (s, ai)]||2
  + 1
  B2
  ∑
  l1 6=l2
  〈δt,l1(w ∗ t )ψθit − Es,a[Aw ∗ t (s, a)ψiθit (s, ai)], δt,l2(w ∗ t )ψθit − Es,a[Aw ∗ t (s, a)ψit,l2(s, a i)]〉.
  Taking expectation over the filtration Ft, we have E[||hit(w ∗ t )− g i(w∗t , θ i t)|| 2|Ft]
  = 1
  B2
  B−1 ∑
  l=0
  E
  [
  ||δt,l(w ∗ t )ψθit − Es,a[Aw ∗ t (s, a)ψiθit
  (s, ai)]||2|Ft ]
  + 1
  B2
  ∑
  l1 6=l2
  E
  [
  〈δt,l1(w ∗ t )ψθit − Es,a[Aw ∗ t (s, a)ψiθit (s, ai)], δt,l2(w ∗ t )ψθit − Es,a[Aw ∗ t (s, a)ψiθit
  (s, ai)]〉|Ft ]
  ≤ 16
  B (rmax +Rw)
  2
  + 1
  B2
  ∑
  l1 6=l2
  E
  [
  〈δt,l1(w ∗ t )ψθit − Es,a[Aw ∗ t (s, a)ψiθit (s, ai)], δt,l2(w ∗ t )ψθit − Es,a[Aw ∗ t (s, a)ψiθit
  (s, ai)]〉|Ft ]
  where the inequality follows from triangle inequality and the facts that |δt,l1(w ∗ t )ψθit | ≤ 2rmax + 2Rw and |Es,a[Aw∗t (s, a)ψ i θit (s, ai)]| = |E[δt,l1(w ∗ t )ψθit ]| ≤ 2rmax + 2Rw. WLOG, for the following term, we suppose l1 < l2. Then we have
  E
  [
  〈δt,l1(w ∗ t )ψθit − Es,a[Aw ∗ t (s, a)ψiθit (s, ai)], δt,l2(w ∗ t )ψθit − Es,a[Aw ∗ t (s, a)ψiθit
  (s, ai)]〉|Ft ]
  =E [ E [
  〈δt,l1(w ∗ t )ψθit − Es,a[Aw ∗ t (s, a)ψiθi(s, a i)], δt,l2(w ∗ t )ψθit − Es,a[Aw ∗ t (s, a)ψiθit (s, ai)]〉|Ft,l1
  ] |Ft ]
  =E [
  〈δt,l1(w ∗ t )ψθit − Es,a[Aw ∗ t (s, a)ψiθi(s, a
  i)],E [
  δt,l2(w ∗ t )ψθit − Es,a[Aw ∗ t (s, a)ψiθit (s, ai)]|Ft,l1
  ] 〉|Ft ]
  =E [
  〈δt,l1(w ∗ t )ψθit − Es,a[Aw ∗ t (s, a)ψiθi(s, a i)],E[δt,l2(w ∗ t )ψθit |Ft,l1 ]− Es,a[Aw ∗ t (s, a)ψiθit
  (s, ai)]〉|Ft ]
  =E [
  〈δt,l1(w ∗ t )ψθit − Es,a[Aw ∗ t (s, a)ψiθi(s, a i)],E[Aw∗t (st,l2 , at,l2)ψθit |Ft,l1 ]− Es,a[Aw ∗ t (s, a)ψiθit
  (s, ai)]〉|Ft ]
  ≤E [
  ||δt,l1(w ∗ t )ψθit − Es,a[Aw ∗ t (s, a)ψiθi(s, a i)]|| · ||E[Aw∗t (st,l2 , at,l2)ψθit |Ft,l1 ]− Es,a[Aw ∗ t (s, a)ψiθit
  (s, ai)]|||Ft ]
  ≤2(2rmax + 2Rw)E [
  ||E[Aw∗t (st,l2 , at,l2)ψθit |Ft,l1 ]− Es,a[Aw ∗ t (s, a)ψiθit
  (s, ai)]|||Ft ]
  ≤16(rmax +Rw) 2κρl2−l1
  where the last inequality follows from
  ||E[Aw∗t (st,l2 , at,l2)ψθit |Ft,l1 ]− Es,a[Aw ∗ t (s, a)ψiθit (s, ai)]||
  =|| ∑
  (st,l2 ,at,l2 )
  Aw∗t (st,l2 , at,l2)ψθit(st,l2 , at,l2)P (st,l2 , at,l2 |Ft,l1)− ∑
  (s,a)
  Aw∗t (s, a)ψθit(s, a)νθt(s, a)||
  ≤ ∑
  s,a
  ||Aw∗t (s, a)ψ i θit (s, ai)|| · |P l2−l1(s, a|Ft,l2)− νθt(s, a)|
  ≤2(2rmax + 2Rw) · ||P l2−l1(s, a|Ft,l2)− ν(s, a)||TV ≤4(rmax +Rw)κρ l2−l1 .
  Then, we have
  E[||hit(w ∗ t )− g i(w∗t , θ i t)|| 2|Ft]
  ≤ 1
  B2 [16B(rmax +Rw)
  2 + 16(rmax +Rw) 2κ ∑
  l2 6=l1
  ρl2−l1 ]
  ≤ 1
  B2 [16B(rmax +Rw)
  2 + 32(rmax +Rw)
  2κρB
  1− ρ ]
  ≤ 16(rmax +Rw)
  2[1 + (2κ− 1)ρ]
  B(1− ρ) . (39)
  Then, we have
  E[||vt(wt)−∇θJ(θt)|| 2] ≤24N
  N ∑
  i=1
  ||wit − w ∗ t || 2 + 6κ3N 2(1− ηN−1)2tgossip
  + 24ξcriticapprox + 96(rmax +Rw)
  2[1 + (2κ− 1)ρ]
  B(1− ρ) N (40)
  As a result, substituting equation equation 40 into equation 33 and taking expectation over Ft on both sides, we have
  ( 1
  2 α− LJα
  2)E[||∇θJ(θt)|| 2]
  ≤ E[J(θt+1)]− E[J(θt)] + ( 1
  2 α+ LJα
  2)
  (
  24N N ∑
  i=1
  ||wit − w ∗ t || 2
  +6κ3N 2(1− ηN−1)2tgossip + 24ξcriticapprox + 96
  (rmax +Rw) 2[1 + (2κ− 1)ρ]
  B(1− ρ) N
  )
  . (41)
  By considering step size α = 14LJ , and dividing both sides of previous equation by 1 16LJ , we have
  E[||∇θJ(θt)|| 2] ≤16LJ (E[J(θt+1)]− E[J(θt)]) + 72N
  N ∑
  i=1
  ||wit − w ∗ t || 2
  + 18κ3N 2(1− ηN−1)2tgossip + 72ξcriticapprox + 288N
  (rmax +Rw) 2[1 + (2κ− 1)ρ]
  B(1− ρ) .
  (42)
  Let T̂ be a random variable that takes value uniformly among {1, · · · , T}. Taking summation over t = {1, · · · , T} and dividing by T , we have
  E[||∇θJ(θT̂ )|| 2] =
  1
  T
  T ∑
  t=1
  E[||∇θJ(θt)|| 2]
  ≤ 16LJ (E[J(θT )]− E[J(θ0)])
  T + 72N
  ∑T t=1 ∑N i=1 ||w i t − w ∗ t || 2
  T
  + 18κ3N 2(1− ηN−1)2tgossip + 72ξcriticapprox + 288
  (rmax +Rw) 2[1 + (2κ− 1)ρ]
  B(1− ρ) N
  ≤ 16LJE[J(θT )]
  T + 72N
  ∑N i=1 ||w i t − w ∗ t || 2
  T
  + 18κ3N 2(1− ηN−1)2tgossip + 72ξcriticapprox + 288
  (rmax +Rw) 2[1 + (2κ− 1)ρ]
  B(1− ρ) N.