Finite-Time Analysis of Decentralized Single-Timescale Actor-Critic
Authors: qijun luo
Xiao Li
Venue: Accepted by TMLR ()

Abstract: Decentralized Actor-Critic (AC) algorithms have been widely utilized for multi-agent reinforcement learning (MARL) and have achieved remarkable success. Apart from its empirical success, the theoretical convergence property of decentralized AC algorithms is largely unexplored. Most of the existing finite-time convergence results are derived based on either double-loop update or two-timescale step sizes rule, and this is the case even for centralized AC algorithm under a single-agent setting. In practice, the *single-timescale* update is widely utilized, where actor and critic are updated in an alternating manner with step sizes being of the same order. In this work, we study a decentralized *single-timescale* AC algorithm. Theoretically, using linear approximation for value and reward estimation, we show that the algorithm has sample complexity of $\tilde{\mathcal{O}}(\varepsilon^{-2})$ under Markovian sampling, which matches the optimal complexity with a double-loop implementation (here, $\tilde{\mathcal{O}}$ hides a logarithmic term).  When we reduce to the single-agent setting, our result yields new sample complexity for centralized AC using a single-timescale update scheme. The central to establishing our complexity results is *the hidden smoothness of the optimal critic variable* we revealed. We also provide a local action privacy-preserving version of our algorithm and its analysis. Finally, we conduct experiments to show the superiority of our algorithm over the existing decentralized AC algorithms.

Published in Transactions on Machine Learning Research (01/2023)
Minite-iime Analysis of Decentralized Single-Timescall Actor-Critic
Qijun Luo
gijunluo@line Glink. cuhk. edu.cn
School of Science and Engineering Shenzhen Research Institute of Big Data (SRIBD) The Chinese University of Hong Kong, Shenzhen Shenzhen, China
Xiao Li
liziao &cuhk edu.cm
School of Data Science
Shenahen Institute of Artificial Intelligence and Robotics for Society (AIRS) The Chinese University of Hong Kong, Shenzhen Shenzhen, Chinaa
Reviewed on OpenReview: https: // openreview. net/ forun? id= KQRUOD8:
Abstract
Decentralized Actor-Critic (AC) algorithms have been widely utilized for multi-agent rein- forcement learning (MARL) and have achieved remarkable success. Apart from its empirical success, the theoretical convergence property of decentralized AC algorithms is largely un- explored. Most of the existing finite-time convergence results are derived based on either double-loop update or two-timescale step sizes rule, and this is the case even for cantralized AC algorithm under a single-agent setting. practice, the single-timescat update widely utilized, where actor and critic are updated in an altornating manner with stop sizes being of the same order. In this work, we study a decentralized single-limescale AC algorithm. Theoretically, using linear approximation for value and reward estimation, show that the algorithm has sample complexity of Ō(E=²) under Markovian sampling, which matches the optimal complexity with a double-loop implementation (here, Ô hides a logarithmic term). When we reduce to the single-agent setting, our result yields new sample complexity for centralized AC using a single-timesoo update scheme. The central to establishing our complexity results the hidden smoolhness of the optimal crilic variable we revealed. version of our algorithm and its analysis.
We also provide local action Finally, conduct experiments to show the superiority of our algorithm over the existing decentralized AC algorithms.
1 Introduction
Multi-agent reinforcement learning (MARL) (Littman, 1994; Vinyals et al., 2019) has been successful various models of multi-agent systems, such as robotics (Lillicrap al., 2015), autonomous driving (Yu et al., 2019), Go (Silver et al., 2017), etc. MARL has been extensively explored in the past decades; see, e.g., (Lowe et al., 2017; Omidshafici et al., 2017; Zhang et al., 2021; Son et al., 2019; Espeholt et al., 2018; Rashid et al., 2018). These works either focus the setting where central controller is available, assuming common reward function for all agents. Among the many cooperative MARL settings, the work (Zhang et al., 2018) proposed the fully raleeed MARL with networked agents. In this setting, each agent maintains a private heterogeneous reward function, and agents can only access bocal/neighhoring information through communicating with its neighboring agents on the network. Then, the objective of all agents is jointly maximize the average long-term reward through interacting with environment modeled by multi-agent Markov decision process (MDP). They proposed the decentralized Actor- ChiorCCritic (AC) algorithm to solve this

---

Published in Transactions on Machine Learning Research (01/2023)
MARL problem, and showed its impressive performance. However, the theoretical convergence properties of such class of decentralized AC algorithms are largely unexplored; see (Zhang et al., 2021) for a comprehensive survey, In this work, our goal is to establish the finite-time convergence results under this fully decentralized MARL sctting. We first review some recent progresses on this line of research below.
Related works and motivations. The first fully decentralized AC algorithm with provable convergence guarantee was proposed by (Zhang al., 2018), and they achieved asymptotic convergence results under two-timescale step sizes, which requires actor's step sizes to diminish in a faster scale than the critic's step sizes. The sample complexities of decentralized AC were established recently. In particular, (Chen et al., 2022) and (Hairi et al., 2022) independently proposed two communication efficient decentralized AC algorithms with optimal sample complexity of O log(s-1) under Markovian sampling scheme. Nevertheless, their analysis are based on double-loop implementation, where each policy optimization step follows a nearly accurate critic optimization step (a.k.a. policy evaluation), i.e., solving the critic optimization subproblem to e-accuracy. Such a double-loop scheme requires careful tuning of two additional hyper- paree-aaaaetoss, which are the batch size and inner loop size. In particular, the batch size and inner loop size need to be of order O(E-t) and (llo(E==)) in order to achieve their sample complexity results, respectively. In practice, single-loop algorithmic framework is often utilized, where one updates the actor and critic in an alternating manner by performing any constant algorithmic iterations for both subproblems; see, e.g., (Schulman et al., 2017: Lowe et al., 2017; Lin et al., 2019; Zhang et al., 2020). The work (Zeng et al., 2022) proposed a new decentralized AC algorithm based on such a single-loop alternative update. However, they have to adopt two-timescale step sizes rule to ensure convergence, which requires actor's step sizes to diminish in a faster scale than the critic's step sizes. Due to the separation of the step sizes, the critic optimization subproblem is solved exactly when the number of iterations tends to co. Such restriction on the step size will slow down the convergence speed of the algorithm. As a consequence, they only obtain sub-optimal sample complexity of O(s-å), 8). In practice, most algorithms are implemented with tingleetimescale step sizes rule, where the step sizes for the actor's and critic's updates are of the same order. Though there are some theoretical achievements for single-timescal update in other areas such as TDC (Wang et al., 2021) and bi-level optimization (Chen et al., 2021a), similar theoretical understanding under AC setting is largely unexplored.
Indeed, even when reducing to single-agent sctting, the convergence property of singlo-timescale AC algorithm is not well established. The works (Fu et al., 2021; Guo et al., 2021) established the finite-time convergence result under special single-timescale implementation, where they attained the sample complexity of Their analysis is based on an algorithm where the critic optimization step is formulated as a least-square temporal difference (LSTD) at each iteration, which requires to sample the transition tuples for Ó(E-1) times to form the data matrix in the LSTD subproblem. Then, they solve the LSTD subproblem in a closed-form fashion by inverting a matrix of large size. Later, (Chen et al., 2021a) obtained the same sample complexity using TD(0) update for critic variables under i.i.d. sampling. Their analysis highly relies on the assumption that the Jacobian of the stationary distribution is Lipschitz continuous, which is not justified in their work.
The above obscrvations motivate us to ask the following question:
Can we eslablish fonile-lmme converyence result for decentralized AC algoritlum with single-timesoale slep sizes rule?"
Main contributions. By answering this question positively, we have the following contributions:
We design a decentralized AC algorithm, which employs a single-timescale step sizes rule and adopts Markovian sampling scheme. The proposed algorithm allows communication between agents for every Ke iterations with K2 being any integer lies in [1, ((==a()r å ]], rather than communccating at each iteration as adopted by previous single-loop decentralized AC algorithms (Zeng et al., 2022; Zhang et al., 2018).
Using linear approximation for value and reward estimation, we establish the fimile-time convergence result for the proposed algorithm under standard assumptions. In particular, we show that the algorithm has a sample complexity of Ö(E-2), which matches the optimal complexity up to a
I As convention (Fu et al., 2021), when we use "single-timescalee" it means we utilize a single-loop algorithmic framework with single-timescale step sizes rule.
2

---

Published in Transactions on Machine Learning Research (01/2023)
logarithmic term. In addition, we show that the logarithmic term hidden in the "Ô" can be removed under the i.i.d. sampling scheme. These convergence results are valid for all the above mentioned choices for Ke.
To preserve privacy of local actions, propose variant of our algorithm which utilizes noisy local rewards for estimating global rewards. We show that such an algorithm will maintain the optinal sample complexity at the expense of communicating at each iteration.
Our key technical result is to reveal the hidden smoothness of the optimal critic variable, so that we can derive a sufficient descent on the averaged critic's optimal gap under the single-limescale update. Consequently, we can resort to the classic convergence analysis for alternating optimization algorithms to establish the approximate ascent property of the overall optimization process, which leads to the final sample complexity results. We also designed Lyapunov function to analyze the descent of the objective function with a single-timescale update under the decentralized setting.
When we reduce to the non-decentralized case, i.e., the single-agent setting, our results yield new sample update scheme.
complexity guarantees for the classic centralized AC algorithm using a
Discussion on a concurrent work. We note that there is a concurrent work (Olshevsky & Gharesifard, 2023) which also analyzes the single-timescale AC algorithu and achieves similar complexity results. Their analysis is based provide useful insights for the AC algorithm from different perspectives. (Olshevsky & Gharesifard, 2023) shows that the coupled expression on the errors of actor and critic can be fit into a non-linear small gain theorem framework, which bounds the actor's error by desired order. Our analysis reveals the hidden smoothness of the optimal critic variable so that approximate descent on the critic's objective can be achieved. In addition, (Olshovsky & Gharesifard, 2023) considers the single-agent sctting while our analysis deals with the more general decentralized setting. Moreover, (Olshevsky & Gharesifard, 2023) analyzes the i.i.d. sampling scheme where the single agent is assumed to have access to the transition tuples from the stationary distribution and the discounted state-visitation distribution. By contrast, our setting considers the practical Markovian sampling scheme, where the transition tuples are from the trajectory generated during the update of the agents.
the small gain theorem, which is different from ours. These two analysis frameworks
2 Preliminary
In this section, we introduce the problem formulation and the policy gradient thcorem, which serves as the preliminary for the analysed decentralzed AC algorithmn
Suppose there are multiple agents aiming to independently optimize a common global objective, and each agent can communicate with its neighbors through a network. To model the topology, we define the graph as G = EN, where A is the set of nodes with |W| = N and & is the set of edges with |g| = E. In the graph, each node represents an agent, and each edge represents a communication link. The interaction between agents follows the networked multi-agent MDP.
2.1 Markov decision process
A networked multi-agent MDP is defined by a tuple (G,S, (A P, (r') (e(M):)) 7). G denotes the communi- cation topology (the graph), S the finite state space observed by all agents, A' represents the finite action space of agent i. Let A : A .... x N denote the joint action space and P(s' sss s,a): x Ax - [o. 1] denote the transition probability from any state E S to any state s' E' S for any joint action A. r' S x A + R is the local reward function that determines the reward received by agent given transition (s, jo, 1] is the discount factor.
For simplicity, we will use a:= [at ................... J to denote the joint action, and 0 E Ndo to denote concalenation of all actor's joint parameters of all actors, with 0² e Rdd Here, without loss of generality, we assume that every agent has the same number of parameters for notation brevity. The MDP goes as follows: For a given state s, each agent make its decision a' based on its policy at ~ Tgs (-Is). The state transits to the next state s' based on the joint action of all the agents: s' P(I)s, a). Then, each agent will receive its own reward
[a+,
3

---

Published in Transactions on Machine Learning Research (01/2023)
as) For the notation brevity, we assume that the reward function mapping is deterministic and does not depend on the next state without loss of generality. The stationary distribution induced by the policy and the transition kernel is denoted by Mag (s).
Our objective is to find a set of policies that maximize the accumulated discounted mean reward received by agents
Σ M (3k, ax) 0
0" = arg max J(0) = E
(1)
Here, k represents the time step. F(8k; 0x) = N Ei=1 (sk, ag) the mean reward among agents at time step k. The randomness of the expectation comes from the initial state distribution po(s), the transition kernel P, and the stochastic policy Ty: (-1s).
N
2.2 Policy gradient Theorem
Under the discounted reward setting, the global state-value function, action-value function, and advantage function for policy set 0, state and action a, are defined as
(s) = E
F(ss ax)]so
(2)
2no (s) = E
k r((k ax) 0,00
(3, := (xo Vxo
To maximize the objective function defined in (1); the policy gradient (Sutton et al., 2000) be computed follow
1 T ANo ()) (s)
V (0) = E Egndnn am-i
where dzp (s) = (1 7 8) is the discounted state visitation distribution under policy To, and Vn (8, = log TH (s, a) is the score function.
Following the derivation of (Zhang al., 2018), the policy gradient for each agent under discounted reward setting can be expressed
Ano (s, a) (s.
(0) Egndan anis
(3)
i
3 Algorithms
3.1 Decentralized single-timescale Actor-Critic
We introduce the decentralized single-timescale AC algorithm; see Algorithm 1. In the remaining parts of this section, we will explain the updates in the algorithm in details.
In fully-decentraalized MARL, each agent can only observe its local reward and action, while trying to maximizo the global reward (mean reward) defined in (1). The decentralized AC algorithm solves the problem by updating actor and critic variables alternatively on an online trajectory. Specifically, we have N pairs of actor and critic. In order to maximize J(0), each critic tries to estimate the global state-value function Vr, (s) defined in (2). Then, each actor updates its policy parameter based approximated policy gradient. We provide more details about the algorithm.
Critics' update. We will use of E d to denote the is critic's parameter and w = N EM wt to represent the averaged parameter of critic. Fach critic approximates the global value function Vn (8) (s).
4

---

Published in Transactions on Machine Learning Research (01/2023)
Algorithm 1: Decentralized singlo-timescale AC (reward estimator version)
Initialize: Actor parameter 0b, critic parameter we, reward estimator parameter Ao, initial state 8o-
2: for == 0,... , do
Option 1: Li.d. sampling:
4: ~ No, (6),
To, (118k), 8k+1 P
Option 2: Markovian sampling:
6:
No. (-Isk), S441 Sk41 P(-(sk,a ax).
8:
Periodical consensus: Compute Wi and X by (4) and (7).
9:
10:
for i = 0,... ,N in parallel do
11:
Reward estimator update: update a by (8).
12: Critic update: Update wf41 by (5).
13: Actor update: Update 0 by (6).
14: end for
15:
end for
The critic's approximation error can be categorized into two parts, namely, the consensus error N Σi || @||, which measures how close the critics' parameters are; and the approximation error || w (0)ll, which measures the approximation quality of averaged critic.
In order for critics to reach consensus, each critic exchanges its parameters with neighbors and perform the following update
Ex wi if k mod K2
at
(4)
otherwise.
Here, Ke denotes the consensus frequency. The communication matrix W E RR** is usually determined artificially in practice and can be sparse, which means that the number of neighbors for each agent is much fewer than the total number of agents. Thus, the cost for each consensus step is usually much lower than full synchronization over the network. The detailed requirements of matrix W will be discussed in Assumption 5.
To reduce the approximation error, we will perform the local TD(0) update (Tsitsiklis & Van Roy, 1997)
w n_ (0t + (Er,
(5)
where = (s, a, s') represents transition tuple, ('(E.w)
is the update direction, ("(,,w) := (s) + (s') (s) is the local temporal difference error (TD-crror). Sh is the step size for critic at iteration k. HR, projects the parameter into ball of radius of R containing the optimal solution, which will be explained when discussing Assumptions 1 and 2.
Actors' update. We will use stochastic gradient ascent to update the policy's parameter, which is calculated based on policy gradient theorem in (3). The advantage function An, (s, a) can be estimated by
((g,0) = a) + (s') (s),
with a sampled from (-Is). However, to preserve the privacy of each agents, the local reward cannot be shared to other agents under the fully decentralized setting. Thus, the averaged reward F(Sk, ag) is not directly attainable. To this end, we adopt the strategy proposed in (Zhang et al., 2018) to approximate the averaged reward. In particular, each agent i will have local reward estimator with parameter A e Rd, which estimates the global averaged reward as F(S ax) x (8x, oz).
Thus, the update of the ish actor given by
o,t1 0f + cau NetzlWnn (sk, at))
(6)
5

---

Published in Transactions on Machine Learning Research (01/2023)
Algorithm 2: Decentralized singlo-timescale AC (noisy reward version)
1: Initialize: Actor parameter 0b, critic parameter we, initial state 8g-
2: for == 0, 0,... K do
Option 1: Li.d. sampling:
4: ~ No, (6),
To, (-18k), 8k+1 P(le)
Option 2: Markovian sampling:
6:
No. (-Isk), S441 Sk41 P(-lsk,au)
8:
Periodical consensus: Compute We by (4).
9:
10:
for i 0,.., N in parallel do
11:
Global reward estimation: estimate Fe(SE, ax) by (9).
12:
Critic update: Update wf41 by (5).
13:
Actor update: Update 0/41 by (10).
14: end for
15:
end for
where 8(5, A) (x(8, +VVa('') - (s) is the approximated advantage function. og is the step size for actor's update at iteration k.
Reward estimators' update. Similar to critic, each reward estimator's approximation error can be decomposed into consensus error and the approximation error.
For each local reward estimator, we perform the consensus step to minimize the consensus error
N Ciewo
if mod Kg 0 herwiisee.
X
To reduce the approximation error, we perform a local update of stochastic gradicnt descent.
1 = nR (N) + (eg Xt)),
(8)
where ()) ((s. a) is the update direction. Th is the step size for reward estimator at iteration k. Note the calculation of gf (5. A) does not depend on the next state s'; we use & in (8) just for nolation brevity. Similar to critic's update, RR, projects the parameter into a ball of radius of Rx containing the optimal solution.
In our Algorithm 1, we will use the same order for ag, Sr, and m and hence, our algorithm is in single-timescale.
Linear approximation for analysis. In analysis, will use linear approximation for both critic and reward estimator variables, Lee. (s(s) == d(s) fx(s, a) = (o(s,a) X, where Φ(s) S - Rd= and ((s,u) : S x A + dd are two feature mappings, whose properly will be specified in the discussion of Assumption 1.
Romarks on sampling scheme. Acquiring unbiased stochastic gradionts for critic and actor variables requires sampling from Mr, and dr,, respectively. However, practical implementations, slates are usually collected from an online trajectory (Markovian sampling), whose distribution is generally different from pre and dzy, Such distribution mismatch will inevitably cause binses during the update of critic and actor variables. One has to bound the corresponding error terms when analyzing the algorithu.
3.2 Variant for preserving local action
Note that in Algorithm 1, the reward estimators need the knowledge of joint actions in order to estimate the global rewards. Inspired by (Chen al., 2022), we further propose a variant of Algorithm to preserve the privacy of local actions. estimates the global rewards by communicating noisy local rewards. As a trade-off, the approach requires Ollg(e-1)) communication rounds for each iteration; Algorithm 2.

---

Published in Transactions on Machine Learning Research (01/2023)
Let rf represents (sk, 0x) for brevity. The reward estimation process goes as follow: for each agent i, we first produce a noisy local reward P = r + 2), with ~ o²), Thus, the noise level is controlled by the variance o², which is chosen artificially. When the noise level o² increases, the local reward's privacy will be strengthen. In the meantime, the variance of the estimated global reward will increase. To estimate the global reward, each agent first initialize the estimation as rk rk- Then, each agent perform the following consensus step for K, times, i.c.
K141
Σ WOL 5=1
K, 1=0,1, ,,,
(9)
The reward K, will be used for estimating the global reward for agent at ben iteration. As we will Ex will converge to 0 lincarly. Hence, to reduce the error to E, we need K, = Ollog(--)) rounds of communications for each iteration. Based on the estimated global reward, the is actor's update is given by
see, the error 1 1 N
0 0++1= = 0f aalkk, + +T) Vai (s)) ()).
(10)
4
Main results
In this section, we first introduce the tochnical assumptions used for our analysis, which are standard in the literalure. Then, we present the convergence results for both actor and critie variables.
4.1 Assumptions
A Assumption (boundedness of rewards and feature vectors). The local rewards are uniformly bounded, i.e., there ewists a positive constant Tmax such that for all feasible (s, a) and i [N], we have (s,(sa) (aaa)ss Tmax. The norm of feature vectors are bounded such that for all s S, a E A, [|o(s)]l S 1, 111s,(s a) = 1.?
Assumption is standard and commonly adopted; see, e.g., (Bhandari al., 2018; Xu al., 2020; Zeng et al., 2022; Shen et al., 2020; Qiu al., 2019). This assumption can be achieved via normalizing the feature vectors.
Assumption 2 (sufficient exploration). There exists two positive constants Ao ho such that for all policy ne, the following two matrices are negative definite
Ao. = (o -
(1 Ao.p = (0sp:a/o...ollllpssssspss....00
with Amax (Ap.s) S X3s Amax S Xop where )max()
()) represents the largest eigenvalue.
The Assumption 2 characterizes a strong convexity-like property of critic and reward estimator's objective function, and thereby ensures sufficiett decrease of the estimation error for each update. It will be satisfied when inf Ta(a)s) 2 for all policy Te, S,a a E A with e being positive. Thus, it can be understood as an exploration assumption on policy Ty. (sce Proposition 3.1 of (Olshevsky & Gharesifard, 2023) for more detail). This assumption is widely seen in analysis of AC algorithms; see, e.g. (Shen et al., 2020; Xu & Liang, 2021; Zeng et al., 2022). Together with Assumption 1, we can show that [[))())] < R, := Euaa, [[)( < Rx Iuax, which justifies the projection step. In practice, see Section 8.2 of (Bhandari et al., 2018) for one approach. We provide more details for the projection in Appendix C.
estimate Rs and Rx online;
Assumption 3 (Lipschitz properties of policy). There erists constants Co. Lgs, Ly such that for all policy pommmteer 0,6 0', & E S and a E A, we have (1). (mo()))) No (a|s)) S T. 0 0 || (2). l1Vo(s, vo (8, a)ll 1 [|: (3). [[0((,))] < Cg.
2Through out the paper, will use ||- || to represent Fuclidean norm for vectors and Frobenius norm for matrices.
7

---

Published in Transactions on Machine Learning Research (01/2023)
Assumption is common for analyzing policy-based algorithms; see, e.g., (Xu et al., 2019; Wu et al., 2020; Hairi et al., 2022). The assumption implies the smoothness of objective function J(0). It holds for policy classes such as tabular softmax policy (Agarwal et al., 2020), Gaussian policy (Doya, 2000), and Boltzmann policy (Konda & Borkar, 1999).
Assumption 4 (mixing Markov chain). There crists constants & > 0 and p E (0,1) such that
sup dTv (I((kk E -|s0 s, uo) kp", Vk. #ES
Assumption 4 is standard assumption; see, e.g. (Bhandari et al., 2018; Wu et al., 2020; Xu et al., 2019). The assumption always holds for irreducible and aperiodic Markov chain. It ensures the geometric convergence of state to the stationary distribution.
Assumption 5 (doubly stochastic weight matrix). The communication matrix W is doubly stochastic, i.e. each column/row sum up to 1. Moreover, the second largest singular value u smaller than 1.
Assumption 5 is a common assumption decentralized optimization and multi-agent reinforcement learning: see, e.g., (Sun al., 2020; Chen et al., 2021b; 2022). It ensures the convergence of consensus error for critic and reward estimator variables.
4.2 Sample complexity for Algorithm
Theorem Suppose Assumplions 1-5 hold. Consider the update of Algorithm 1 under Markovian sampling. Let ag /R for some positive constant ā, $x the total number of iterations. Then, we have
Co agg and Ti 2xg 22
Cua and K2 O(K3/A), where K is
E ||ut (0W)l s 0 log K VK
(log* K VK
E [( so
+ O (Capp + Esp)
(11)
where Cg, Cio posilive conslands defined in proof.
The proof of Theorem 1 can be found in Appendix D.1. It establishes the iteration complexity of Ollog K/vK), or equivalently, sample complexity of Õ(=-2) for Algorithm 1. Note that actors, crit- ics, and reward estimators use the step size of the same order. The rate matches the statc-of-the-art sample complexity decentralized AC algorithms up to a logarithmic term, which are implemented in double-loop fashion (Hairi al., 2022; Chen al., 2022). The approximation error is defined as
(s) - (s) + [F(s - (s,
Capp == max E. Esppa 8.0
(12)
The error Eapp captures the approximation power of critic and reward estimator. When using function approximation, such error is inevitable. Similar terms also appear in the literature (sce, c.g., (Xu et al., 2020; Agarwal al., 2020; Qiu et al., 2019)). Eapp becomes zero in tabular case. The error Eep represents the mismatch between the discounted state visitation distribution dr, and stationary distribution Pr.- It is defined as
Esp Esp : 4C8 (ogg, K x 11) (1 71-
By policy gradient theorem (3), the states should be sampled from discounted state visitation distribution in order to atlain unbiased estimation of policy gradient. Nevertheless, the state distribution converges to stationary distribution Mx, due to Markov chain's mixing, which inevitably introduces the sampling error Exp- Similar terms also appear (Zeng al., 2022; Shen et al., 2020). When y is close 1, the error becomes small. This is because dn, approaches Mr, when 7 goes to 1. In the literature, some works assume that sampling from dz, is permitted, thus eliminate this error; see, e.g., (Chen et. al., 2021a).
8

---

Published in Transactions on Machine Learning Research (01/2023)
Complexity result under i.id. sampling. Under the i..d. sampling scheme, state can be directly sampled from Mm, and day. In this case, the logarithmic term caused by the Markovian mixing time, and the error Exp caused by the distribution mismatch, can be avoided. In this sense, one can attain the iteration complexity of O(1/VK), or equivalently, sample complexity of ((==2).
4.3 Sample complexity for Algorithm 2
Theorem 2. Suppose Assumplions 1-5 hold. Consider the update of Algorithm 2 under Morkovian sampling. Let Or = & for some positive constant a and Bx Co ak. Kr = 12)( Ke S O(K1/4), where K is the total number of iterations. Then, have
VK
2A
K
log² K VK
E
-0 (0x)]] S 0 [lw
K
Ilog* K
ΣΣ
E L so
O((Epp + Esp),
(13)
VK
where the constants defined in proof.
The proof of Theorem 2 can be found in Appendix D.2. It establishes the sample complexity of Ō(= 2)) for Algorithm The cup captures the approximation error of the critic variables, which defined as
opp = max E Renni (VeL(s) Vo-(o)(s))
The Algorithm preserves the privacy of local actions and requires less parameters than Algorithm 1 since there is no reward estimator. The cost is that it needs to communicate O(log(==1) times for each iteration.
4.4 Proof sketch
We present the main elements for the proof of Theorem 1, which helps in understanding the difference between classical two-timescale/dee dooblle-oooo analysis and our single-timescale analysis. The proof of Thcorem 2 follows the similar framework.
Under Markovian sampling, it is possible to show the following inequality, which characterizes the ascent of the objective.
-
0R Ta E V [2
Ell (i Wh A1+1
2
SCBauBlIw (0x) w/+1l1 1CGa N
Ollog (K)a O(Eappp + spp)
(14)
To analyze the errors of critic [[,) (1(())_((1111) and reward estimator [A^(0x) 1 12, the two-timescale analysis requires O(a)) < min(O(Bk), Omh)) in order for these two errors to converge. The double-loop approach runs lower-level update for (llo((-1)) times with batch size ( to drive these errors below and hence, they cannot allow inner loop size and bath size to be O(1) simultaneously. To obtain the convergence result for miggle-timscall update, the idea is to further upper bound these two lower-level errors by the quantity (aqgE (l by the ascent term on Ellg' (Et, w/+11 Xi 1.
w/r
(rrg.1E/lga (fx, w 1 (through a series of derivations), and then eliminate these errors
2
We mainly focus on the analysis of critic's error through the proof sketch. The analysis for reward estimator's error follows similar procedure, We start by decomposing the error of critic
W w (0+)l Σ (1 wx+1l? 1|0+11 w" (0+)))))).
(15)
9

---

Published in Transactions on Machine Learning Research (01/2023)
The first term represents the consensus error, which can be bounded by the next lemma.
Lemma 1. Suppose Assumptions and 5 hold. Consider the sequence {wi} generated by Algorithm 1, then the following holds
I[Qu+ ||1 < th |woll + NC
Σ Ar. -Bs
-
Sume
where wa = [wb 1.....,,0 ......ll' : : 1-= E (0,1) is the second largest singular value of W.
Based on Lemma and follow the step size rule of Theorem 1, it is possible to show ||@ Ei 1| Wk+1ll = (K3 Let K. O18 )) we have [[@w*+1l 2|2 ((3)), which maintains the optimal rate. To analyze the second term in (15), we first construct the following Lyapunov function
V4 ((x) || w (0x))l + 1| (0x))]l??
(16)
Then, it remains to derive an approximate descent property of the term ||= w" (0x) in (16). Towards that end, our key step lies in establishing the smoothness of the optimal critic variables shown in the next lemma. Lemma 2 (Smoothness of optimal critic). Suppose Assumptions 1-3 hold, under the update of Algorithm 1, there exists posilive conslant Lu. such that for any policy parameter 01, 02, it holds that
(V)
S Lw,21101- -02ll,
This smoothness property is essential for achieving Ö(L/VK) convergence rate.
To the best of our knowledge, the smoothness of w (0) has not been justified in the litcrature. Equipped with Lemma 2, we are able to establish the following lemma.
Lemma (Error of critic). Under Assumptions 1-5, consider the update of Algorithm Then, holds that
B|ll=x+1 w w0(0+t1)11) S (1 Cgow)) - (0x))?
Elgg wh+ 11+1))11 O F1|35+1--W00 - (0x))) < (1 22 3x) |i - w (0x)11
as
(17)
CK₁ B ZK + CK,ax-20 Bk-
(18)
Here, Zk := min(z E |N & m [KTnk] [1k] }}. Cg \s are constants specified in appendia, and Ck and CK, are of order O(log(K)) and Ollog" (K)) respectively.
Plug (18) into (17), we can establish the approximate descent property of ||ūx - (Bx)ll in (16):
Bill@t+1 - (0x+ (1 Cgau)(1 2x wa w (fx)11
+
OKk
Bigg Wf X X OO BeBk-Kk + Ck, (k 2x Bk).
(19)
4
Finally, plugging (14), (17), and (19) into (16) gives the ascent of the Lyapunov function, which leads to our convergence result through steps of standard arguments.
Remarks on update step. In Algorithuss 1 and 2, the actor and critic updale once for each iteration. This update scheme can be generalized to the case where actor and critic update arbitrary number of constant steps without affecting the order of the sample complexity. In particular, suppose that actor updates C. steps per iteration, and let sh, be the actor's update direction at iteration The bounds (14) and (19) become
N
E[J(0++1) - -((x)) N
akk E [(02)]
+ @ E Fl
(0%) wf+1
2
E (0x) Men1 12] OC (K)aa) - Ol(Eapp + esp)as)
10

---

Published in Transactions on Machine Learning Research (01/2023)
Average Reward
Average Reward
SDAC nci
OLDAC
SeAC-1
SUMRC not basch
botch
1e4
15 Communicat on Complexity
1e3
Sample Complexity
Figure 1: Averaged reward versus sample complexity and communication complexity. The vertical axis is the averaged reward over all the agents. The result is averaged over 10 Monte Carlo runs.
Bl|lw++1 - w (0x++))x) (1 Cbau) - -2 -- (0x))l
+
|E Bc3k- zx CaCK,ak-zxPa
where we replace the norm bound as ll (Ess wht
with |I and apply inequality: 11 < Ca Callg wh41 1/ A/-1)ll- When C. is constant that is not related to K, these two bounds recovers (14) and (19). Hence, we can follow exactly the same proof procedure and obtain the Ō(E-2) sample complexity result as before. When critic update C. > 1 steps per iteration, the expected temporal difference error will decrease for each step by controlling step size, that the bound in (19) still holds. Thus, updating critic for multiple steps will not affect the sample complexity.
Schwartz
4.5 Convergence of single timescal decentralized NAC
The natural Actor-Critic (NAC) (Peters & Schaal, 2008) a popular variant of AC algorithm, which enjoys the convergence to global optimum (with compatible function approximation error) instead of a local stationary point. While our main focus is the convergence of the single-timescale AC algorithm, we find that the proof technique can be directly extended to establish the global convergence of single-timescale decentralized NAC. For reference, we design such an algorithm and provide ils convergence result in Appendix E as a by-product of our tinele-timescale AC's analysis. To the best of our knowledge, this is the first convergence result of singlo-timescale NAC. However, our analysis only establishes a ((E-6) rate for the algorithm. This result is sub-optimal compared with the existing best complexity of O(e-²) (Chen el al., 2022), which is based the double-loop implementation. The main reason for the sub-optimality is that in comparison with the double-loop update, the critic variables under the single-tinescale update will inevitably converge slower due to the change of the actor's parameter in each iteration. Based on the classical NAC's analysis, the slower convergence of critic variables will result in a worse convergence rate of the optimality gap. Please refer to Appendix for more discussions on the sub-optimality.
5 Numerical results
5.1
Experiment setting
We adopt. the grounded communication environment proposed in (Mordatch & Abbeel, 2018). Our lask consists of N agents and the corresponding N landmarks inhabited a two-dimension world, where each agent can observe the relative position of other agents and landmarks. For every discrete time step, agents take actions to move along certain directions, and receive their rewards. Agents are rewarded based on the distance to their own landmark, and penalized if they collide with other agents. The objective is to maximize
11

---

Published in Transactions on Machine Learning Research (01/2023)
the long-term averaged reward over all agents. Since focus decentralized setting, each agent shall not know the target landmark of others, iee, the reward function of others. To exchange information, each agent is allowed to send their local information via a fixed communication link. Through all the experiments, the agent number N is set to be 5, and the discount factor y is set to be 0.95.
5.2 Comparison with existing decentralized AC algorithms
In this section, we compare the proposed algorithm with existing decentralized AC algorithms under the cooperative MARL setting (Chen et al., 2022; Zeng al., 2022) in terms of sample complexity and communication complexity. In the sequel, we refer Algorithm 1 as "SDAC-re" and Algorithm as 'SDAC-noi' (see Appendix 2). The algorithm proposed in (Chen et al., 2022) is referred as "DLDAC', which is based on double-loop implementation. The algorithm proposed in (Zeng et al., 2022) is denoted by "TDAC-re', which is based on two-timescale step size implementation. For comparison, we also implement a noisy reward version of 'TDAC-re' and denote by "TDAC-noi'.
Comparison to doublc-loop dccentralized AC. For 'SDAC-re" and 'SDAC-noi', we set as 0.01 (k: 1)-0.5 Ba_ 0.1 + 1) -.5 TΙe 0.1 + 1)-0.5 K. 5, a 0.5, K, = 2. For 'DLDAC", we fix T. = 50, T- 10, T = 5, Ne 10, N 100, o 0.1 3, which is adopted by their paper (see comparisons under different syper-parametens in Appendix A). We set
0.01, 3 0.1 for 'DLDAC" since observe that larger step sizes will result in divergence. We have to mention that such a inner loop size T. = 50 in 'DLDAC' is not necessarily consistent with the theory of a double-loop algorithm, in which the loop size should be proportional to ()= The sample complexity and communication complexity results are shown in Figure 1. For the sample complexity, "SDAC-noi' enjoys a faster convergence compared with 'DLDAC". In terms of communication complexity, 'DLDAC' achieves better performance as applies mini-batch technique and thereby requires less communication rounds when using the same amount of samples. Such mini-batch approach can also be adopted to our proposed algorithms. Thus, implement mini-batch version of our proposed algorithms, which we refer as "SDAC-noi-batch and "SDAC-re-batee batreb respectively. We set 10 as the batch size for actor, critic, and reward estimator. We can see that by applying mini-batch update, these two variants achieve significantly better commuication complexity compared with "DLDAC". This is because our algorithm updates actor for more times compared with 'DDACC' under the same communication rounds.
Average Reward
-
-8-
SDAC-nol
SDACre
TDAC-nct
-14
TDAG-r
1e4
Sample Complexity
Figure 2: Comparison between the proposed algorithms and two-timescale decentralized AC algorithms (Zeng et al., 2022). The results are averaged over 10 Monte Carlo runs.
Comparison with two-timescale decentralized AC. We fix K, = 1, K, = 5 for this experiment. We set αg = 0.01 (A + 1)-0-, 0.5 3x = (k: + 1)-0.5 and 7 0.1 + 1)-0.5 for 'SDAC-re' and 'SDAC-noi"; we set = 0.01 (A: + 1)-0.6 0.6 S. = 0.1 + 1) 0.44 and = 0.1 & + 1) -0.4 for "TDAC-re" and "TDAC-noi". The sample complexity is presented in Figure 2. We can observe that the convergence speed of "SDAC-noi" is
Note that adopt the notations in (Chen et al., 2022). Here, T. the inner loop size, T3 is the communication number for each outer loop, T' is the communication number for reward consensus, N is the batch size for actor's update, and N. the batch for critic's update.
12

---

Published in Transactions on Machine Learning Research (01/2023)
slightly better than that the two-timescale counterpart "TDAC-noi'. In addition, when using reward estimator for the global reward estimation, we see that 'SDAC-re" has much more stable convergence behavior than "TDAC-re", and achieves significantly higher rewards.
Average Reward
Average Reward
-6
10
-30
-12
-14
con-110
con 20
cone
le4
12
16
1e3
Sample Complexity
Communicat on Complexity
Figure 3: Ablation study on the consensus periods. The results are averaged over 10 Monte Carlo runs.
5.3 Ablation study on different choices of Ke
We compare the performance of 'SDAC-noi' under different choices of consensus periods Ke. In particular, set Oę 0.01 1)-0.5, B& 0.1 + 1)-0.5 K, = 2, 0.5 and examine the consensus periods K, of 1, 5, 10, and 20, respectively. The corresponding sample complexity and communication complexity results are summarized in Figure 3. Evidently, in terms of sample complexity, the convergence becomes slower and relatively unstable as the consensus period K. increases. Therefore, when the communication cost is low, choosing a small Ke will yield a better performance. We also plot the communication complexity under the consensus periods
and We can see that the communication complexity of "cons-5' outperforms 'cons-1" after 12 103 communications. Thus, when the communication cost is expensive and high averaged reward is required, one may large Ke and run the algorithm for a relatively large number of iterations.
6 Conclusion and future direction
In this paper, we studied the convergence of fully decentralized AC algorithm under practical single- timescale update. We showed that the algorithm will maintain the optimal sample complexity of Ō(=-2) and communication efficient. We also proposed a variant to preserve the privacy local actions by communicating noisy rewards. Extensive simulation results demonstrate the superiority our algorithms' empirical performance over existing decentralized AC algorithms. However, directly extending our single- timescale AC's analysis technique to single-timescale NAC will result in sub-optimal sample complexity. We leave the study on improving the convergence rate and design more efficient single-timescale NAC algorithm as promising future directions.
Acknowledgement
The authors would like to thank the Action Editor and anonymous reviewers for their detailed and constructive comments, which have helped greatly to improve the quality and presentation of the mamuscript.
X. was partially supported by the National Natural Science Foundation China (NSFC) under Grant No. 12201534 and 72150002, by the Shenzhen Science and Technology Program under Grant No. RCBS202106088 0009100000000000000 and by the Shenzhen Institute of Artificial Intelligence and Robotics for Society (AIRS) under Grant No. AC01202101108.
13

---

Published in Transactions on Machine Learning Research (01/2023)
References
Alckh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient Optimality, approximation, and distribution shift. (xXiu:198.000200 2019.
methods:
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approximation with policy gradient methods in markov decision processes. In Conference on Learning Theory (COLT), pp. 64 66, 2020.
Jonathan Baxter and Peter L. Bartlett. Infinite-horizon policy-gradient estimation. Journal of Artificial Intelligence Research, 15:319-350 3500,,35522000 2001.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference on Learning Theory (COLT), pp. 1691-1699 2018.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021a. URL 0ItvP2-19j.
Ziyi Chen, Yi Zhou, and Rongrong Chen. Multi-agent off-policy td learning: Finite-time analysis with near-optimal sample complexity and commuication complexity. arXiv preprint arXiv:2108.1814 2021b.
Ziyi Chen, Yi Zhou, Rong-Rong Chen, and Shaofeng Zou. Sample and communictiinn-fffient decentralized actor-critic algorithis with finite-time analysis. In International Conference Machine Learning, pp. 3794- 3834. PMLR, 2022.
Kenji Doya. Reinforcement learning in continnous time and space. Neural Computation, 12(11:219-245, 2000.
Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Vlad Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, Tain Dunning, et al. Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures. In International Conference Machine Learning, pp. 1407-1416. PMLR, 2018.
Zuyue Fu, Zhuoran Yang, and Zhaoran Wang. Single-timescale actor-criti provably finds globally optimal policy. In International Conference Learning Representations, 2021. URL httpss://opemteeteee..ett forum?id=pqZV, -eirvk srUVmK.
Hongyi Guo, Zuyue Fu, Zhuoran Yang, and Zhaoran Wang. Decentralized single-tinescale actor-critic on zero-sum two-player stochastic games. In International Conference Machine Learning, pp. 3899-3909. PMLR, 2021.
FNU Hairi, Jia Liu, and Songtao Lu. Finite-time convergence and sample complexity of multi-agent actor-critic reinforcement learning with average reward. In International Conference Leorning Representations, 2022.
Sham M Kakade. A natural policy gradient. In Proc. Advances in Neural Informalion Processing Systems (NIPS), pp. 1531-1538, 2002.
Vijaymohan Konda and Vivek S Borkar. Actor-critic type learning algorithms for Markov decision processes. STAM Journal on Control and Optimization, 38(1):94-123, 1999.
Timothy P Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Frez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint S.kw:1509.0297. 2015.
Yixuan Lin, Kaiqing Zhang, Zhuoran Yang, Zhaoran Wang, Tamer Başar, Romeil Sandhu, and Ji Liu. A communiettion-elleeenn multi-agent actor-critic algorithm for distributed reinforcement learning. In 2019 IEEE 58th Conference Decision and Control (CDC), pp. 5562 5567, 2019.
Michael L Littman. Markov games as a framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pp. 167-163. Elsevier, 1994.
14

---

Published in Transactions on Machine Learning Research (01/2023)
Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin. An improved analysis of (varianco-roduced) policy gradient and natural policy gradient methods. Aduances in Neural Information Processing Systems, 33: 7624 7636, 2020.
Ryan Lowe, Yi I Wu, Aviv Tamar, Jean Harb, OpenAI Picter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-compeittie environments. Adnances in neural information processing systems, 30, 2017.
Igor Mordatch and Pieter Abbeel. Emergence of grounded compositional language in multi-agent populations.
In Proceedings of the AAAT Conference Artificial Intelligence, volume 32, 2018.
Alex Olshevsky and Bahman Gharesifard. A small gain analysis of single timescale actor critic. To appear in SIAM Journal on Control and Optimization, 2023, 2023.
Shayegan Omidshafiei, Jason Pazis, Christopher Amato, Jonathan P How, and John Vian. Deep decentralized multi-task multi-agent reinforcement learning under partial observability. In International Conference on Machine Learning, pp. 2681-2690. PMLR, 2017.
Jan Peters and Stefan Schaal. Natural actor-critic. Neurocompuling, (7799:11880-1199 2008
Shuang Qiu, Zhuoran Yang, Jieping Ye, and Zhaoran Wang. On the finite-time convergence of actor-critic algorithm. In Optimization Foundations for Reinforcement Learning Workshop at Advances in Newral Information Processing Systems (NeurIPS), 2019.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shimon Whileson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In International Conference on Machine Learning, pp. 2995-4304. PMLR, 2018.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alee Radford, and Oleg Klimov. Proximal policy optimization algorithms. Xiv preprint 1ix:::1007063.44 2017.
Han Shen, Kaiqing Zhang, Mingyi Hong, and Tianyi Chen. Asynchronous advantage actor critic: Non- asymptotic analysis and lincar specdup. ArXi::2012.13 15511, 2020.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354-335)) 2017.
Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. In International Conference on Machine Learning, pp. 5887-5896. PMLR, 2019.
Jun Sun, Gang Wang, Georgios B Giannakis, Qinmin Yang, and Zaiyue Yang. Finite-sample analysis of decentralized deiferra- learning with linear function approximation. In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 4485-4495, 2020.
Richard S Sutton, David McAllester, Satinder P Singh, and Yishay Mansour. Policy gradient methods for reinforeement learning with function approximation. In Proc. Advances in Neural Information Processing Systems (NIPS), pp. 1057 1063, 2000.
John N Tsitsiklis and Benjamin Van Roy. Analysis of temporaal-difffernnce learning with function approximation. Tn Advances in neural information processing systems (NTPS), pp- 1075-1081, 1997.
Oriol Vinyals, Igor Babuschkin, Wojeiech M Czarnecki, Michaöl Mathicu, Andrew Dudzik, Junyoung Chung, David Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782):350 354, 2019.
15

---

Published in Transactions on Machine Learning Research (01/2023)
Yue Wang, Shaofeng Zou, and Yi Zhou. Non-asymptotic analysis for two time-scale TDC with gen- eral smooth function approximation. In M. Ranzato, A. Beygekimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp- 9747-9758. Curran Associates, Inc., 2021. URL https:/ wwwr.ps.cc/pppppeee.a.e.eee htarppss.c//papee/2/////e. pdf.
nwurips.
Yue Frank Wu, Weitong Zhang, Pan Xu, and Quanquan Gu. A finite-time analysis of two time-scale actor-critic methods. Advances in Neurol Information Processing Systems, 33:17617-17622 2020.
Pan Xu, Felicia Gao, and Quanquan Gu. An improved convergence analysis of stochastic variance-reduced policy gradient. In Proc. International Conference on Uncertainty in Artificial Intelligence (UAT), 2019.
Tengyu Xu and Yingbin Liang. Sample complexity bounds for two timescale value-based reinforcement learning algorithms. In International Conference on Artificial Intelligence and Statistics, pp. 811-819. PMLR, 2021.
Tengyu Xu, Zhe Wang, and Yingbin Liang, Improving sample complexity bounds for (natural) actor-critic algorithms. In Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 33, 2020,
Tengyu Xu, Zhuoran Yang, Zhaoran Wang, and Yingbin Liang. Doubly robust off-policy actor-crilic: Convergence and optimality. ArXiv:2102. 11866, 2021.
Chao Yu, Xin Wang, Xin Xu, Minjie Zhang, Hongwei Ge, Jiankang Ren, Liang Sun, Bingcai Chen, and Guozhen Tan. Distributed multiagent coordinated learning for autonomous driving in highways based dynamic coordination graphs. IEEE Transactions on Intelligent Transportation Systems, 21(2):735 748, 2019.
Siliang Zeng, Tianyi Chen, Alfredo Garcia, and Mingyi Hong. Learning coordinate in multi-agent systems: A coordinated actor-critic algorithm and finite-time guarantees. In Learning for Dynamics and Control Conference, pp. 278 290. PMLR, 2022.
Haifeng Zhang, Weizhe Chen, Zeren Huang, Minne Li, Yaodong Yang, Weinan Zhang, and Jun Wang. Bi-level actor-critic for multi-agent coordination. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 7325 7332, 2020.
Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Basar. Fully decentralized multi-agent reinforcement learning with networked agents. In International Conference on Machine Learning, pp- 5872-5881. PMLR, 2018.
Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Başar. Global convergence of policy gradient methods to (almost) locally optimal policics. arXiv preprint arXiv:1906.08355 2019.
Kaiqing Zhang, Zhuoran Yang, and Tamer Başar Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforeement Learning and Control, pp. 321 384, 2021.
16

---

Published in Transactions on Machine Learning Research (01/2023)
Contents
Introduction
1
Preliminary
3
2.1
Markov decision process
3
2.2 Policy gradient Theorem
4
3
Algorithms
4
3.1 Decentralized single-timescale Actor- Critic
4
3.2 Variant for preserving local action
6
4
Main results
7
4.1
Assumptions
7
4.2
Sample complexity for Algorithm 1
8
4.3
Sample complexity for Algorithm 2
4.4 Proof sketch
4.5 Convergence of single-timescut timescale decentralized NAC
11
Numerical results
5.1
Experiment setting
5.2 Comparison with existing decentralized AC algorithms
12
5.3 Ablation study different choices of Ke
13
6 Conclusion and future direction
13
A Additional simulation results
19
B Auxiliary lemmas
20
C Supporting lemmas
23
C.1 Error of critic
23
C.2 Error of reward estimator
C.3 Consensus error
31
C.4 Error of actor
33
D Proof of main results
35
D.1 Proof of Theorem
35
D.2 Proof of Theorem 2
40
E Natural Actor-Critic variant and its convergence
42
17

---

Published in Transactions on Machine Learning Research (01/2023)
E.1 Decentralized natural Actor-Crithe
42
E.2 Convergence of natural Actor-Crice
43
E.3 Proof of Theorem 3
45
18

---

Published in Transactions on Machine Learning Research (01/2023)
Average Reward
Average Reward
SDAC
SDAC noi
DLOAC b2o 50
DLOAC hac
-10
DL.0AC-82a-11
-10
M.DAA--b2-50
1e4
1e4
Sample Complexity
Sample Complexity
(a) Different actor'
rrtiics 8 batch sizes.
Average Reward
SOAC nal
OLDAC-Oop
DAC
2
1e4
Sample Complexity
(c) Different loop sizes.
Figure 4: Comparison between the proposed algorithms and the double-loop decentralized AC algorithm that uses mini-batoh update. The results are averaged over 10 Monte Carlo runs.
A Additional simulation results
In this section, we provide more experiments which compare the proposed algorithms with double-loop based decontralized AC algorithm under different batch sizes and inner loop sizes.
Actor's batch size. We fix T. 50, TV 10, N. 10, which is adopted by (Chen et al., 2022). We examine values of N in {10, 50, 100). The results are in Figure 4a. We observe that the best choice of actor's batch size N is 50, and the proposed "SDAC-noi" converges faster than it in terms of sample complexity.
Critic's batch size. We fix T. 50, T- 10, N 100, which adopted by (Chen et al., 2022). We examine values of N. in {2, 10, 50}. The results are shown in Figure 4b. As see, 'DLDAC' with smaller critic's batch sizes can achieve better sample complexity, indicating that the variance of critic's update is relatively small and the mini-batch update is not needed for this task. Our proposed "SDAC-noi" achieves better convergence compared with the double-loop decentralized AC under different choices Ne.
Note that adopt notations in (Chen al., 2022). Here, the inner loop size, To is the communication number each outer loop, N. is the batch size for actor's 's update, and is the batch size for critic's update.
19

---

Published in Transactions on Machine Learning Research (01/2023)
3. Inner loop size. We fix T 10, = 100, = 10, which is adopted by (Chen al., 2022). We examine values of Te in (5,20} The results are shown in Figure 4c. We can see that the proposed "SDAC-noi" enjoys a better convergence in terms of sample complexity.
B
Auxiliary lemmas
In this section, we provide some auxiliary lemmas, which serves as the preliminary for the proof main theorems and lemmas.
The following two lemmas present the Lipschitz properties of the objective function and value function. Lemma 4 ((Zhang et al., 2019), Lemma 3.2). Suppose Assumption 3 holds, then there crists positive
constant L such that for any policy parameter 02 and 02, we have [) V (02)l s L||0] 02ll- Lemma ((Shen al., 2020), Lemma 4). Suppose Assumption holds, for any policy parameter 01, 02 and S, there cxils a posilive conslant Ly such that.
VV [s)] S Lv
VT., (8) Vaug (8) S L 02l1-
The next lemma shows that the stationary distribution is Lipschitz continuous with respect policy. Lemma 6 ((Wu et al., 2020), Lemma B.1). For any policy parameter 0, and 02, it holds that
drv ) - Lr (log, x -1 + (1 - p) 1|00 - 021
drv (HO, & No, P02 @ To - | log 1 + )){{ 821
drv (pe, @ no, P, M02 nT2 P) - |A|L, log, x- (1 p) )) 0 |l-
We will define Ty = (T K (1 -) for the proof of main theorems and lemmas.
The following lemma characterizes the geometric mixing of the Markov chain. Lemma 7 (Shen et al., 2020), Lemma 1). Suppose Assumplion 4 holls, then there erists 0, [0, such that for any policy parameter 0 we have
sup drv (P((ss, abe 8k+1) -1s0, To)) p4 P) S kp" #
where na is the stationary distribution induced by ao and transition kernel P(-|s, a).
The next lemma bounds the error of the discounted state-visitation distribution and the stationary distribution. Lemma 8 ((Shen et al., 2020), Lemma 2). Suppose Assumption 4 holds, then for any policy parameter 0, there crists k. > 0, E 10 such that
(1 7). drv (oT)) S 2(log, x= 1-
The following lemma bounds the total variation distance between state distribution under a fixed policy and that under an updating policy. The lemma used for analyzing the sampling error. Lemma 9. Consider the Markov chain:
Sk-2 De- ak-z P4 sk-2+1 0R-
OR-1, ax-1 2 sp
2r as P, sk+1
ak-
Also consider the auriliory Markou chain with fized policy:
Sk-z ok-z Py 8k-241 Oe-r, āk-st1" Oa-e, ux-1 Pg Sy
Ox-2, ās
P 5k+1
Let Ek = (sk, ak, 9k+1) be sampled from chain 1, and Ex = (šk, āes Sx+1) be sampled from chain 2. Then we have
2-1
drv(P((f E -100 9k-2+1), P(Ee E -000 2k
5
Σ
| 100 - 0x-2ll-
m=
20

---

Published in Transactions on Machine Learning Research (01/2023)
Proof.
(PV E P(, E E.)
1
- JEE SLES aEA
[P( ds, 0g = a, 8k+1 do') - P(šx = dds Cx. a, 84+1 1 = ds')l
[P(8: = ds, ag a) - PP = ds, ux = a)l /
Σ
P(sx+1 do'10 - ds, az = 0)
JES aEA
[8(2 ds, ax a) - PP - da, ux = a)l
2 JES aEA
[P(5: dO) (alds) - P( = do) (alds)
2 JES
aEA
5 SES
Σ
[8(2 (a P(sk = ds) (alds)
aEA
1
+
P(5S = do)TT d (alds) p( - do)Too (alds))
2
SES
aEA
1
5 SES
|A|L - -0-= |((x = ds)
1117
2
1
[P(sk ds) P(šk ds)l Σ
2
J.ES
aEA
1
- 1ALLx110 0k-5l + drv (P(sk P(E E .))
(20)
The second term can be bounded as
dr (P(sk P(5k E .))
2 3 |P(sk ds) - -P(5 ds)l
PP(Sk-1 d8, ah-1 = a, = ds') - PP ds, āx-1 = 0, 82 dds')
2 VEs aEd SES
< S'ES aEA sES
Σ
[P(S--1 = ds, ax-1 a, 8h = ds') P(š = ds, āx-
a, 8y = ds
ddV .), PP :).
(21)
Combined (20) and (21), we obtain
(Pv(((E( E E c)) s drv E E() E ))
2 |A - 0x-211
Sum over steps, we obtain
(P((E E PPEe E 1) < ddv E. P() E E)) + Σ
A 0 - O2-zll
m=0
1
|A 0x-
2 m==
Next, present some mathematical facts that useful in analysis.
21

---

Published in Transactions on Machine Learning Research (01/2023)
Lemma 10 (CChn et al., 2021b), Lemma F.3). For doubly stochastic matriz W E ERNxN and the difference matris Q = 1 N 11", it holds that for any matrie H E RNNN [W*H] S v IQHH), where v is the second largest singular value of W.
Lemma 11 (descent lemma in high dimension). Consider the mapping F RR + R If there erists positive constant such that
VV((2) (F())lle & L|| - all, Vx,y E dom(F),
(22)
then the following holds
F(() - F(x) VF - =)1l S vml y x012.
Proof. Observe that (22) directly implics the smoothness of each entry Fi:
[VF((x)
> VF(())F S L - yll-
Define
x(r,y)= = Fi()) F((x) - VF,(x) x).
We have
[F(y) - F(x) VF(x)(y - x)|1 =
Σ 21 y)
L
$ m |1 =2|2222
L
Vmily xr12
where the inequality follows the descent lemma.
Lemma 12 (Lipschitz property of multiplication). Suppose f(x) and g(x) are two functions bounded by C and Cg. and are - and Lg Lipschhtht continuous, then f(z)g(z) C2Ly + -ipshhips continuous. Proof.
(((())((z))) - ((22)g(22)) ((a)))))))((()))))) - f(an)((() (=) g(x2)) +1f((z)) f(x2)1l(((=)11 (C CyL,) x2ll-
Lemma 13 (invertible property of matrix). If square matrix sotisfies lom A 0, or equivalently, [X(A)) 1, then A is invertible.
Proof.
++
(I A) lim
A'
lim
1
A
to
1=0
i=1
I
lim
A 1+1
[+000
= I
Since I is invertible, by the rank inequality rank(AB) < (an/ran((A)rrakk(()) I- A and lim Eizo A' will be full rank and thereby invertible.
7
22

---

Published in Transactions on Machine Learning Research (01/2023)
C
Supporting lemmas
Before proceeding to the analysis of critic variables, justify the uniqueness of fix point for critic and reward estimator variables under the update (5) and (8), respectively. Define the following notations
Ag.a ((d(s)(T((s))== - -(())())("""'()))))) )ss)))
(23)
Ag Ap = pls(s.a)p(s.a)",
6 (s),))
b ()
with expectation taken from 8 ~ (o)ss), nB,
5 P. The optimal critic and reward estimator variables given By Assumption 2, Ag.s and As,p are negative
policy 8 will satisfy Ae Ae.s""(0) b A0)) (0)+ be.p definite with largest eigenvalue As and Apr which ensures the unique solution w" (0) A 2g,0 X x²
-A be.p. Let R == Eus RA == "umss Then the norm of optimal solutions will be bounded as I|0" (0)ll s Rw: (0) s Rx, which justifies the projection step of the Algorithm In practice, the knowledge of ds and A may not be available. One estimate projection radius online using the methods proposed in Section 8.2 of (Bhandari et al., 2018).
We slightly abuse the notation by overwriting VT, as Vg. To study the error of critic, we introduce the following notations (erf. 5 = (8),,8))
(E, 0) == (s, + +Vo(('') Vo(s)
ö(E, 0) = r(s, + wVls's Ve(s)
8(E.w) F(s, TO(5') ((s) + 7(6) ww
8(5, A) ==
(24)
For the case of expression, we further define
(,,,, A) 8(g, N),a
dC(C, w) = ()))))
(c(5, w) = 3(S,w)
(e, = ES~EE (c((E.)))
(25)
C.1 Error of critic
The following lemmas and propositions serves as the preliminary for establishing the approximate descent. property of the critic variables' optimal gap.
Proposition 1 (Lipschitz continuity of (0) (Wu et al., 2020)). Suppose Assumplions 1, 2, 9, and 4 hold, then there erists positive constant Lu such that for any 0,, 0g E Nds, we have
||| (02) w (02)l _ L., 10 92l1-
Lemma 14 (smoothness of stationary distribution). For any 0, 0' E Rd, there exists positive constont L,.2 such that [[)))()) Pu (s)] < 1 l'|l
The proof of this Lemma consists of two main steps: 1) Derive the expression of the gradient and 2) establish that the gradient is Lipschitz continuous. For the first part, we follow the main idea in (Baxter & Bartlett, 2001).
Proof. For given policy Te we define the transition probability Po(sss') := = To(als"))(sss'' a). By the Assumption 4, there exists stationary distribution (a(s) which satisfies for all state
23

---

Published in Transactions on Machine Learning Research (01/2023)
(o(s) Σ (P(ss))))))s))
(26)
s'ES
Define the following notations
μe (o(()) ... (o0
R
Po(s) == (o(sss) .. Pa(s))n)]
R|
P(O) [Po(si), Po(s), PPo(sa)
R|S
VPo = [uuo(s)) ViHa(22).... ... [[n((s)]
Ps( (PP(s)))); (P)(s)s2), PPo(s(s.)
Rd
Upon taking derivative with respect to l on both sides of (26), we have
Vuo(s)= = Σ ((())))))
e'ES
-VuoPo(s) V
(27)
(27) can be written in compact form
Viee VupP(() (VPoss))o
(P)(s))
(28)
Therefore, we have
(PP(ss)po. (PP(s,)pol
Vpo(L P(0))
ViO(T - (P(()) -1441))
where the second inequality is due to Vuse = (uge) = v1=0.
=
We now show that I - (P(0) - euτ) is invertible. The first step is to show lim -p7)))cp7)--- Let P. au represent P(O), μı for simplicity, we first show (P- - eqi"t = p pt-tep=" by induction. Observe that. when 1, this trivially satisfied. Suppose the equality holds for k, then
(P- (pk pb--eep" P (p& pk eqe Dep? pk+1 - -p-le eeet - ph ext" + p
pk+1 ph phe
where the second equality is due to (26) such that p efa" and the last equality due to μ² Therefore, we have
lim (16))epb)) lim (P(8)* P(p))-leph) -ui eut 10000
t-000
which together with Lemma 13 justifics that I - (P(() - eH²) is invertible. Thus, we have
Vua = (1 -
(29)
24

---

Published in Transactions on Machine Learning Research (01/2023)
We will utilize Lemma 12 to prove the Lipschitz property of Vpo. We first show the Lipschitz continuous of the first term. Let A(0) to represent T - (P(0) ev²)), ) then we have
|| [A())) A( I|P(0)) P(02) + e(No, 10,
(1((0)) P(02)]l |le(pe po; po:) 1²11
Σ 8,8
(To, (als') To, (cls')))s(s a) + ViSillee -M0,
acA
Σ
(TTO, (als") - ((s)(a( + VISi|uoo 100
8, aEA
1 - 02|1 Σ P(s|s',a)² + VISI - -22l
E'SS
EES
/ISIIIL + 1x) --211-
where the second inequality uses triangle inequality. The last inequality is due to Lipschitz continnous of the policy specified in Assumption 3, and Lipschitz continuous of μ사 implied by Lemma 5.
To see that A (0) is Lipschitz continuous and bounded, observe that
(0:) - - = |44 (a=) - ((0)))
$ | A((1))
$ VIS((IA)L + (00 0111,
(30)
where the first inequality uses Cauchy-Schwarr inequality, and the last inequality uses the Lipschitz continuous of A()) in (30). Since |[A())]] is bounded, ||4=1(0) is also bounded (due to invertibility). which justifies that the first term in (29) Lipschitz continuous and bounded.
We now consider the second term in (29). For any state
V (o - (Pp
V (s) (02) (VPe (s))po2)
V Pa, (s) (o.)) + [( (s) v (s))
V Pa, (8)lll[u,,
1o. | V (8) |6.1|
Σ Σ
(als)
- -22ll
S'SS aEA
ΣΣ (T - (als)) a)
[C + L+)1 0211,
which justifies the Lipschitz continuous of V Define B(0) (VPa (Poos)))l we have
[B(0,) B(02)l < 1 I,)] 02ll-
Since Vpo (0)(B))(0), with (0) and B(0) being Lipschitz continuous and bounded. Therefore, according to Lemma 12, there exists positive constant L,,2 which satisfies
|V Vpo, ll S L, -82l1-
Proposition 2 (restatement of Lemma 2, Lipschitz continuity of Vew" (0) (Chen et al., 2021a)). Suppose Assumptions 1-4 holds, then there crists positive constont Lu such that
Vew (01) Vow" (02)llr S Twu,2101 02l1-
25

---

Published in Transactions on Machine Learning Research (01/2023)
Proof. The proof follows the derivation of Proposition 8 of (Chen et al., 2021a). However, they make assumption that po(s)) is Lipschitz continuous, which we have justified in Lemma 14. We present the proof for the completeness.
We have w²(0) bo where A is defined in (23). The Jacobian of wn (0) can be calculated as Vaw" (0) - Vo
A (Vo Ap A (Vobol)).
(31)
We can utilize Lemma 12 to show the Lipschitz continuity of (w) We have to verify the Lipschitz continuity and boundedness Ap.or be.o. V8Ag,s and Voba.s-
The Lipschitz continuity and boundedness of Ag has been shown in (30. Let bi and by represent do, b have
|6 b2ll = |[]r(s, a, - 33)(ll
0, a, E)- a( -lllv
S sup ||r(s, a,
,,0,s'
< Tmmxx [|Pesl|((ssss__sp_ a, E -) P a. ( e))llrvv
< 2||A| log, x= + p1- '10 02ll.
where the last inequality follows Lemma 6.
We now analyze Vo We first define
A(s, = - ass = s')((s)
as
VoA0. = Vo Σ po( Im(()aaaappp))::)))0))))))
= Σ
8,0,8'
By Lemma 14 and Lemma 6, and Assumption 3, (*)),, no(als), Vona(s), Voro(als) are Lipschitz continuous and bounded. Therefore, Vodg, Lipschitz and bounded.
Finally, we analyze Veba. by following the same technique.
Vaba,o Va
ua(s) (e(s))aaaas)P
s.a.s'
Σ 8,0,0'
(3))oooa(sss a)b(s, a, s')]
By Lemma and Lemma 6, and Assumption 3, (*),,, To(a)s), Vana(s), Vovo(uls) are Lipschitz continuous and bounded. Thus, Voby.s is bounded and Lipschitz continuous.
We have shown the Lipschitz continuity and boundedness of A bo VoAr,s, and Vobe. Therefore, by applying Lemma 12, conclude that there exists a positive constant Lu,2 such that Vow" (0) in (31) is Lw.2-Lipschite continuous.
Lemma 15 (descent of critic's optimal gap (Markovian sampling)). Under Assumptions 1-5, with we41 generated by Algorithm 1 given We and 0₂ under Markovian sampling, then the following holds
12 Cg Vd
Bl - w (((++1))1 [p] < [1+4L,NOx
+ 2
Ellaa+1 w (fx))12
L2,
+
CJN + L2CON
a
| (Et, wh+1 11111
(32)
26

---

Published in Transactions on Machine Learning Research (01/2023)
B|| ((x))] (1 2A,,Bk)Bl1s w (8x)ll + CK, + CK,
(33)
where the constants are defined as CK, = 4C20,2K + C3 Ck. = 4C,0,2x + 2C3Co2 + Cs. 2K =
minf2 E |mpp & min(ax Tk]].
Proof. We begin with the optimality gap of averaged critic variables
| w" (0x+1)ll²
-I - (0%) + w² (8x) -
|Wk+1 - w0x)) + (0,) - w" (0x+1)ll + 2/wx+11 -
w w0(0ww00' (0x+1))
|k+11 (0x))l + 23 2( - -w((0k) Vw" (0x)² (0z -b++1)
2( - (0 - w' w0(0++1) - (0x) (0s 0x+1)),
(34)
where the inequality based on the Lipschitz of (0) implied by Proposition 1
|| (Ok) w w0x++))l < L. 10 Oc+ili 113
N
110x- - 1x-11111 Σ
| 3 wh. X xo) (sk. af)11 Na
(35)
with Cg = CsCss and Cs is defined in (39).
The third term in (34) can be bounded
(K+1 w (0%), Vw" (0x)) ((( 0k+1))
| - w (0x) (0.)² (02 02+1)l
Vw (0+) [ w (1))l1(0 Ok+1l
Lu [[0k+1 w (8x) 0s+1ll
Woww/WWn+ - w (0s) (0+) (ER, w 1b+1
N
ak Σ (2L.aallb6-11 - (0x)))
(Ex. (Ex, wh+t 11+1)113)
(36)
8
where the second inequality follows Proposition 1, the third inequality uses triangle inequality, and the last inequality uses Young's inequality.
The last term in (34) can be bounded
E B[5x+1 - w (0x), w (0x) w (6x+1) Vw" (0x) 0x-1))
L3.2
/dgE||WAH1 - w' w0(0)=))))))))))))))) (0x) 0x11
12
I2 110 - 1x.12
/d,EllWHt w/ (1x) - 0x11
L2
L2
< C (0x)l1 + NC
(37)
The first inequality uses Lemma 11. The second inequality induced by Young's inequality. The last incquality follows (35).
Plug (36) and (37) into (34) will yield (32).
27

---

Published in Transactions on Machine Learning Research (01/2023)
We now prove (33). By the critic update rule, have (crf. ge(0,w) == Bsruue (o)(:
E Wk+1 - w (fx))l2 = E| R.. (wk + (xDc(EE, RR w (8x)1l
l + (A wx) - w (0s)ll
1 w (0+) 3. (e w1 + 2, - w (0x). Blge (Ex, wx))
(8)
| - (0w))l + C + 2B (T) - w (0x), Blū wn)l)
1 w²
+ 2 + (3 - (0x), ge (0(0k,
+ 23x - w" (0x), Bly,),,, Wx)l -90(Ox wk)) ));
(38)
where (i) due to the non-expansivennes of projection to convex set, and (ii) follows
lTe(S, w|ll - [r a) + r0(5') -=()"" w S maax + (1 + Rw = Cs.
(39)
The product in the third term in (38) can be bounded as (wx w (Os)s (Ox, Wx)) (wxe w" (0x), Ee - loo(Ex wa]l
(wx w (0x). Es- (E wx) - ge w- (Bx))l)
BBx - wn (0x),, R Re-ro (7(((()))))) - (1) - w (Ax)))
-Bu(Wx - w w0x), o w" (0x)))
S -Ao |Wا - w (0x))
(40)
Here the first equality is due to critic's optimality condition ge (0k, wn (0x)) Bga ( = 0. The last inequality uses the negative definiteness of As of Assumption 2.
Plug (40) to (38) gives
E Wk+1 (04)11 < (1 (1- -2
- - (0x)11 SEC3
2B w" (0x), (ER, wk)] ge(On, ak))
(41)
We now bound the last term in (41). By Lemma 16, for any 2 E N+, we have
B(a w- (0x) (Ex, w (o,, ax))
S <C 0x- C2 ورز Wن = |||++00 C3
- - 0k- + CaKp"
m=0
(
C1
E B110g-nt Ok-all + C2
E Wk n+1 øk-al
n=1
I-
C3
1k #k-m-n+1 - Ok-m-nll + Cynp*-1
1-1 3-1
< C
Ok-n + 2C2Cs Σ
Bk-n + C2Co
Σ Σ
ak-m-n + CSKPp*
m==
(6) < CCzCzz + 2C2Cs2ßB-s +
+ Csspp-1
(42)
where the (1) uses triangle inequality, (11 uses the non-increasing property of step sizes.
Let Zk, we have (crf. ZK == minf2 E N+ |mp=-=1 & minfax, (x,
EWw wtt) - (0 wx))
22 Zx + 202C0 Zx + C2Co2f a2 + Coax-Zx
(43)
28

---

Published in Transactions on Machine Learning Research (01/2023)
Plug (43) into (41) will yield
|| w" (0x)]l 1 (1-22 |50x - -0,)) C3
+ +4C,Co2x0k-24, + +4CgC22kBk22x + +C,cColRak-2x + 2Cgak 2xx
By defining Ck, == 2 + C/ Ck2= -0, + 2030p2 + Cs, we complete the proof.
Lemma 16. Consider the sequence generated by Algorithm 1, for any 2 E , we have
E(w; w" (0x). gelk, (c(Ok. - C1 0k-= + C2 C2l Wx==ll
s-1
+ Cs
110 0k-=|l + CsKpp-1
(44)
where C1 := Co (1 + logp ~1 + (1 - p) + 20gLw, C2 == 4(1 + R) + =0ss, O3 =
Co Cg == Cs.
Basically, this lemma shows that the term on the left hand side of (44) is of order Ö(ax + Ba).
Proof. Consider the Markov chain since timestep k- 2:
ak- Pa
O Op-etl
02-1, ax-1 2 8k
" as Po 8k+1-
Also consider the auxiliary Markov chain with fixed policy since timestep k - 2:
8k-z 0k-E 0k-z 8k 84- Be-e, āx- Ok- āk-1 2n 8k 0k-z, āx 2g 5k+1-
Throughout the proof of this lemma, we will use 0,0',,,,'',5 E, as shorthand notations of kk: 0x- Wh, wh-zi EK.EA. Es.
For the case of expression, define
A1 0,))) = (w-""(0), -0 (0,w))
Therefore, we have
(wx wn (0x), (E6,,, wxx - (e(Ok,
= (E,
= A1 - A (5, 15,0 ()) + A (E, 0,,00000) ()) - A1(5,8',00
A 15, (,,, A16E, 1')'"))))))))))))))))))) + Ai(E, +
(',"")
(45)
11
J can be expressed as
h = (ā w (0)) (), - (5 w (0'). (6(0''2)) (0.5)) x)) - (3 - --- (0), - 90 ())
= (ã - wn -
+ (0) w² (6') (0())))
< || wn ( @) (0. + (l) w (8)) (l)(EE w) (f))))))
(46)
The first term can be bounded as
| ( (0', (0',))))))))),)))) ()- (0, x| < 2R, | BB (5, - Ee (S,
< 4R, sup ll (c, w) dd (16 @ m/ & P, क. P)
< 4 RR Cidry 3 T 3 P. X n. x)
< 4r Log (1 log, K + - (1-p) ||0 011
(47)
29

---

Published in Transactions on Machine Learning Research (01/2023)
where the first incquality is due to I R induced by the projection step of critic's update. The third inequality is due to [+)ا I Cs, and the last inequality follows Lemma. 6.
By the Lipschitz conitinuous of w² (0) proposed in Proposition 1, the second term in (46) can be bounded as [|=*(0) - w (0') Ill w) ge(0, +|له - 1
1 - 0 (I) - a (0, W)ll
- 2C سي 110 8'1
(48)
Plug (47) and (48) into (46), we can bound 11 as
+ 1 S (4R, (1 x -1 + (1- -)- + -C0LL)110 0
(49)
12 can be decomposed by
1 = (w w (0)) 9c(6 x)) - - w6'
ge (c(f'a')) ,d)))
(a w² ((())) - (.(6' (w' (0), (c @)) 9. (6',))
w
(0') (.(E,w") 9o(0', w) + go (0', R)))
(w - ((0))) (0(,W)))
+ (ā0 -00()), - 3.(5. (0 ()) + ge ,0))
S (0))) (a' -
Bc(E, - (0 ()) + (e(f'a''))
The last term can be bounded as
(5/ - - - -00(0',00 + (0',5a"))
- 5o(
$ || -0 (f)1((0((EE)) - De(E, w|)l + |l (0', x²) (c()"
s -) - (8', a)) ge(6"' I))
- ( W')l - IIg.(E, - go(E,))])
4R + -
(50)
where the first inequality applics Cauchy-Schwarte incquality and triangle incquality, the second inequality follows the projection of each critic step. The last inequality is due to
@)) (e w²)|l = (T)))())())) w²) o(s) (5 -=))I s >>|oo(s)) (=>==>=\++++ w')ll 10(s)) (w)=')
< (1 71 -'1l-
Thus, 12 can be bounded
I2 3 (4(1+))), 2063|| -
(51)
We bound Is
E[I 0', Sk ++1 E|A (E, 0 50) - A, "')0" st-2t1]
< 2sup A (1 "'"')) drv (P E 10', s8-2+1) PP E s00()))-++1))
8R, Codrv (P(E E 10' Sk- P() E .18", sk-2t2))
#-1
< 4R Σ
110mm 8z-
(52)
Here, the second inequality due to ||, 0' wi)ll S ||W1 - - (0>0lllla(()) (0' (()(w/))l S Cs, and the last inequality is according to Lemma 9.
30

---

Published in Transactions on Machine Learning Research (01/2023)
We now bound I
E | a (8+2-11 B[Ai (E, 8 ('))'' sk--111
< sup A (')IIE E -100888-2+1) p4r @ wa @ PI
S Cadrv (P(6 E -100', (01=++),,1000 @ To P)
I CoKpp"
(53)
where the last inequality follows Lemma 7. Plug (49), (51), (52), and (53) into (45), we get
(E 0, & (4R,,Ca log, + (1- + 2CIL.)B110. 0x-2ll
+
+ 20 W - -
+ (4R,
Σ
Bm Ok-ell
m==
RR
which completes the proof.
C.2 Error reward estimator
The analysis for the error of reward estimator is similar to critic. To see this, we only need to change āe(S, ()) into Gr (E, = (r(s, a) pls, (),(())))))))))))))))))))))))))) to recover most of the proofs.
Lemma 17 and 18 are the counter parts of Lemma 15 and 16 for reward estimator.
Lemma 17. Suppose Assumptions 1 2, 3, hold, with A generated by Algorithm 1 given d and 6g
under Markovion sumpling, then the sollowing holds
12.2 C@N / doag
E1 10(0++))1210N) < 1+4L,Nas + 2
IE 111AA+1-~~0011
[2
C2N + 1,C0,N
2
+
|1 (Ex A1 N 1111.1112
(54)
s (1- -mm-)))1Ae - + - CK..B.Ok--xe>
(55)
where CKς = 4CoC^ZK + C2, Ck. = 4CrCoZK + 2C,Co2 + Cs Cs = mintz E N+|xp=11 5 min(ax, 3K. 1, C^ = mmax + RA 2 max (((r(s,)) - p(s a){{(s,))))
Lemma 18. Consider the sequence generated by Algorithm 1, for any 2 N we have
EK (0)0), Au) (02. AeMi S Cs110A - 0--ell + C-ColAx - dR-zll
+
110mm - 02-22l + Camp3-1,
(56)
m=0
where C₃ 4R2C, + log, -1 p)- + 202li, Co 4R, +2 Cr 44R.C/ALLL Cs 8R.Cx.
C.3
Consensus error
Lemma 19 (restatement Lemma 1, bound of consensus error). Define the matrie representation of critics
and reward eslimators' porometers Wh = [ ... W. d = [N,,.. N Let Q = I- 11 then
31

---

Published in Transactions on Machine Learning Research (01/2023)
the consensus error can be expressed as Di= 1ww wxll2 1Qwa 12, E - 1|Q2111 Suppose
Asssumption 5 holds. Let {wf)); (NehR be the sequence generated by the Algorithm then for any k 2 1, the following inequalities hold
A
lQwall Sv -Iwoll + AVNCs
Σ
3
(57)
t=0
k
IQaIl Sut= + +VVNCx
BLv RC
(58)
t=
where V E 10 is the second largest singular value of W.
Proof. We will prove the bound in (57) for the critic variables. The analysis for reward estimator in (58) follows the same routine. simplify the notation, we will use g to represent gE(Ex, wi) throughout the proof of this lemma. We also use ej to represent the projection update ej. := IRR (w) - Bugg)) (w (xg()) Define Tk =- Ein zii En = N >i=1 e and the corresponding matrix exressions as
Tott?
(et)
Gk ==
Es ==
(o )T
(
According the update rule of critic variables, the following equalities holds
W Wwn B& + Ex, if k mod K. = 0 Wk
Wh+1
(59)
B&G Ek, otherwise.
To bound the consensus error, We first bound the consensus error of critic's update as
N
(
N
||QGk|I
19 gN
12
2| + 21 < 2VNCs.
(60)
N
2 2| + 2/ (8) Σ
N
N
[| =
l1e
2011
S
2 23 23 VNC..
(61)
where (i) is due lI Cs: (di) is ensured by the convexity of the projection set.
We now study the consensus error of critic variables. Let K'' = [ Ke. By the update rule in (59), we have
Qwx @WWw-11
QEx-11
WQWW-1
-w- +QE
W-1 Σ
t=k-1
WWOww-K
+ Σ wIK---- k- Ke
(62)
t=--K K.
where the second equality is due to the doubly stochasticity of matrix W implied by Assumption 5:
QW = W -11 W t = WQ The last equality is indicated by the update rule that
W-2
W-2
Ww wk-Ko
Σ
B.G.
Σ
E..
t=
t
Expand the recursion in (62), we have
#-1 Σ
K- W B.QG, + Σ
Qwi W x Qwo
WeQQE
t=0
t=0
32

---

Published in Transactions on Machine Learning Research (01/2023)
where C₁ := -= [K'-] K.
k'-1-t1 Therefore, the hi iteration's consensus error can be expressed
k-1
k-1 Σ
Qwa QWE 3.Q. +
t=k'
k
= W t Qwo
W + Σ QqQQE
(63)
t=
Take norm on the each side of (63) and apply triangle inequality, we get
1[@w]l S | the Qwoll
+
Bell
+ IWRQE
1=0
t=
(0)
S x
Woll + Σ
GG +
(is)
S b
السه| + +VNNC3
3ee
1=0
(15))
I u ||m|| + 4VNCs
Σ
Bev k-t Ke
1=0
where (i) inequality uses Lemma 10 and the fact that the spectral of Q is less than 1; (ii) is due (60) and (61); (dit) uses the fact that K' & and [ 1 k-t Ke 2 K.
K. K. 1' 2 1 1
k-t K. 1. Thus, the
proof for (57) completed. The proof of (58) follows a similar procedure, we leave as an exercise to reader.
C.4 Error of actor
The following lemma characterizes the sampling error of actor. Lemma 20. Consider the sequence generated by Algorithm 1, for any = 2 1 we have
[Eenuo [ō(E, (15,0))or (Sk, at) 1E(((Ek, 0% Ox) (sk, all
S 20orpp= 11 + C12
10-mm - O2-ell + Ciall0 - Oz- 11 + Ciall0% - 08-211
(64)
m=00
where C12 : Al C=3:= [Aog x- (1-pp) p) 2(1 +2(1+ + Cu = 2C
Proof- Consider the Markov chain since timestep k 2:
_ 8k-z+1 0 0g-2+1
8x 0k-1, a
P, 8k
Bk, P sk+1.
Also consider the auxiliary Markov chain with fixed policy since timestop k 2:
Sk-2 ak-s P -41 ak-s41
áx-1 P3 3t 0x ān P sk+1.
Throughout the proof of this lemma, we wil use thg to represent whs (5k, at) for brevity. We define the following notation for the ease of discussion
Ag 0) = Ee-ns 18(5, 0) - 6)b.0)
Then our objective to bound
|B|| A3 Ow)lll 0u-z]-
33

---

Published in Transactions on Machine Learning Research (01/2023)
We decompose (EA, 0x)l by applying triangle inequality
|| (Ekk, 0w)l - | 0x) AS(ER. 0x-2)11
11
A 0k-x)
AS(ERs 0k-=))
12
|As(EE, 0R-=)1
(65)
13
We apply triangle inequality again to bound 1ı
1 18(Ex; :)oo Ö(Ek. Oz 1 11
19
+ Bempee (ō(5, 0z) - REe-er 18(E, Ok- ))
(66)
19
1 can be bounded as
1 = ||Ō(Ek, 8x- )o0 8(Ex, Os (x)
I [iŌ(ER, OR Vog 8(EN, Ox)
+ 110(E. 2x 0x) 8(EA. 0%: 0x) 11
I (Von (5') (s)) + (Vo._.(s) Von.. (5 (6)))1622211
+ 118(EA, 0x) 0x) 8(5x, Oz 9/) !1
< (1 + ||0 0x-z2l + [1ō(Ex, 0z) -_ - -E(Ex, On 0r)oz |I
$ (1 + Lv 0x-2ll + C3L 0h-ell
(67)
where the second last inequality follows the Lipschitz continuous of value function in Lemma 5, and the last inequality uses Lipschitz continuous of thg.
((2)
can be bounded as
((2)
|Be (0(E, Oz) Ox)) Ee-nol_ Lō(E, On- 2) ]11
Bg IEgNuo 18(E, 0k-o >)00 BE~ 16(5, O2 - 100
+ Ee BE (8(E, On ))oo -5(E. 0n (00m=2)): )oi, (op...1) _1ll
A A| K -1 + (1 - -)-1) -
01-22l
+ Be (5(5, 0%. V/og -((, 0x_ )bbo0__)]
A A| K- + (1 p) ")Col00 0x-=ol
+ (1 (1+))) + 1| 0x- + C. |10 02-211
(68)
where the first incquality applics Lemma 6, and the last inequality uses the derivation in (67).
Combine (67) and (68), we have
0 - 02-=1l h s [A|L(log, K -1 (1 (1-
+ 2 7)v 10 0x-2ll |l 2C 110 02-211
(69)
34

---

Published in Transactions on Machine Learning Research (01/2023)
We now bound I2
[|4]] = (En. On 0x-z) Ō(Ex, 0x-2) 1
S 2 sup |Ó(EE, O2 Ok==)(oo _odd (P(Ex E 10 8k-2), P(Ek -10 8k-z))
$ 2C
| 1 - 0k-zll:
(70)
m==
where the last inequality follows Lemma 9.
Is can be bounded
13 = 1BI 10(5, O2 0x-2) - -((E,, Oz 0x-2
- sup |0((5, 0k (l -106-2, 82 sk-2); Hoe-. @ Top_, ② P)
$ 2Corp""11
(71)
where the last inequality follows Lemma 7. Plug (69), (70), and (71), we have
[ [6(E, (k)vi (sks at)] [E] Ox)rreg (sk: ak)]l
< 2Compp=11 + 20' T1p 110 02-zol || + 2C
T 10 - 0k-
m=
+ ([A|][logg -1 (1 2(1 + )1 -Oa-
which completes the proof.
D Proof of main results
D.1 Proof Theorem
Let 0g E Ndo be the stack of actors' parameter at timestep k. By Lemma 4, we have
E [[ - J(Ox) 2 [(())(() 0x+1 - 02)l
=1 -10 - 0x11
-
L
L
(V: (Ox), 0 01)
10
1
N
ax p: ((x)), (f.. N1
a >
E lg
wf Ab
Fkk V I(Aa)l +
E (E,, w N1 1
2
2
ak V J ((x) - E (Ee, wi Al 1)] IP]
(EL,
L NC
(72)
2
where the expectation is taken over EN under Markovian sampling. The last inequality due to
Il wher Nf.1))l [|| |6EE, wi, Mo) (SK, ob))l SCCC = Co.
CsC.
(73)
35

---

Published in Transactions on Machine Learning Research (01/2023)
For brevity, we will use Vog to represent dogg (sk: d.).
The gradient bias can be bounded
V g: ((x) - E ga (Ex, w 2 Nu 1112
(Ó(En, 02) 8(En w" (B=))) ]1r
$ ((O)) E 6(Ex. 0kx 0x) +4 E
+ E (B(Ek; - 8(5k. w 10 11 +4 E (8(Ek. 8(En, Wh+ 1: Ne. 1241))
1|? (74)
where the incquality uses I|a + el12 S 4|1a||? + 4||b1| 4|lc|12 + 4||d]1?.
We bound I
1
Vo.J(On) [((E,, Oz Ooo 10x
8(5, Ox)a,, 10u] - EE [ō(Ex= Ou Jrio [8u] ]
Bewddo
<
Be 0(S, 0z) 0x) (6.)
- Remuu (0S5 O.).0o 10x 11 +2 Bemas [8(., 0x) 10
IR ((
0(Ek, 0x) Vot 10x ||
1(
(75)
From now on, we will use & de to denote s dra (-|ss, s' for notational simplicity. 11 is the sampling error under perfect value function estimation of critic. It can be bounded as
1 1x
V ((Bx) - E [B((EN Ox)vee 10x]]i
=
(8(.. (...0))rrs [0x]
Beruus [o(s, 0x) [0k l|
2 sup |o(E, (ier || drr 6 Toe @ de @ Te @ P)
(2CadTv (Mox, d)
(4)
< 16C2 (log, x- + 1 21
where (1) uses (73); (M follows Lemma 8. Define sp = 1Cg(1og, + 2)
212(1 7)??, then we have
1 < 45
(76)
By Lemma 20, ((22 can be bounded as
(2) < 20onp=-1 + C12
10-m - -0-mm10-sl11 +1 Ox-ell + Ciall0/ 0b-=11l Σ
m==
m
20ompp-1 C12
10k-m-nt1- -
0k-mll + C13
10 10k-tt1 Ah-nll + C14
1
0 8%
2Compp"' + C12 2(2+1)
ak= CIaNaaCok + C112Cauus))
2
< 1602 2===2 CB-2000
0/
+ N2 + +C 20 C2
(77)
36

---

Published in Transactions on Machine Learning Research (01/2023)
where the second incquality uses triangle inequality, and the last inequality applies (a + b + c + d)2 1 4a + 4b2 + 4c + 4d2. Let Z == min(z E N+|mp==1 v min(ax, mx)) Then we have
1 - Ck.ak-2N
(78)
where we define Ck2 160% + 2C 40 N2 2 C + 40 Cg. Thus, we have
11 S a5 - Cx2 ok 7x"
(79)
The term Iz describes the approximation quality of linear function class, it can be bounded as
(ō(Ex) 0n) - Ö(Ex, (0 (0x))) ||
1
E
[E(A: 0k) - _lEK, w (0x)) 2 /obo |-]
E
(44
by Viog (SK+1) (ow + Vio, (0x) Po-
TE
(aa)
(n2D Vo2 (88+1) ( 27 + VoL - PoT(ON(ON)
S 20
(10)
20 (1 + >=)ppp S 40
(80)
where (1) applics Cauchy Schwarz inequality and triangle inequality; (it) is due to 1 || S Cs. which is ensured by Assumption 3; (Hi) uses la b12 s 2/a|2 + 2|b/2; (tilt) follows the definition of the critic's approximation error:
app max V Bonuo (s) (v) Vw- (o(o))
(81)
Ia captures the error of critic's estimator, which can be bounded
E (Ō(Ek) w w (Bx)) (( Voz 11
[[4s]
(((E)) (Bx)) 8(EK, wh+ )1² /100. 19
E
s C ( )T (w (0x) wh++)) - ((())² (w^(Ok) |1
s c3 2E (T(())+1)) TT (w" (0x) wh+1) |9] + 2E [((s)) (w (0x) w 11
s c (27²E
||0( (0((sk+1)) ([=()))) (0x) w/ 11 + +2 [1o(()))1 (0=) we 111)
<20 + (0=) (0x) w1+lll 2| 4C (0x) wh+1 1|?
(82)
where the last inequality is due to [|(())] < 1, which is specified by Assumption 1. 14 characterizes the error of reward estimator, which can be bounded as
E[4]] = E ((Lk wh+ - ô(EK, wht 1 )er1)) wog [
E
E
[iss, ax) p(5k, an) N 12 1R
< c 22 [[(sk) ax) p(su )x)² T X (0())
2E [1 ax) ((s),a)) TT) 12
2 (
< 220 + +2 (xL( 11
(83)
37

---

Published in Transactions on Machine Learning Research (01/2023)
where the Eapp in the last inequality is the approximation error of reward estimator, which is defined as
[[(ss.)) - (0)
app == max 8,0
Combining (79), (80), (82), and (83) gives us the bound of the gradient bias error as
V F(Ox) - Elg (Ex. wh Xe Mll I 16(c.p + Ch + 16C (0x) - wl+
+ +80 1 + 4CK, ak a 2xx
(84)
Plug (84) into (72), we get
-
0kk E V 0: ((x)) + ak
Ellg' (Ex: Wh:1: 11+1)112
2
2
Bhh (0n) wh+1l1 Caa Not11 113)
NChht 2NCKx at- -xx - 8(eep + ((sEap))aas
(85)
2
Consider the Lyapunov function
V& := J(Ob) 1|0 ('(6))]? + || - (+x))1
(86)
The difference between two Lyapunov functions will be
[[V++1] [[V+] [[J(0,)] - ([]((+++))))))) + B|| w (0x+1)l1 E.|0a w (0x))l
+ + - (0x))1 - EIJ - (0x)
N
Vo: a Ellg's 2
Bllls (Ex, (Ex+ 11++))11
==1
+ 2NCK, 0k 2x + NCJaf + 8(E + ChEapp Nax
2
80 CoaBEll (0kk) wh+1 12 + El wk41 w (0 1)1 - w (0x)1l
Ts
40 (0) - 1 B1I+++1 - X (0 E1 - (0x0))
(87)
The first two terms of Is can be bounded
(O)) wh+1 Wk+1 wh+1l1 Bl -s' (0x+1)))
(CaaEEWWkH - 11+ SC CCRaaBlWat - w² (0x))1 + - El - w (0x+
80 un E 1 - (0x)) + +B - w (0x+1)11 2 tox
12.2
E Bk - w (0x))1 1 4 + 80 + N Vd
2
+ L2C
E (EL, Wh Nk+z))]( 11 ag
(88)
2
4
1=1
38

---

Published in Transactions on Machine Learning Research (01/2023)
where the equality is due to The first inequality follows the Lemma 19, where Ma, is defined as
w (0x) WK+1, wh+1) (w- (0x) 1641,W044 Wk+1) 0.
h
MR, = v a5 1woll 16NC;
Σ
Bru tee
+ +8VNCouUee - B.
The last inequality follows (32) in Lemin 15.
Plug (88) into (87), and define Cg == min {el Naw + 808.s + Lig N N S Scaa). we gel
12 C2 + LECEN ox
Is S (1 + Caar w0"h)]1
+ Σ
Elg (SA: w/
1/ X ta
< [[1 + C1a 21x3k) 1|E||b - w -0 (1=)
+ (1+ + (Cx BeBK-ZK 2x
2xx)
CEN + 12 af +
N
+
ak
IE
[o (Eiss Weer, A ( as May
(89)
4
where the last inequality follows (33) in Lemma 15.
By letting BR 2h
Co ork, we can ensure
(1 + C1 220 <
Therefore, Is can be bounded as
N
I2 12,2
O I
(ER 1111 ag +
+ +L.CNN
ar
4
2
1=1
+ (1 + Caou. BeBB xx +
(90)
By applying Lemma 17 and following the similar procedure, bound
12
16
<
Ok Σ | (Ee, wht 1112 Mr + 4
13G3N of
2
(1 1--- 2x + Ck.TB0k-2z)
(91)
with 7p
Cuar Cio and Mc, are defined as
2x
L2 Cio min c 4LaNaa + -45 C N / dooa S cakk
4. Σ
Mb. : Rt 22 16NC2
m + 1=0
+
Σ
na Re
(92)
t=
39

---

Published in Transactions on Machine Learning Research (01/2023)
Plug (90) and (91) into (87), we have
B
E|V
V J(0x)]1 + (Mrr Mxa)ax
i=1
+ (1 (CK, Bx8k-2x + -Kg
+ (1 Cinars)(Css 11ll--- xx +
7x)
L
2 NC3 + Cu at +((Epp CBEapp-
+
(93)
where Cn = Cg. thae
L2 12).
2
By letting ag as
Vk
for some positive constant a, and recall Bk = Cv 2x,
ak. 17s
Cla ark we can telescope (93) 2Ag
K N
Vo
2 K
ΣΣ
E
+ 16( + Cappp N) +
(Mxl + -M22)
K
Kox
0=
k=0
3x
3k
+ (2 + 2Cgan)(CK,
BR -x + CKK
Okk
ak
+ (2 + 2C1000 (CKs
TN -1-- + Cka
- 7xK)
Ok
Okk
+ (LNC + 2011) ax.
(94)
The summation of Ma, can be bounded as
K
M
2 -wolll + 16N
BI
+ +8 N8VNCsu Ae
Br Re
0=0
1=0
K
2
k
Σ
ukc -2 wwol? + 16NC
Σ
h-t Ko
-1
+ +8VNCsuk -138
Σ
R-t Ko
k=0
1=0
1=0
(4)
K2
Ke
VRC 1101l 2 + 16NC
+ +8VNCcuuE -1
12 v)2
v(1 v)
(40)
||Wll 1|2
16NC33KK3
Ko
+
+ &CNCC [ul - -v)
12 )2/Ke)²
v2(1-1)
033 O(VK),
(95)
where the second equality is according to the step size choice. (i) is due to
Σ
A-t
Re
Ko x- K.
u(1 - v)
(ii) is due to Σ us arguments, we can show that Σk= Mr2 = O(VK). Therefore, the third term in (94) of order O (())
m( ut/kke The last equality uses Ke O(K2/). By following similar
K
Finally, by noticing Ck, Ollog 1 1,,C, Ollg at C,,,C, O(log a ) Ck, Olog² ).). we obtain the az desired iteration complexity of Ō k or equivalently, the sample complexity of -(s
D.2 Proof of Theorem 2
Define the update of actor using the noisy reward
(Ex = k. (Sk, ax) + 7 Whtn ((5)T( wwyr)
(96)
40

---

Published in Transactions on Machine Learning Research (01/2023)
Following the derivation of (72), we have
N
B[J(0++1] J(Ok)
OCk
V g: [(x)]]
an || (Etx will
0kk
VV g: J(Ox) - Eigh (ER, w M11*]]
2 NC
L
(97)
2
Similarly to the proof of Theorem 1, the gradient bias term can be decomposed
| ((x,) (Eg wt 11ll s 4 J(O,) B[d(ER. On )b) I1|a
[B((((E,, B&) 8(Ek, w" (0x)))) (ox I1I
[I(((((s..""0A)) Ö(Ex, (kks::H41)10 1) 11I
In
(F - Fx (8ks ax wb)
(98)
I1 I2, I3 can be bounded following the derivation of (84), (80), and (82), respectively. Plug these bounds into (97), have
ak B
+ ak 2 Ilo wf+1))? aO wh+2ll?
[[[(0x+1]] ((On) 2
1=1
N
ak
L ( ax) - - #k,,, (sk. ax)l NC
-
2
2
1=1
2NCKs ak ak - 8(esp + Cae Nork
(99)
Define fk,k, = [r,,
I. IT. The reward bias can be bounded as
N
Σ
[i ax) - Fi, (sk) ||QFx,k 112
-IQ Fx.osrr ax)l
2K 1F |F ax) 12
(1ii,o(sk: ax) (5 ax)l || (sk, a+)
< 2K, N(o² + +max);
(100)
where o² is the variance of the reward noisc. Let K, 2 log, ag and define C15 = 0² + 2
Plug (100)
back to (99), we have
[[]((
ag E p: J(xx))
a gl 1111 S05a (0k) wh+1 IP2)
N 2
(Cis + CgL)a - 2NC af ai zx 8(Esp + )aa.
Consider the Lyapunov function
W = -((x) + 1| " (0x))l
41

---

Zx Published in Transactions on Machine Learning Research (01/2023)
The difference between two Lyapunov functions is
N
ak ((
- at 111l wk-
B W+++1]
-
|
2
N
Cloa 2NCK3 ax 8(Eep Cppp Napp))Naa
2
N
8C BCB (8x) - -w/+ w/+i1l B - w (fx+1)ll2 Blia - - w0x))]
Is can be bounded by following the derivation of (90). Thus, we have
E E
N
+ N Cioaj - 2NCK,, ak- 8(Eep + (ppppp)NNn
[Ou)) 2
+ Cgax ( (Ck, BkBx- CK2BRas-2x 2x) Mk.
(101)
L2 23N2
where C1e C1s + CZ +
+ L
Telescoping (101), we have
2E[Vo]
2 K K
B Vo
+ 16(Eep + Cheape N) +
Σ
Mr. + Clbar
Kax
k=
3k Br 3x-2x + CK2
3r akk
+ (1 + C.aa)
CKi
an
The term 2
K Σx= Ms, has been bounded in (95). Let O% = VK will yield the desired rate.
Co for some positive constant ā, Bg = 2X
Ole
E Natural Actor-Critic variant and its convergence
In this section, we propose a natural Actor-Critic variant of Algorithm 1, where the approach of calculating the natural policy graident under the decentralized setting is mainly inspired by (Chen et al., 2022). We show that the gradient norm square of such an algorithm will converge with the optimal sample complexity of Ō(e-3). Morcover, the algorithm will converge the global optimum with the sample complexity of O(e-)). In the rest of this section, we first explain the update of the algorithm, and then prove its convergence.
E.1 Decentralized natural Actor-Critic
The natural policy gradient (NPG) algorithm (Kakade, 2002) can be viewed as a preconditioned policy gradient algorithm, which updates as follow:
Oct1 = 02 Or. F(aa)
(102)
where F(0) E Egwda aa- [v,,s, ())nls,a)) a is the Fisher information matrix (FIM). The natural Actor- Critic (NAC) uses the critic variable to estimate the gradient. The main challenge for implementing NAC lies in the ostimation of the matrix-vector product F( especially under the decentralized setting. The work (Chen et al., 2022) proposes to solve the following subproblem in order to estimate the product in a decentralized way:
h(0x) = arg min for = hht F(0.) VJ(Oa)
(103)
2
42

---

Published in Transactions on Machine Learning Research (01/2023)
Algorithm 3: Decentralized singlo-tinescale NAC
1: Initialize: Actor parameter Oo. critic parameter wo, reward estimator parameter Ao, initial state so, natural policy gradient estimation hg.0-
2: for k == =, -0............................ K 1 do
3: Option 1: Li.d. sampling:
4: ~ nag (:), 0g ~ me, (+|s)), 8841 a())s,,a).
Option 2: Markovian sampling:
6:
No, (+]s)), 8k+1 P(-(sE,
8:
Periodical consensus: Compute ai and Xi by (4) and (7).
9:
for i = 0,... NN in parallel do
11:
Reward estimator update: Update 1 by (8).
Critic update: Update wh+1 by (5).
13:
Actor update:
Collect transition samples based on Markovian/iid sampling. for k' L,... Ka do
15:
Estimate Eer,,, Vn E [Na] using (104).
17:
Update 1a.++1 by (106).
end for
19:
Update 0/-1 by (107).
20: end
21:
end for
Such a problem can be solved by using (stochastic) gradient descent, where the gradient is calculated by F( (((a)). For the centralized sctting, the gradient w.r.t. cach agent can be approximated as N. Em Vo, (sm: a Wo, (sn; an) ' 3 (S,, Wk+1, AR+1). However, when considering the decentralized setting, the term Σn == (Sn, (1sn,an)7)) h = Σ/= 2ig, (s):,n)) an) ht is not accessible for each agent. To approximate this value under the decentralized sctting, agents compute 2 v/o (8ns Th locally and then perform the following communication step for K₂ steps:
W 2 Vn E [Na,, k' = 0..... 1
(104)
As we will see, the value N , converges to En linearly. Thus, the gradient of the subproblem (103) for agent i can be approximated as:
No Σ
N
Vob (NK,K)) Na
wh. (On, an)=n, - gl (Sn: W A1+1).
(105)
Then, each agent i performs the following update for Ka steps to estimate the natural policy gradient direction:
hE II,, (hi - -V (hw,))),
(106)
where is positive constant step size. Since the norm of optimal direction is bounded by Cs. Amax (F)))- project the vector into a ball of norm On for each update. Finally, perform the approximate natural policy gradient step as:
0 = 0 ochhik..
(107)
E.2 Convergence of natural Actor-Critte
In this section, we establish the sample complexity of Algorithm 3. We first introduce an additional assumption.
43

---

Published in Transactions on Machine Learning Research (01/2023)
Assumption 6. (invertible FIM) There erists positive constant AF such that for all policy 8, Amin (F())) 2
(min(F(f))
Xp-
Assumption 6 ensures that F(0) is positive definite so that the problem (103) is strongly convex for all policy. Such an assumption is also adopted by (Chen et al., 2022; Xu et al., 2021; Liu et al., 2020).
We now show the sample complexity of the Algroithm 3 in terms of gradient norm and the global optimality gap. To keep the analysis concise, we will consider the i.i.d. sampling scheme where we can directly sample transition tuples (s. 0, s') from the stationary distribution Mms. Extending the analysis to the Markovian sampling scheme essentially follows the similar technique in AC's analysis, which introduces additional Ollog(=))) ))) error terms caused by Markov chain mixing, and an error of order O due to the mismatch between MT, and da..
Theorem 3. Suppose Assumptions 1-6 hold. Consider the update of Algorition 3 under the i.i.d. sampling. 1
& Let a = VK for some positive constant ā, 3% Co akk I 20% No O(VK), Ka Ollog(K (2)) Ke = Ollog(<1/4)) Then, the following hold
K
1 VK
(o 50
+ +EEapp + Eep)
(108)
k=1
1=1
K
((0") ((Ox) S 0o K1/44
+ O(Epp + Exp + Eactor).
(109)
K
k=0
The eтror Eopp and Exp are defined in (12) and (4.2), respectively. The error Sactor is referred as "compatible function approximation crror', which is defined as:
Eactor == max min E Esndy aooo ((bb ( Ano (s,
d
Such an error captures the expressivity of the policy paramotorization class: it mcasures the error of approximating Ano (8,a) using (o a) as feature. The error becomes 0 when using the softmax-labular parameterization; see more discussions Section 6 of (Agarwal et al., 2019).
Based on Theorem 3, Algorithm 3 needs K ((E=²) iterations to achieve E-crror for gradient norm square, and thus attains the sample complexity of KN, complexity of NAC (Xu al., 2020; Chen et al., 2022). In terms of the global optimality gap, the algorithm requires K = 0( 4) iterations to achieve E-error, and thus has the sample complexity of KN& = Ö(= Such a sample complexity is worse than the best existing sample complexity of ((e-3) (Xu et al., 2020; Chen et al., 2022).
Ō(e-)), which matches the best existing sample
We now explain the gap for the sub-optimal sample complexity. Mimicking the analysis of (Chen et al., 2022) allows to establish the following incquality:
K Σ J(0)) ((0))))(0))
BII ((w))11
K
K
N
+
Ellug - (+x0) +
(110)
K
Kay
While our analysis can obtain the iteration complexity of O(7 for (Ox)() can only achieve O iteration complexity for critic's error ||m - (fx)). This is because our algorithm uses single-timescale update, where the critic's error inevitably converges slower than that of double-loop based algorithms which have ((+ complexity for the critie's error each iteration. Therefore, the sample complexity in terms of global optimality gap of our single-timescale NAC is dominated by this critic's error term, resulting in the final complexity of Ö(E-9). Nevertheness, the bound (110) is not necessarily tight. We leave the research on the tight. bound of single-timescale NAC future work.
(()))))
44

---

Published in Transactions on Machine Learning Research (01/2023)
E.3
Proof of Theorem 3
By Lemma 4, we have
L
[[ -((m)) ((la)BB(VA (1) -0)
0x) 2 1100+1 0xl1
2 a,B(Vo - -
NNCRaa
-
- (0)) 9a Wk An+1))
L
+ +o..(Vo. F(OR) - (EN: Wk Ak+1)) NC
(4)
oLE(F((A) 1/2 (0) 112 Da (Ek Wk+1 Ax+1))
1/2
L NC
to h4 F(Ox) - 9a Wk-1 )x+1))
2
2 -1 v.
1/2BB/g wk+1 A I|1
2 -11110)) 1.2 =(Ox) 1/2 (Es, 1 111 2
Wh ga )R+1)) L
+ (V A4 - =(xx)= -t (Ex.
NC
((8)
0k C VoJ(ss))
aA AF (841,
2
4
2
a
XF (ok) - FEgo (Ex wk+1 )|1?
2
L NC 2
4ox C
[[( - F(Ox) (Egg WK+1, A- i]lI
(111)
where (i) is due to |0 0l S == = Note that we use h to represent hj K, for simplifying the notation. (ii) uses decomposition of positive definite (PD) matrix. Specifically, let A be PD matrix, then by eigenvalue decomposition, = VAVT for some orthonormal matrix V. Define 1-1 := VA-1/2VT, then (x. A (-)) (A 1/2 A A-1/ for any x and y. (iit) uses Cp S X(F(0)) -1 S XF and Young's incquality. Ii represents the error of gradient bias, which we have bounded when analyzing the error of AC. By (84), we have
1 1 Σ [16(Eep ChEup) 160 (fx) wf (C 1
(112)
To bound 12, we need to bound the error hx We start with the gradient bias when estimating hx Define Vkk (hx,v) = (F(O))ha. (Egga(E,, 1 M+t1), then is easy to see that V (hv,w) is the unbiasod gradient of the following problem
h VF(B)). (Eg. wh+1 ((+1)) hy.
Define the following notation for the ease of expression:
1 No
(h =
Σ
Vig (8ns dhe (8ns an) Th - gf (E,, whe1 Mbr1)
N,
n=1
fee (ho.er) fh, .......,f F.N
N.
N
Σ
Vag (Sn; o lE where Nb41)
No
Vi (be.r) = (BEN) (ha,o))
45

---

Published in Transactions on Machine Learning Research (01/2023)
We now analyze the error at outer-loop iteration k. For notational simplicity, we omit the subscript k for the prementioned notations, e-g. we use (hw), (he)), (fg)))) Vie (har) to represent the above notations, respectively.
(wx.)) Fh. $ (h.:))))) +2 f
f (hx) f.
1s
14
13 can be bounded as
13
(o an (snn) F(0)) 1|²
No
N
(ann an an) - F(O)
Na
1
h.
(113)
No
Ia can be bounded
N
N₂
14
Σ
Vo
(Sn; ann)
N - 1h0 an) an) Ts
Na
1=1
N No
1
NC
1z. - =n.K.ll
N.
1=1 n=1
NC
IIQ 2n.ull 1
No
NC w
Na
Σ
Ks ||2,,,001 NNC.RRK.
(114)
Na
Let K2 minfc N+ <
N.N b then K2 = O(log N.). Combine (113) and (114) gives us
4C C2
- (ww
N₂
We now analyze the error of ha. Note that we omit the subscript here for simplifying notation. Define
h arg min fo(h) = h2 F(0)h (s., A)
(115)
h
It is easy to see that the function on the RHS is strongly convex, since F(O) is positive definite w.r.t. h. We bound the optimal gap by
E Ele
h 112
E| hy e (k 10112
ho 11111 22lE(hw
h", V fwr (hw )) + V )12
S El hy - h=112 20 h- f (hw))) + 20E - h², fh - fck((hw)
2 V fer (hx 2112 + 20 fk. (h+r) V fix (h+: )12
(
$ (1 edp E A 112 20( (lw)) - -F + 2ow h" (he()) Fix
+ 20 V (1 2112 + 20 Ix (hw))) VIx )1
46

---

Published in Transactions on Machine Learning Research (01/2023)
(3))
- (1- Bllhh - 200f-22(11-3 200 (hw) - F)
+ +20R(hx - 11";,"", (hx) (hxx()x))) + 20 11 SK. (hw) - V Scx
(00)
(1 gxF B ha - 1²12 + + - h-, fh - (hw))
+ 22² / L (1x:) - V. (wx)))
(1 - QAF
BBllh - 1012 + ( 20
+ 22²²) fl (hw-)
2
where F" is the optimal value of (h) defined in (115), and the incquality follows the property of Xp-strongly convex function: [(h2)= 2 [(hi)) + (VI h2 - h2) + Ae [|h - he2l?, Vh,, ho. (ti) uses the PL condition
implied by Ap-strong convexity: f(h)) f(h) S 2AP IVS(0)3 Vh. (iii) is due to step size rule that
e शे.. (iiti) applies Young's inequality.
Use the above induction, we have
K,
edR Kg 1h-1 - 11111 + >
OA
20
E BlIK, - 111112= S (1
(1
2 )r( dr
+ +20²) Vok VSK, (1x,))l
2
s <4 OdR jke )
40
40
J Ch No
4
+
AF
Let Ka = minfc e N+14C% -
2
4p
+
4e Ar
C C+ J. then Ka Olog(( Nt))). Define Cis :=
2
( + Xr 120 we have exp
2C18 N₂
1/ = Ellk. - 111122 <
(116)
Plug (112) and (116) back to (111), we have
[[J(0++1]] - -J(x)) 2
N
Okk
- vo.
+ as (r(1F((p))
"EE' (6,, 1 1111 + C
201s
4
2
Na
8AP (Eap + ChEapp) + 2 wf-+ 4Xp C31 \1+1
Consider the Lyapunov function
v* = =-(kk) + Xp (lwwk - (Bx))1 +11e (
The difference of the Lyapunov function is
B|yA+1] B = [()()+)] - E[J(Ox+ X - w (0++1)ll Ellaa ~ (0x))l
+ B A2+1 - X'(0++1)l' 112 - -EIIAE - (0x)
ak cT E V J(Bx)) + A5 [F(x)) " (Ex, (f of
21 + 02 2C18
No
+ x
Σ
8C SC (0&) wh+ 11 Bl w (0x+2))1 - w (B&b)1
N
+ x
Σ
B0 - 11 + E A'(0x+1)11 -B]A - -x
1=1
+ 1 + Cheapp).
(117)
47

---

Published in Transactions on Machine Learning Research (01/2023)
By following the similar procedures through (87) to (91), we can bound Is and Is
Is 5 (1 C394)
ak
x
E (((x)) (En wh+1 111 + ag + C2oa
(118)
4
I8 $ C2
ak
E F((x) 9
2111 + ax + Craak (Ex, -
(119)
4
where C19, C2o, C21, C22 are some positive constants. Plug (118) and (119) back to (117), we have
E V Von + C 20
E - E
+ +O(a + 3 m
No
+ (Mxz + May + O(Epp + Eapp)ask
(120)
By telescoping (120), can get
1 Σ Σ
VC
8C2C1s
O(ax + P
n
E J(
+ OEEp + Eapp) +
Ka
No
akk
k
+ 4C
2 (Mr, + Max) k=0
# K
By (95); Mr + MR, =0 1 vK
when K. O(K1/)) Therefore, let C, ã be some positive constants. Set
N₂ CVK, an VK' Bk
Co U7
Cia ag, we obtain the desired result of (108).
2h
ak:
2xp
We now prove (109). Let Eg- denote the expectation over ~ drg.: ~ To- (-18). By the smoothness of log (a(ss), we have
Eg- llog To.., (als) loog To, (a|s)]
2 ax (io. (s, a5.a)² )2thp] h4] L C²
2
2 au (ob, (8, (5,aaT((a,
11" (0x))) Eg (1 (s,
a C2
- Fo [Ao, (8,
2
L a C2.
2 2-acC 11" (0x)ll - ak EEccoo + -x(()()))((1))
2
By telescoping the above inequality and rearranging terms, we have
K EJ((0) -((x)) S
Eg- [log T (a/s)
log (alss) + Eeacoor
K 1=1
Ko
K
Lyak
C Chl (0x))l
K
km
The term ||Ae 1a (0x) S |1 -
Wk+1, A++1 1]ll + |[]]a Wk+1, \x+11 -F-VJ Since by the (116) and (84), these two terms are of order O NT/z and O(I Wh+1| Eapp); respectively, we conclude that || 1 h²" (0x) is of order O(I w" (0x) Eapp). By following the step size rule suggested by Theorem 3, obtain the desired result.
48


Reviews:
[{"review_id": "5T3pMvrMa4", "reviewer": "Reviewer_LYfg", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n\nTo my best knowledge, it seems the first paper achieving the sample complexity of O(\\frac{1}{\\epsilon^2}) using a single-timescale algorithm with either iid or Markov sampling in the fully decentralized cooperative MARL.\n\nWeakness: \n\nIt seems the proof techniques are not very new. From my understanding, the key analysis is from [1], and the main non-trivial contribution compared with [1] is to verify that the Jacobian of the stationary distribution is indeed Lipschitz, which is the assumption 10 (ii) and not verified in [1]. Other than that, the algorithmic techniques to extend the algorithm for single-agent [1] to fully decentralized cooperative MARL such as consensus update and reward estimator/noisy rewards seems common in existing literature [2, 3].\n\n\n[1]. Chen, Tianyi, Yuejiao Sun, and Wotao Yin. \"Tighter analysis of alternating stochastic gradient method for stochastic nested problems.\" arXiv preprint arXiv:2106.13781 (2021)\n[2] Zhang, Kaiqing, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Basar. \"Fully decentralized multi-agent reinforcement learning with networked agents.\" In International Conference on Machine Learning, pp. 5872-5881. PMLR, 2018.\n[3] Chen, Ziyi, Yi Zhou, Rong-Rong Chen, and Shaofeng Zou. \"Sample and communication-efficient decentralized actor-critic algorithms with finite-time analysis.\" In International Conference on Machine Learning, pp. 3794-3834. PMLR, 2022.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the actor-critic methods in fully decentralized MARL. Compared with existing works, this work makes main contributions in the following sense:\n\nA. Single-time algorithm instead of double-loop or two-timescale fashion\nB. Considers the more practical markovian sampling and i.i.d sampling\n\nIt maintains the state-of-the-art sample complexity O(\\frac{1}{\\epsilon^2}) and demonstrates the effectiveness of the algorithm through experiments in the grounded communication environment, showing improved sample and communication efficiency.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "In order to highlight the contributions of this paper, I suggest the authors discuss the main technical difficulties for (1) extending the algorithm for single-agent RL to fully decentralized MARL (2) using markov sampling. Discussing how the standard techniques for (1) and (2) will or will not be different when using a single-timescale algorithm can make the contribution of this paper clearer.\n\n**Post rebuttal**: I would like to thank the author(s) for providing the detailed rebuttal, and I think they generally make sense. I have also checked other reviewers' comments, and still have a bit of concern about the technical novelty and significance of the work. I would suggest a borderline acceptance post-rebuttal.", "broader_impact_concerns": "No.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "kYiQ9YqUXd", "reviewer": "Reviewer_tG2W", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I do not think this paper provides convincing motivation for studying single-time scale actor-critic algorithm. In practice, people often train actor and critic for a different number of steps per update, even if they use the same-scale learning rate. Therefore, I don't think it is useful to study the setting where the actor and critic have the same-scale learning rate and the same number of updates per inner loop. \n\nThe proof techniques are quite standard and well-known. The analysis simply blends the existing ideas for distributed optimization and policy optimization, under the assumption that the Markov chain is irreducible and aperiodic for any policy and every policy has a lower bounded probability to pick any action at any state. \n\nThere is also a considerable number of typos in the submission, e.g., in Theorem 1 function $F$ is used without defining it. \n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies decentralized actor-critic algorithm which uses the same learning rate for actor and critic. By using linear approximation for value and reward estimation, they obtained $1/\\epsilon^2$ sample complexity guarantee. \n\n", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I think this submission is just another A+B paper which doesn't provide much useful information to the community. And I don't think any revision could change such nature.", "broader_impact_concerns": "I don't foresee any such concerns.\n\n\n=============\n\nPost rebuttal: I appreciate the authors' detailed response to my comments. After reading the author response and other reviewers' comments, I agree that there is indeed something new in this work compared to the existing ones. Nonetheless, I am still quite suspicious about the overall novelty of the analysis, and feel (just my own research taste) this single-timescale feature is a rather minor point due to its inconsistency with common empirical RL. As a result, my overall recommendation is borderline reject.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "eTur8mfBTi", "reviewer": "Reviewer_VYyQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- The authors characterize a tight convergence bound\nWeakness: \n- The paper lacks novelty.\n- The results are for convergence to stationary point, and even for that, the upper bound involves constants which do not go to zero.\n- The convergence bound provided in the paper is based on average of gradients of the algorithm over time. The authors claim that single time-scale algorithm which is studies with them do not require careful design of the parameters. However, for one, the choice of the step size \\alpha_k depends on the horizon, and also the bound is on the average of the gradient of the points observed so far, which means we need a uniform sampling of time step from 1 to K. Hence, their criticism for two-time-scale algorithms is not valid.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the Finite-Time convergence of Decentralized Single-Timescale Actor-Critic and Natural Actor-Critic algorithm. In this setting, we have A agents where each of them take actions a^1, ..., a^N separately according to their local policies parameterized by theta^1, ..., \\theta^N, and each agent receive separate rewards. The goal is to find the optimal joint set of parameters \\theta^1, ..., \\theta^N which results in the maximum cumulative discounted reward. \nThe authors provide two algorithms for finding the optimal policy. In the first algorithm, we estimate the reward function of the agents separately, and we use this reward function approximation to find the optimal policy. However, this algorithm requires the knowledge of individual actions of the each agent, which might violate the privacy. For that, the authors further propose algorithm 2 which adds some noise to the reward function before sharing it with the other agents. However, this algorithm requires the agents to communicate log(1/\\epsilon) times more.\nFinally, the authors characterize the sample complexity of Algorithms 1 and 2. At the end the authors provide experimental results for their algorithm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- In the bounds of Theorems 1 and 2 there is term O(\\epsilon_{sp}), which is essentially a constant. This constant is not acceptable when we characterize an upper bound. Even though the authors argue that this term goes to zero as \\gamma-->1, but still it is a constant which is not even dependent on the function approximation error. Can the authors get rid of this term?\n- Furthermore, on the paper \"Actor-Critic Algorithms \" by Konda and Tsitsiklis, the authors characterize convergence to stationary point of actor-critic algorithms. In this paper, however, we do not even have convergence to stationary point, and the upper bound involves \\epsilon_{app} term. Can the authors get red of this term, or argue why it is essential to have this term?\n- Could the authors expand more on Assumption 5? What is the requirement on the upper bound on the second largest singular value mean? Does the assumption more or less require a complete synchronization among the agents every K_c time step? In that case, we cannot assume this algorithm is decentralized, since we need a complete synchronizer, which is against decentralization.\n- Could you explain how the error of Algorithm 2 depend on the \\sigma of the noise added?\n- How do we choose the radius of projection? In the paper you are not mentioning a rule to choose this radius.\n\n---------------------------------------------------------------------------------------------------------------------------------------------------------\nComments after reading the review:\n- The reference to the paper [Konda et al., 1999] is not accurate. As long as I understand, [Konda et al., 1999] does not require the function approximation error to be zero. So my question regarding function approximation error for convergence to the stationary point remains.\n- The argument provided by the authors for why $\\varepsilon_{sp}$ is inevitable, is not satisfactory. There might be ways to get rid of this term. Either by changing the algorithm, or by a finer analysis.\n- In the case you need to know the horizon before hand to tune the parameters, then we do require careful design of the parameters, and the point mentioned in the paper for the advantage of single time scale algorithm is no longer valid. \n\n---------------------------------------------------------------------------------------------------------------------------------------------------------\nThe second round of responses, and the changes the authors made to the paper addressed my main concerns. I do not have crucial concerns anymore.", "broader_impact_concerns": "No broader impact concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies finite-time convergence of decentralized actor-critic in multi-agent reinforcement learning, which uses single-timescale updates. This kind of update is simpler than two-timescale updates, but has limited theoretical understanding in its convergence behavior. The work is solid, although there are concerns with technical novelty. The author response clarified some of the issues. Furthermore, given popularity and simplicity of single-timescale updates, the results are interesting and relevant, and I’m happy to recommend acceptance.

Minor suggestion for the final version: There is no need to submit the main paper and appendix in separate files. They can be merged into a single file.
Decision: Accept (poster)