Achieving Communication-Efficient Policy Evaluation for Multi-Agent Reinforcement Learning: Local TD-Steps or Batching?
Authors: FNU Hairi
Zifan Zhang
Jia Liu
Venue: Submitted to ICLR 2023 (2023)

Abstract: In many consensus-based actor-critic multi-agent reinforcement learning (MARL) strategies, one of the key components is the MARL policy evaluation (PE) problem, where a set of $N$ agents work cooperatively to evaluate the value function of the global states under a given policy only through communicating with their neighbors.
In MARL-PE, a critical challenge is how to lower the communication complexity, which is defined as the rounds of communication between neighboring nodes in order to converge to some $\epsilon$-stationary point.
To lower communication complexity in MARL-PE, there exist two ``natural'' ideas: i) using batching to reduce the variance of TD (temporal difference) errors, which in turn improves the convergence rate of MARL-PE; and ii) performing multiple local TD update steps between each consecutive rounds of communication, so as to reduce the communication frequency.
While the effectiveness of the batching approach has been verified and relatively well-understood, the validity of the local TD-steps approach remains unclear due to the potential ``agent-drift'' phenomenon resulted from various heterogeneity factors across agents.
This leads to an interesting open question in MARL-PE: *Does the local TD-steps approach really work and how does it perform in comparison to the batching approach?*
In this paper, we take the first attempt to answer this interesting and fundamental question.
Our theoretical analysis and experimental results confirm that allowing multiple local TD steps is indeed a valid approach in lowering the communication complexity of MARL-PE compared to vanilla consensus-based MARL-PE algorithms.
Specifically, the local TD steps between two consecutive communication rounds can be as large as 
$\mathcal{O}(\sqrt{1/\epsilon}\log{(1/\epsilon)})$ in order to converge to an $\epsilon$-stationary point of MARL-PE. 
Theoretically, we show that in order to reach the optimal sample complexity up to a log factor, the communication complexity is $\mathcal{O}(\sqrt{1/\epsilon}\log{(1/\epsilon)})$, which is *considerably worse* than TD learning with batching, whose communication complexity is $\mathcal{O}(\log (1/\epsilon))$. However, the experimental results show that the allowing multiple steps can be as good as the batch approach. 

Under review as a conference paper at ICLR 2023
ACHIEVING COMMUNICATION-EFIICEN POLICY EVALUATION FOR MULTI-AGENT REINFORCEMENT LEARNING: LOCAL TD-STEPS OR BATCHING?
Anonymous authors Paper under double-bling review
ABSTRACT
In many consensus- actor-critic multi-agent reinforcement learning (MARL) strategies, one of the key components is the MARL policy evaluation (PE) prob- lem, where set of N agents work cooperatively to evaluate the value function of the global states under a given policy only through communicating with their neighhors. In MARL-PF,, a critical challenge is how to lower the communica- tion complexity, which is defined as the rounds of communication between neigh- boring nodes in order to converge to some e-stationary point. To lower com- munication complexity in MARL-PE, there exist two "natural" ideas: i) using batching to reduce the variance of TD (temporal difference) errors, which turn improves the convergence rate of MARL-PE; and ii) performing multiple local TD update steps between each consecutive rounds of communication, so as to reduce the communication frequency. While the effectiveness of the batching ap- proach has been verified and relatively well-understood, the validity of the local TD-steps approach remains unclear due the potential "agent-drift" phenomenon resulted from various heterogeneity factors across agents. This leads to an inter- esting open question in MARL-PE: Does the local Tt-steps approach really work and how does it perform in comparison to the batching approach? In this pa- per, we take the first attempt to answer this fundamental question. Our theoretical analysis and experimental results confirm that allowing multiple local TD steps is indeed a valid approach in lowering the communication complexity of MARL- PE compared to vanilla consensus- based MARL-PE algorithms. Specifically, the local TD steps between two consecutive communication rounds can be as large as O( OVVI/clog (1/c)) in order to converge to an c-stationary point of MARL- PE. Theoretically, we show that order reach the optimal sample complexity up log factor, the communication complexity is O log (1 (1/e)). which is worse than TD learning with batching, whose communication complexity is (log(L/e)) However, the experimental results show that the allowing multiple steps can be as good as the batch approach.
INTRODUCTION
1) Background and Motivation: With the recent success of reinforcement learning (RL) (Sttonn & Barto 2018) techniques in the dynamic decision making process where the underlying model is unkown, MARL, a natural extension of RL to multi-agent systems, has also found increasing applications. Compared to traditional RL, the richness of multi-agent systems has given rise far more diverse problem settings in MARL, including cooperative, competitive, and mixed MARL (see Zhang al., 2021a) for an excellent survey). In this paper, we are interested in cooperative MARL, which has found wide range of applications in the field of networked large-scale systems, such as power networks (Chen et al.) 2022, Riedmiller et al. 2000), autonomous driving (Yu et al. 2019) Shalev-Shwartz et al. 2016) and so on. A defining feature of cooperative MARL is that all agents in the system collaborate to learn a joint policy to maximize long-term system- wide total reward through communicating with each other. However, due to the decentralized nature (i.e., lack of centralized infrastructure) of cooperative MARL, the collaboration between the agents can only rely on some algorithmic designs induce "consensus" that can be reached by the agents.

---

Under review as a conference paper at ICLR 2023
In many consensus-basee based actor-critic MARL strategies, one of the key components is the MARL policy evaluation (PE) problem, where a set of N agents work cooperatively to evaluate the value function of the global states for given joint policy. Just as in the PE problem of conventional RL, temporal difference (TD) learning (Sutton 1988) has been the prevailing method for MARL-PE thanks to its simplicity and empirical successes in real-world applications. Simply speaking, the key idea of TD learning is to learn the value function by using the Bellman equation to bootstrap from the current estimated value function. However, as mentioned earlier, the decentralized nature of the MARL-PE problem necessitates communication among agents for TD learning. Hence, critical challenge in consensus-based MARL-PE is how to lower the communication complexity, which is defined as the required rounds of communication between neighboring agents in order to converge to some e-stationary point of the MARL-PE problem.
To lower communication complexity for solving MARL-PE problems, there exist two "natural" ideas: i) using batching of trajectory samples reduce the variance of TD errors, which in turn im- proves the convergence rate of MARL-PE; and ii) using an "infrequent communication" approach where we perform multiple local TD update steps between each consecutive rounds of communica- tion to reduce the communication frequency. While the effectiveness of the "batching" approach has been verified and relatively well-understood (Hairi et al., 2022] Chen et al., (022), the validity of the "local TD-step" approach remains unclear due the potential "agent-drift" phenomenon resulted from various heterogeneity factors across agents (more on this soon). This leads to two interesting open questions: 1) Can the local TD-steps approach really lower the communication complexity for solving MARL-PE? 2) If the answer to 1) is "yes," how does the local TD-steps approach perform in comparison to the batching approach? Answering these two questions from both theory and in practice constitutes the main goal of this paper.
Answering the above questions is highly non-trivial due to several tech- nical challenges in the convergence analysis of the local TD-steps approach. Notably, it is easy to see that the structure of TD learning consensus-based cooperative MARL resembles that of decentralized stochastic gradient descent (DSGD) method in consensus-based decentralized opti- mization(Nede Nedic & Ozdaglar 2009)] Lian et al. 2017: Pu & Nedie 202I). Thus, it is tempting to believe that one can borrow convergence analysis techniques of DSGD and apply them in TD learn- ing. However, despite such similarities, there also exist significant differences between TD learning in MARL and DSGD.
2) Technical Challenges:
Structural Differences: First, we note that TD learning is not true gradient-based method, since TD error is not a gradient estimator of any static objective function as in DSGD, which is well defined in consensus-based decentralized optimization problem. Also, in decentralized opti- mization, the gradient terms are often assumed to be bounded. However, in TD learning, the TD-errors can not be assumed to be bounded without further assuming that the value function approximation parameters lie in some compact set.
Markovian Data in TD Learning: In RL/MARL problem, there exists an underlying Markovian dynamic process across time steps, where the state distribution may differ at different time steps. By contrast, in decentralized optimization, it is often safe to assume that the data at each agent independently distributed. Thus, it is not applicable directly use convergence analysis tech- niques of decentralized optimization in TD learning for MARL-PE. The coupling and dependence among samples renders the convergence analysis of TD learning in MARL far more challenging.
"Agent-Drift" Phenomenon: Due to heterogeneity nature of the rewards across agents, executing multiple local TD update steps would inevitably pull the local function approximation parameters toward the direction of approximating local value functions rather than the global value function, leading to the "agent-drift" phenomenon. Hence, it is unclear whether such local steps help or hurt the convergence of TD learning in MARL. Intuitively, if the agent-drift is too large, then the low communication-come compllxxit benefit of infrequent communication might be offset by the errors in aligning the local model parameters at each agent to the true global value function parameters. Because of the agent-drift effect, the number of local TD update steps has to be chosen judiciously to mitigate the potentially large divergence of the function approximation parameters between each communication round.
3) Main Results and Contribution: The main contribution of this paper is that we overcome the above challenges in analyzing the communication complexity of the local TD-steps approach for cooperative MARL-PF. By doing so, are able shed light on the feasibility and effect of local
2

---

Under review as a conference paper at ICLR 2023
TD steps in the consensus- based TD learning in the MARL-PE problem. We summarize our main results in this paper as follows:
Both theoretically and empirically, we show that allowing multiple local TD steps is indeed a valid approach that can significantly lower the communication complexity of MARL-PE com-
decentralized TD learning algorithms Doan et al. (2021] 2019); Zhang al. ( Specifically,
pared to vanilla consensus-
show in theory that under the condition of achieving OL/e log- (1/e)) sample complexity (which differs from the state-of-the-art sample complexity only by a log factor), the local TD-steps approach can allow up O( O(v log(1/e)) local steps and the communication complexity ( log(1/e)), Compared to vanilla algorithms, this improves the communication complexity by a factor of O (VV//e).
Moreover, we show in theory that although executing multiple local TD steps improves the com- munication complexity significantly, its improvement may not be good as that of the batch approach under the same sample complexity condition Hairi et al.] (2022); Chen et al. (2021), Specifically, by choosing the batch size be ((1/c) the communication complexity of the batch- ing approach can achieve (loo(1 /c)). This indicates that the local TD-steps approach "helps." but may not as much as the batch approach.
Although the communication complexity bound relatively worse, the extensive empirical re- sults show that the performance of the local TD approach can be comparable to that of batching approach both in synthetic and real-world setting.
The rest of the paper is organized as follows. Section 2 we review the literature to put our work in comparative perspectives. In Section we present the system model and formulation of the MARL- PE problem. In Section 4 we introduce the decentralized TD learning algorithm with multiple local TD steps for MARL-PE. In Section we provide the theoretical convergence analysis for the decentralized TD learning algorithm with multiple local TD steps. Section a presents numerical results and Section 7 concludes this paper. Due to space limitation, some proof details are relegated to the supplementary material.
RELATED WORK
In this section, we provide an overview on two lines of research that are related to this work: MARL-PE and ii) single-agent RL policy evaluation.
1) Multi-agent reinforcement learning policy evaluation: To our knowledge, the work in Zhang et al. 2018)) proposed the first fully decentralized multi-agent actor-critic algorithm using TD learn- ing in the critic step, which solves the PE problem. However, the convergence results for both its critic and actor steps are asympiotic. Finite-time analysis of MARL-PE problem using distributed TD learning algorithm has been first studied in (Doan et al. 2019) under the i.i.d. sampling assump- tion. later the work in (Doan et al. 2021) generalized the result to Markovian sampling assumption. In (Lin et al. 2019). a compressed algorithm is proposed where, instead of sending a vector, only a single entry sent during communication is proposed. However, their communication complexity (i.e., the number of communication rounds) remains the same as sample complexity and the con- vergence is only asymptotic. In (Chen al. 2018). lazy communication algorithm proposed assuming a central controller, which is different from the fully decentralized setting we consider in this paper. There exists another class of approaches (Zhang al. 20216 Macua et al. 2014 Lee et al. 2018 Wai et al., 2018 Ren & Haupt, 2019) that solve MARL-PE problem by formulating into optimizing projected Bellman eтror
variants, where the proposed algorithms require frequent communication. This class of algorithms do not use the on-policy TD learning approach as we in our paper. In (Kim et al. 2019), the paper optimizes communication in order to comply the bandwidth restriction and minimize the collision between pair-wise channels. However, the work adopts centralized learning and distributed execution paradigm, where in our paper, the learning process is fully decentralized.
However, most of the existing distributed TD learning algorithms (Zhang et al. 2018 Doan et al. 2019 2021) for MARL perform frequent consensus rounds (i.e., one round of communication per local TD update) to share the approximation parameters among neighbors. Specifically, in these algorithms, agents share the parameters to their neighbors in every time step, which causes the
3

---

Under review as a conference paper at ICLR 2023
communication complexity to be the same as the sample complexity. In this paper, consider an infrequent communication framework that allows the agents to do multiple local TD learning steps and share the value function approximation parameters one every K(> 1) rounds. In (Haini et al., 2022; Chen et al. 2021), complete actor-critic algorithms have been proposed and batching approach has been used in the critic step, which corresponds to MARL-PE, In such batch approach, consensus is performed in every M = cc/e batch samples, which in turn only requires Olog 1/e) communication complexity. To investigate the effect of such local steps solely, do not consider further modifications of batching as in Xu et al., 2020 Hairi et al. 2022; Chen et al. 2021).
2) Single-agent reinforcement learning policy evaluation: For single-agent RL, policy evaluation problems have been extensively studied in terms of asymptotic convergence (Tiissiklis & Van Roy)
1997 1999 2002), finite-tine thite-time convergence under i.i.d. sampling assumption Lakshminarayanan &
Szepesvani 2018) and under Markovian sampling assumption using different techniques (Srikant
& Ying 2019 Bhandari et al.) 2018). Further, using batched TD learning (Xu et al. 2020) yields state-of-the-ar sample complexity (((1/e) log() However, there is no notion of "communi- cation with other agents" due to the single-agent nature. Thus, results in this area are not directly comparable our work.
3 DISTRIBUTED POLICY EVALUATION IN MULTI-AGENT REINFORCEMENT LEARNING
Throughout this paper, || denotes the f2-norm for vectors and the fz-induced norm for matrices. || denotes the Frobenius norm for matrices. (.)² denotes the transpose for matrix or vector.
3.1
SYSTEM MODEL
Consider a multi-agent system with N agents, denoted by N {1,..... ......,, NN), operating in a net- worked environment. Let & be the edge set for given network g (N. E). To formulate MARL problem and facilitate our subsequent discussions, we first define the notion of networked multi-agent Markov decision process (MDP) as follows.
Definition 1 (Networked Multi-Agent MDP). Let G (N,E) be communication network that connects agents. A networked multi-agent MDP is defined by following six-tuple (S, {AtheN P, (R' Hev, he 9, where S is the global state space observed by all agents, A is the action set for agent i, :::.. x A x S [0. 1] is a global state transition function, R' S x A the local reward function for agent i, and 7 E (0, 1) is the discount factor. Let A = IlieN A' be the joint action set of all agents.
In this paper, we assume that the global state space is finite. We also assume that at time step I. 2 0, all agents can observe the current global state 8t. However, each agent can only observe its own reward ri, i.c., agents do not observe or share rewards with other agents at time t. The reward function (s, a) is expectation given and a, and the instantancous reward is denoted by r' (s, a). i.c., R (s, a) = as)'
We consider policies that are stationary. In our MARL system, each agent chooses its action follow- ing its local policy xO that is conditioned on the current global state s, i.e., x <aaa)) (a'Is) is the probability for agent to choose action at E A'. Then, the joint policy æ S x A + [o. can be written as T (als) = IlEN x' (a*1s).
The global value function for all S is defined as follows:
V(s)
E
r r'sst (0)
N
VEN
3.2 TECHNICAL ASSUMPTIONS
We now state the following assumptions for the MARL system described above.
Assumption 1. For the given policy म, we assume the induced Markov chain {sth2 is irreducible and aperiodic.
4

---

Under review as a conference paper at ICLR 2023
Assumption 2. The instantaneous reward ri is uniformly bounded by constant Xmax for any i E N and 2 0.
Assumption 3. Let A be consensus weight matrix for given communication network G. There exists a positive constant 7) > 0 such that E xgN is doubly stochastic and A 2 7h Vi N. Moreover, A.j 2 1) if i. j are connected, otherwise A,
Assumption 4. The global value function is parameterized by linear functions, i.e., V(s: ((s)² w where d(s) [o1 (s),... da(s))²²
_ E I is the feature associated with the state E 8 and < |S]. The feature vectors (bs) are uniformly bounded for any E S. Without loss of generality, we assume that ||((()] < Furthermore, feature matrix RRSSxdd full column rank.
Assumption 1 guarantees that there exists a unique stationary distribution over S for the induced Markov chain by the given policy л. Assumption ii common in the RL literature (see, e.g., (Zhang et al. 2018 0 Xu et al. 2020] Doan et al. 2019) and easy to be satisfied in many practical MDP models with finite state and action spaces. Assumption i standard in the distributed multi-agent optimization literature (Nedic & Ozdaglar 2009). This assumption says that non-zero entries of
the weight matrix A needs to be lower bounded by positive value r). Assumption 4 on features is standard and has been widely adopted in the literature, c.g., (Tsitsiklis & Van Roy [999] Zhang
et al. 2018: Qiu et al. [022]] Srikant & Ying 2019). The goal of this assumption is to approximate the value function as follows:
V(s) R ((s; w) = ó(s)"
where ((s) is the feature associated with state s E S. As a result, V (s; = ols) for all s S.
DECENTRALIZED TD LEARNING WITH LOCAL STEPS FOR MARL
In this section, introduce the decentralized TD learning algorithm with local TD steps (i.e., in- frequent communication), which illustrated in Algorithm | Given a policy म, the goal of the MARL-PE in the decentralized setting is to collaboratively characterize the value function. Specifi- cally, each agent maintains a value function approximation parameter w locally, which estimates the global value function follows:
V(s; w/) wws)
Our algorithm is designed with two loops. The outer loop is the communication rounds, where consensus update (Line in Algorithm [ performed for L rounds. The inner loop is local TD update steps, which consists of K steps. Locally, each agent performs local TD learning updates within each communication round 0 E S
as follows:
wi,t+1 wf,x + 3 0i ((81,x);
where / > 0 is the step size and 8î is the local TD error, which is defined as follows
6, == rl,+1 + + ((.,))
We note that equation] 1 iis considered one local TD learning step. Within each inner loop, this local TD update step is done K times.
Due to the privacy of the reward signals in the fully decentralized setting, the agents are unable to access the rewards any other agents, let alone the average rewards. Therefore, communi- cation/sharing of the value function approximation parameters among the neighbors is necessary (Zhang et al. 2018 Doan et al., 2019 Chen et al. [021 Hairi et al. 2022). This step is also referred to as consensus update, which can be typically done follows:
w
Σ
Ay
JEN;
In other words, after performing K local TD steps, each agent shares its parameter to the neighbors, receives the ones from the neighbors, and then updates its own parameter a weighted aggregation as shown in equation 2 We note that in our algorithm, the infrequent communication is done by agents communicating only periodically with the period being K. The decentralized TD learning with periodic local steps is concluded in Algorithm I We also note that when K 1, our algorithm reduces to the vanilla distributed TD learning algorithm (Doan et al. 2019 2021 Zhang et al. 2018). Hence, the vanilla distributed TD learning can be viewed as special case of our algorithm.
5

---

Under review as a conference paper at ICLR 2023
Algorithm 1: Decentralized TD Learning with periodic local steps
Input Initial state π = {~ E W], feature map é, initial parameters (wo E N). step size 8. communication round number L, local step number
for 0,... L do
for k = 0, ... K do
$1,0 = 1, (when 0 and k: = 0, S1,4 = s0);
for all i E N do
Execute action of ~ x' (+100)))
Observe the state S1,+1 and reward ri,--i
Update 8i - ri,t+ + (0(51,4)) wi, (((1
end
Local TD Step: wi,n-1 t wi, + 38 o(sL));
10
end
Consensus Update: 0141,0 EjEN, A(i,5) wi,
12 end
Output: Wr.0
5 CONVERGENCE ANALYSIS OF DECENTRALIZED TD LEARNING WITH LOCAL STEPS
In this section, we present the convergence results for Algorithm which further imply both the sample and communication complexities of Algorithm I
To characterize the convergence, define the following quantities:
V [[(ro(s') of (s)] and b: Blo(s) Er'(s,
(3)
IEN
The expectations in equation 3 are taken over the steady state distribution induced by the policy, which is guaranteed to exist due to Assumption [ stationary action policy a ~ (-1ss, state transition probability s' P(-|s, a), and the reward distributions. Furthermore, define
state
w" -
where the invertibility is due to being negative definite (Tsitsiklis & Van Roy 1997. quently, we define mixing time r(3) follows
Conse-
v E((( ((s))) (s)]s0 *]1 B Vs, Vk 2 ((3)
(5a)
1 N B(p(s)) Σ r (')
02)1s0
vs, Vk 2 T(3),
(5b)
iEN
where the expectation is state distribution at the k-th time step, stationary action policy ~ a (-[sg), state transition probability 8k+1 P(-Isk. ax) and reward distribution. We note that under the Assumption T by (Levin & Peres 2017 Theorem 4.9), the Markov chain mixes at a geometric rate, which implies r(3)= O 5)-
The choice of step size 33 on the right-hand (RHS) of the definition of mixing time in equation is for simplicity. From (Srikant & Ying 2019). we know that the error level at the steady state is order-wise proportional to the step size up to a log factor (see the second term in the RHS of Eq. (12) of Srikant & Ying 22019), which is due to the geometric mixing time property.
Before presenting our main theorem, we introduce two useful lemmas. Our analysis to divide the convergence error into two parts, the consensus error, which is defined the agent's parameters deviation from the average parameter, and convergence error of the average parameter to the solution of the ODE in equation
First, we define the average of the parameters to be Wt,k = EiEN wf,x, for any communication round < L - 1 and local step < k: < 1. Then, we define the consensus emro as: Qi = wi.x 01
6

---

Under review as a conference paper at ICLR 2023
and the matrix form is Q1, [Qi - R
We provide an upper bound for the consensus error generated by Algorithm ! in the following lemma.
Lemma 1. Suppose that Assumptions 2 hold. For the consensus envor generated by Algorithm 1
3K & min(2 4(1 n x ). holds that
K2
11Q,,l S kip xn1p=1111000
1 1-p"
4(1 + (N mmax and p= 48K)(1 - -1y By the condition on 3K, we have 0 < 1.
where 2N (1
1-4²
Lemma shows that even if the parameters are not set to be the same initially, the effect of the initial consensus will converge 0 exponentially fast the round of communication goes infinity. The second term linear with respect to 3K, which resembles the constant term in optimization using constant step size SGD. This product term will dictates the consensus error and the error level that the algorithm converges to, see Section A.3 for detail. The proof for the lemma is relegated to Section
Next, we provide lemma that characterizes the convergence of the average parameter 0i,k- Note that, here we utilize the Theorem in (Srikant & Ying 2019), which has the state-of-the-ar non- batch sample complexity for TD learning.
Lemma 2. Suppose Assumptions A For the parameters generated by Algorithm V we have following result for the average of them
El w0 w01 c2 (201--18)k--000 (1 w=[l+ Timx )2 cyBT(B),
(8)
3
where Ct, C22 C3 > are constants that are independent of step size B, local steps K and commu- nication round L and TB) is the mixing time, See the specified expressions of the constants and discussion in Section
The average parameter L1 EiEN ti, corresponds to the updates after K x L iterations (samples). Lemma 2 shows that the average of the parameters converges to solution of the ODE with the rate given by the RHS of equation 8
Now, we state the main convergence result Algorithm
Theorem 1. Suppose that Assumptions hold. For the given policy, consider the iteration gener- ated by Algorithm
BK < min
4(1 x-1);
"
}. it then follows that:
K23KK 1-p
E
w²1|3
<2d kap 1mp=1110.u
+ 22 (22(1 kL-
(1 w0 1/|| Tmax )2 cgST). (9)
where KI, K2, C3 > 0,0 < p < 1 are constants, and wn.o v EiEN who and Qa is
the initial consensus error defined in equation 6 Furthermore, by letting 3 O(clog -(c()o-(((/E))
K = = O(vI/c h/c/////////////////////// (o)(1/c) and L = O / 1 (1)))/ we have EIEN ll - w01 = O(c).
(og(((())) The sample complexity is KT. 011 log (1/e)) and the communication complexity L ((V///log(L/e))
Note that since we use double loops Algorithm the parameter who, corresponds to the iteration
result after K x L samples (iterations). We remark that the sample complexity of (((1/e) log" (1/e)) (I/e)) the -fate-of-the-ee art sample complexity for non- batching single agent RL policy evaluation problem Srikant & Ying 2019). The sample complexity of our algorithm in distributed multi-agent setting, which also a botchig approach, matches this sample complexity. addition, compared with single-agent policy evaluation (Xu et al. 2020), which is batching method and its multi-agent
7

---

Under review as a conference paper at ICLR 2023
counterpart (Hairi al. |022 Chen al., 2021), this sample complexity only differs by a log factor. We note that, in (Xu et al., 2020; Hairi et al. 2022] Chen et al.) 2021). the algorithms are complete actor-critic algorithms. Thus, we only compare our results with their critic steps, which solve the policy evaluation problem.
In our proposed algorithm, between consecutive communication rounds, the number of local TD steps for each agent can be K = = /1/e log(1 (mggg())))))))))))))) This improved the communication complexity of vanilla distributed TD algorithms (Zhang et al. 2018 Doan et al.) 2019 2021) by a factor of K =
log(L/))) The communication complexity of our algorithm is L O M
which, interestingly, equals to K order-wise.
EXPERIMENTAL RESULTS
In this section, we conduct numerical experiments to compare our proposed local TD-update algo- rithm, TD learning with local steps, with vanilla TD learning (Zhang et al. 2018 Doan et al. 2019 202T) and the batch TD learning (Hairi et al.) 2022: Chen et al. 2021) | in both synthetic settings as in (Zhang et al. 2018) and cooperative navigation tasks as in (Lowe et al. 2017). Due to the page limit, we relegate the experiment setups and rigorous definitions of the performance metrics in the Appendix A. and B.1
6.1 CONVERGENCE PERFORMANCE ON SYNTHETIC SETTING
In the synthetic experiment, show that the function approximation parameter in the proposed local TD algorithm converges and the convergence with respect to the number of communication round for all algorithms. In Figure [ the y-axis the normalized convergence error of the left hand side of equation 9 and the axes are the numbers of communication rounds in Figure Ia Lc and sample numbers Figure [bb] Id] For extensive experimental details, discussions and results of experiment setup, convergence performance, the impact of local steps and linear convergences, please see Appendix A
20
1000
(a) K = 50, L = 200
(b) K = 50, L 200
(c) K = 100, L 100 (d) K = 100, L = 100
Figure 1: Convergence with respect to Communication Rounds and Sample Number
We considered 20 agents over a ring network. In Figure Ta we provide the convergence results with respect to the communication rounds for all three algorithms, where the local step K = 50 for local TD algorithm and the batch size is 50 for batch algorithm. Under such setting, both local TD algo- rithm and batch TD algorithm only performs consensus communication every 50 samples. To keep the comparison fair, keep the local step number and batch size to be the same for the majority of the comparisons except Figure 4 We can see that within 200 communication rounds, both batch algorithm and local TD algorithm converge a very similar level, yet vanilla TD algorithm doesn't 't converge even after 400 rounds of communication. Between the local TD algorithm and batch al- gorithm, the batch algorithm converges slightly faster, which means requiring slightly fewer rounds of communication among the agents. In Figure Ic when local step K = 100 for local TD algo- rithm and batch size 100 for batch algorithm, the local TD algorithm requires the least amount of communication rounds to converge, even compared to batch algorithm. On the other hand, local TD algorithm performs significantly better compared to vanilla algorithm. Note that in these parameter settings, our algorithm has the same number of communication rounds the batched TD algorithm. In Figures 1b and Id we present the corresponding convergence results with respect to sample num- that vanilla TD eventually converges but requires consensus operation after each
bers. We sampling. For more detailed discussion on the convergence with respect to sample numbers, please Section A.2 and A.4
8

---

Under review as a conference paper at ICLR 2023
sppning
wew
800
1869
1860
300
1900
(b) Bellman Error over Commu- nication Rounds
(c) Bellman Error over Sample Number
Cooperative Navigation Task
Figure 2: Convergence with respect to Communication Rounds and Sample Number
Tigure[[vriite the theoretical analysis that allowing local steps does help with the communication rounds compared to vanilla algorithm. In addition, even though the theoretical sample complexity of local TD algorithm is worse than batch algorithm, in practice, the communication rounds are comparable between these two approaches. This may be because the sample complexity is derived from the upper bound of the finite time analysis in Theorem I and this upper bound not only an order-wise result with respect to some criteria, the tightness of the upper bounds depends the analysis techniques. This may indicate that there is room to improve for the finite time analysis of the local TD algorithm.
6.2 CONVERGENCE PERFORMANCE ON COOPERATIVE NAVIGATION TASK
In the cooperative navigation task, the agents (blue circles) are trained to cover the landmarks (crosses) as illustrated in Figure 2a| Agents observe positions and velocities of all agents and collab- oratively cover the landmarks while avoiding collisions. The rewards for agents are defined through the proximity to the nearest landmarks. Unlike the synthetic experiment, the fixed point of the cor- responding ODE as in equation can't be calculated, performance metric. For extensive simulation results, which include discussions on various net- work topologies, local steps/batch sizes, different step sizes, and consensus error metrics, please Appendix B
the squared Bellman error as the
consider N = 9 agents over an Erdos-Rent (ER) network and set local step K to be 20 for local TD algorithm and batch size to be 10 for batch algorithm and appropriate step sizes for the algorithms. Similar the synthetic experiment, we can see that all algorithms converge to very similar Bellman error. This again verifies the theoretical analysis that allowing local steps and performing infrequent communications is feasible and can converge. More- over, in this setting, our local TD algorithm converges much faster in terms of the communication round. Specifically, local TD algorithm requires much less than 500 rounds of communication to converge, and both batch algorithm and vanilla algorithm perform similarly and require more than 500 rounds of communication to converge.
For the results in Figure 2b and 2c
7 CONCLUSION
In this paper, we answer the questions of whether local TD steps can lower the communication complexity of distributed TD learning and, if so, how the performance in comparison with batch TD learning. Our theoretical analysis and experimental results show that the local TD steps can significantly lower the communication complexity compared vanilla TD learning.
addition, our theoretical analysis also shows that the local step can be as large as O( (VVI/ log(1/ (I/+)) to converge to close to the solution of the corresponding ODE. However, in order to achieve the same (up to log factor) sample complexity as in batch TD learning, the communication complexity may also be significantly worse than that of batch TD learning in theory. But experimental results show a comparable performance of local TD algorithm with batch algorithm terms of communication rounds.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference on learning theory, pp. 1691-1692. PMLR, 2018.
Tianyi Chen, Kaiqing Zhang, Georgios B Giannakis, and Tamer Basar. Communication-efficeent distributed reinforcement learning. arXiv preprint arXiv: 2018.
Xin Chen, Guannan Qu, Yujie Tang, Steven Low, and Na Li. Reinforcement learning for selective key applications in power systems: Recent advances and future challenges. IEEE Transactions on Smart Grid, 2022.
Ziyi Chen, Yi Zhou, Rongrong Chen, and Shaofeng Zou. Sample and communication-effie decentralized actor-critic algorithms with finite-time analysis. arXiv preprint arXiv:2 2021.
Thinh Doan, Siva Maguluri, and Justin Romberg. Finite-time analysis of distributed td (0) with linear function approximation on multi-agent reinforcement learning. In International Conference on Machine Learning, pp. 1626-1635, PMLR, 2019.
Thinh T Doan, Siva Theja Maguluri, and Justin Romberg. Finite-time performance of distributed temporal-differen learning with linear function approximation. SIAM Journal on Mathematics of Data Science, 3(1):298-320) 2021.
FNU Hairi, Liu, and Songtao Lu. Finite-time convergence and sample complexity of multi-agent actor-critic reinforcement learning with average reward. In International Conference on Learning Representations, 2022.
Daewoo Kim, Sangwoo Moon, David Hostallero, Wan Ju Kang, Taeyoung Lee, Kyunghwan Son, and Yung Yi. Learning schedule communication in multi-agent reinforcement learning, arXiv preprint arXiv:1902.01554 2019.
Chandrashekar Lakshminarayanan and Csaba Szepesvari. Linear stochastic approximation: How far does constant step-size and iterate averaging go? In International Conference on Artificial Intelligence and Statistics, pp. 1347-1355. PMLR, 2018.
Donghwan Lee, Hyungjin Yoon, and Naira Hovakimyan. Primal-dual algorithm for distributed re- inforcement learning: distributed gtd. In 2018 IEEE Conference on Decision and Control (CDC), pp. 1967-1972. IEEE, 2018
David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathe- matical Soc., 2017.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu, Can decentralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent. Advances in Neural Information Processing Systems, 30, 2017.
Yixuan Lin, Kaiqing Zhang, Zhuoran Yang. Zhaoran Wang, Tamer Başar, Romeil Sandhu, and Liu. A communication-effiiiiii multi-agent actor-critic algorithm for distributed reinforcement learning. In 2019 IEEE 58th Conference on Decision and Control (CDC), pp. 5562-5567 IEEE, 2019.
Ryan Lowe, Yi I Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi- agent actor-critic for mixed cooperative-competiiie environments. Advances in neural informa- fion processing systems, 30, 2017.
Sergio Valcarcel Macua, Jianshu Chen, Santiago Zazo, and Ali H Sayed. Distributed policy evalu- ation under multiple behavior strategies. IEEE Transactions on Automatic Control, 6065):1260- 1274, 2014.
Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimiza- tion. IEEE Transactions Automatic Control, 54(1):48-611 2009.
10

---

Under review as a conference paper at ICLR 2023
Shi Pu and Angelia Nedić. Distributed stochastic gradient tracking methods. Mathematical Pro- gramming, 187(1):409-44) 457, 2021.
Shuang Qiu, Zhuoran Yang, Jieping Ye, and Zhaoran Wang. On finite-time convergence of actor-
critic algorithm. JEEE Journal on Selected Areas in Information Theory, 2(2))652 664,6 2021.
Jineng Ren and Jarvis Haupt. A communication efficient hierarchical distributed optimization algo- rithm for multi-agent reinforcement learning. In Real-world sequential decision making workshop at international conference on machine learning, 2019.
Martin Riedmiller, Andrew Moore, and Jeff Schneider. Reinforcement learning for cooperating and communicating reactive agents in electrical power grids. In Workshop Balancing Reactivity and Social Deliberation in Multi-Agent Systems, pp. 137-149. Springer, 2000.
Shai Shalev- Shalev-Shwartz. Shaked Shammah, and Amnon Shashua. Safe. multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv:1610.0329; 2016.
Rayadurgam Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation andtd learning. Conference on Learning Theory, pp. 2803-2830. PMLR, 2019.
Richard Sutton. Learning to predict by the methods of temporal differences. Machine leurning, (1):9-44, 1988.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
J.N. Tsitsiklis and B. Van Roy. An analysis of -emporal-diiferencc learning with function approxi- mation. JEEE Transactions on Automatic Control, ((5)):74-690, 1997. doi: 10.1109/9.580874
John N Tsitsiklis and Benjamin Van Roy. Average cost lemporal-difffrrnce learning. Automatica, 17799988888 1999.
John N Tsitsiklis and Benjamin Van Roy. On average versus discounted reward cumporal-differene learning. Machine Learning, 1992)1179-191, 2002.
Hoi-To Wai, Zhuoran Yang, Zhaoran Wang. and Mingyi Hong. Multi-agent reinforcement learn- ing via double averaging primal-dual optimization. Advances in Neural Information Processing Systems, 31, 2018.
Tengyu Xu, Zhe Wang, and Yingbin Liang. Improving sample complexity bounds for (natural) actor-critic algorithms. arXiv preprint arXiv:2004. 122550.04...6..... 2020.
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 high- ways based on dynamic coordination graphs. IEEE Transactions on Intelligent Transportation Systems, (122):335-748 2019.
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, Zhuoran Yang. and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, pp- 321-384, 2021a
Xin Zhang, Zhuqing Liu, Jia Liu, Zhengyuan Zhu, and Songtao Lu. Taming communication and sample complexities in decentralized policy evaluation for cooperative multi multi-agent reinforcement learning. Virtual Event, December 202
A APPENDIX
In the section, we provide the experiment setup and additional experimental results for the synthetic setting.
11

---

Under review as a conference paper at ICLR 2023
4.5
leaming slep
TD with
Vanilla
Vanilla TD leaming
leaming
TD leerning batch
3.5
Cbjective Erao
Objadiva
2.5
1.5
0.5
0
2000
4000
10000
2000
6000
9000
Sample Number
Sample Number
(a) K 50, I 200
(b) K 100, L 100
Figure 3: TD with local steps vs. vanilla TD and batched TD.
A.1 SYNTHETIC EXPERIMENT SETUP
We consider the same setting as in Section 6.1 of (Zaang et al.. 2018). There are N = 20 agents, each of which has a binary-valued action space, i.e., AA' = {0, 1 for all E W. There are |S] 10 states. The entries in the transition matrix are uniformly sampled from the interval [0, 1] and normalized to be stochastic. For each agent i and global state action pair (s, a). the mean reward R (s. a) is sampled uniformly from [0, 4] and the instantaneous rewards {ri} are sampled uniformly within the set RR (s, a) 0.5, R' R'(s, a) + 0.5]. The policy considered in the simulation is (-(ss) 0.5 for all i E N, s E The entries of feature matrix + are sampled uniformly at random from [0. 1] with feature dimension d = 5 and ensured to be full rank. In addition, we set each feature vector to be unit length. The discount factor 7 is set to be 0.99. The network topology is chosen as a ring network with diagonal elements being 0.4 and off-diagonal elements being 0.3. The simulation results are averaged over 10 trials. We choose the step sizes for our algorithm to be 0.005, vanilla TD to be 0.1, and batched TD to be 10. We note that these step sizes chosen to be best for the corresponding algorithms.
The objective error is defined the normalized version of convergence term (LHS of the equation ie., the empirical sample mean errors divided by the number of agents N and the dimension number d:
Objective Error := sample average of v
||w VE
w I|2
for 10 trials.
dN
We remark that due to the fact that the transition matrix is not dependent joint action, the steady state distribution can be computed and so is the value of w", whose definition is in equation 4
A.2 CONVERGENCE PERFORMANCE
First, we show that the local TD-update algorithm exhibits similar empirical convergence perfor- mances as the other algorithms.
In Fig. we choose the number of local steps to be K 50 and communication rounds to be L = 200 for the local TD-update algorithm. We choose batch size to be 50 and communication rounds be 200 for batched TD algorithm in Fig. B(.). In Fig. b). we increase the number of local steps to K = 100 and decrease the communication rounds to L, 100 for the local TD-update algorithm, and we also increase batch size to be 100 and decrease the communication rounds to be 100 for batched TD algorithm. Note that in these parameter settings, our algorithm has the same number of communication rounds as the batched TD algorithm.
From both Figure a) and (b), we can see that all algorithms converge similar low objective error levels. This verifies the theoretical analysis that allowing local steps and performing infrequent communications is feasible and can converge. Then, we look at the number of samples needed to reach the low objective error. From Figure aa), we see that when local steps are relatively small, i..,, K 50, the vanilla TD algorithm requires the most samples, while batched TD requires the
12

---

Under review as a conference paper at ICLR 2023
least, and our local TD algorithm with local steps requires somewhere in between. In Figure b(b), when we increase the local steps to be K = 100, the number of samples of the local TD-upd algorithm requires is the least compared to the other two algorithms. On the other hand, when the batch size increases, the number of samples required for batched TD to converge to low objective emror is very similar to that of vanilla TD. However, we note that both our algorithm and batched TD requires less than 200 rounds of communication to reach that level of objective error in Figure 3(a) and less than 100 rounds of communication in Figure B)). Moreover, these results show that the local TD-update approach can effectively lower communication complexity of MARL-PE compared the vanilla TD method.
4.5
local TD leamnnn with K=50, L=200
local TD learning with K-100, L-100
local TD learning with K-200, L=50
3.5
Vanilla TD learning
Batch TD leaming with M-50,L-200
Objective Error
Batch leaminng with M=100,L=100
Batch TD leaminng with M-200,L-50
2.5
1.5
0.5
0
0.5
1
1.5
2
Sample Number
x 100
Figure 4: Additional TD with local steps vs. vanilla TD and batched TD.
In addition, we compare different pairs of local step K and communication round L of our proposed algorithm with different pairs of batch size M and communication round L in Figure ! In general, local TD learning performs at a comparable level with batch TD algorithm, especially for the case K = M 50 and L = 200, red curve for local TD algorithm and blue curve for the batch TD algorithm respectively. When increasing the local steps for local TD algorithm, it converges faster but to higher error level. In comparison, when increasing the batch size for batch TD algorithm, the convergence is slightly slower but to a smaller error level.
A.3 IMPACTS OF THE NUMBER OF LOCAL STEPS ON CON VORVEGENNC
Next, we illustrate the effect of the number of local steps on the convergence for our proposed algorithm. In Figure vary the number of local steps from K 40 to K = 250. There are two interesting observations from this result. First, the number of samples needed to reach a low level objective error decreases as the number of local steps increases. For example, when K 100 or larger, the curves drop much more rapidly in the beginning compared to the curves with smaller local steps. Second, the level of objective error that the algorithm converges increases as the number of local steps increases. For example, when K < 100, the objective error is relatively low and stable, but K increases to 200 or 250, the objective eтror large and oscillates around a relatively higher level. This observation is consistent with our theoretical analysis. Recall the second term on the RHS of equation 7 in Lemma T that is proportional to the product of step size / and local step K. This term says the objective error will converge to neighborhood of zero, for which the size of the neighborhood depends on 3K. As a result, for a larger K-value the objective error will oscillate with a larger magnitude. This resembles the constant step size term in the convergence of the SGD method in the distributed optimization problem (Nedic & Ozdaglar 2009). Also intuitively, the agent-drift phenomenon will exacerbate with larger local steps, the results for K 2 200 in Figure Jjagree with such intuitions. In summary, empirically, when the step size is fixed, larger local steps helps the convergence speed, but it will also result in converging higher objective error level.
13

---

Under review as a conference paper at ICLR 2023
3.5
K-50
K-100
K=200
K-250
Objective Erro
1.5
0.5
0
2000
4000
6000
8000
10000
Sample Number
Figure 5: Impact of local steps K on convergence.
A.4
LINEAR CONVERGENCE WITH RESPECT TO SAMPLE NUMBER
10
TD leamnng with local stop
TD keaming with local stop
Vanila TD leamiin
Vantlia TD leaming
TD learning with barch
TD keariing with batch
Objecive Error
Objective Error
100
10
10"1
2000
4000
8000
8000
10000
0
2000
4000
6000
8000
10000
Sample Number
Sample Number
(a) K = 50, L = 200
(b) K = 100, L = 100
Figure 6: Convergence in Log Scales
In Figure 6 we provide the log scaled objective error with respect to sample number for all three algorithms. All algorithms behave similarly. Specifically, there are two phases in the convergences, roughly a linear convergence phase at first and oscillation phase at a relatively low objective error level. At the linear convergence phase, the objective error quickly decreases as the number of sample increases and reaches relatively low objective error phase; at the oscillation phase, the objective error oscillates. This oscillation is likely caused by both the randomness in sample and the consensus error. For the local TD algorithm, as increase the local step K from 50 to 100, the only difference is the oscillation phase, where when K = 100, the objective eттоr is higher due to the effective step sizes 3K becomes larger, as indicated by the second term in Equation equation 7 This constant error term that is linear with respect to step size is common in the constant step size learning scheme.
B COOPERATIVE NAVIGATION TASK
B.1 EXPERIMENT SETUP AND PERFORMANCE METRICS
We consider a cooperative navigation task that adapted from one of Multi-Agent Environments (Lowe et al. 2017). There are N = 9 agents in total, and the goal is to cover 9 landmarks collab- oratively. Each agent can choose from the action space, .A' =[no action, move left, move right, move down, move up}. in order to reach the goals based on the policy. The policy considered in the simulation is r' (-Is) = 0.2 for all actions and e N, s E S, i.c. uniformly random policy. The local rewards given by the distance between the agents and goal landmarks. However, if they collide
14

---

Under review as a conference paper at ICLR 2023
with each other, there would be penalty given. The agents trained to cover landmarks and reach the destination while avoid colliding with other agents, and the entire training process is fully decen- going to accomplish. As shown in the figure,
tralized. Figure Za illustrates the task that agents the blue circles are the agents, and the black crosses are the landmarks. Agents should learn to cover goal landmarks, for example, following the arrows to finish the task. The feature dimension here is 36, i.c. d = 36, which includes all agents' self velocity, self position, landmark relative positions, other agent relative positions, and corresponding values are ranged within (-oc, 00), Discount fac- tor is set to be 0.95. We choose step size / for our algorithm to be 0.05, for vanilla TD algorithm be 0.1, and for batch TD algorithm be 0.1 as well. We note that these step sizes are chosen for the best performance for the corresponding algorithms.
The performance metrics are mean squared Bellman error (MSBE) and consensus error (CE). The empirical squared Bellman error is defined
N SBE (f [ww)) Sk: 5k+1)
Σ iEN
-x (0((=+1)))++++)) ) wwf
N
where F +/r
EiENT Then, mean squared Bellman error is computed by averaging all squared Bellman error in the history, which is defined as
1 MSBE
SBE
(fwt, J SBx 5x+1)
The consensus error is defined
CE
(wk
[wkii=1
1 -
N
eN
(a) Ring Network
(b) 4- Reggglarr Network
(c) 6 6-Regular Network
(d) ER Network
(c) Complete Network
Figure 7: Network Topology
B.2 NETWORK TOPOLOGY
We compare all algorithms under five different network typologies. These are ring network, 4- regular network, 6-regular network, Erdos- Rends-)))yy(ER) network with 0.5 connection probability, and fully connected network. These network topologies are illustrated in Figure For simplicity, the local aggregation is the average of neighboring nodes for all networks.
B.3 CONVERGENCE PERFORMANCE
First, we show that the local TD-update algorithm exhibits similar empirical convergence perfor- mances the other algorithms while using less communication rounds among agents. Here
15

---

Under review as a conference paper at ICLR 2023
choose the number of local steps to be K 20 for the local TD-update algorithm, the batch size to be 10 for the batched TD algorithm. For all of these algorithms, we set the total sample number over various network
to be 10000. The comparison among the algorithms is shown in Figure 9 13 topologies.
and consensus error level based on these figures. This verifies our analysis that allowing local steps and performing infrequent communications feasible and can converge. In this case, vanilla TD algorithm performs 10000 communication rounds, which is the most, batch TD algorithm performs 1000 communication rounds, while local TD-update algorithm only performs 500 communication rounds. Left columns of the Figure 9 13 demonstrate the mean squared Bellman error, and right columns demonstrate the consensus error. For the mean squared Bellman error, the curve of local TD-update algorithm and the curve of vanilla TD algorithm has similar dropping rates, while the curve of batched TD algo- rithm drops slower. In terms of eπror level, all algorithms converge to a comparable mean squared Bellman error, which is around 2. On the other hand, the consensus errors in the right column of Figure 13 of all algorithms are close to O, although local TD-update algorithm may have a rel- atively high error level depending the network topology. In Figure g present the topology effect on our proposed algorithm. is, in general, as the network becomes more and more connected the consensus error fluctuates less. Intuitively, with better connected network, after local consensus aggregation, the parameter can be closer to the global average of the network.
We can that all algorithms converge to very similar low squared Bellman
Ring Network
4-Reqular
Mean Squared Bellman Error
6-Regular Network
ER Network
Complete Network
5
0
2000
10000
Sample Number
Figure Topology on Local TD Algorithm
30
TD leaming with local stop
local
Varilla TD leamingg
Mean Squared Bellman Eiror
with batch
learning with
Consensus Error
15
20
0.05
0
6000
10000
0.09
2000
4000
5000
8000
10000
Sample Number
Sample Number
(a) Mean Squared Bellman Error
(b) Consensus Error
Figure 9: Comparison among Algorithms in Ring Network
16

---

Under review as a conference paper at ICLR 2023
0.15
TDleaming with stop
TD leaming with local step
Varila TD leaming
Varita TO
Mcan Squared Bellman Error
TD leaming with batth
20
Consensus Error
15
2000
4000
600n
8000
10000
0.00
2000
4000
6000
80:00
10000
Sample
Sample Number
(a) Mean Squared Bellman Error
Consensus Error
Figure 10: Comparison among Algorithms 4-Regular Network
30
leamiing with step
TD leaming with local slop
Varilla Teaming
Vanila TO
Mean Squared Bellman Error
TD leaming with batch
leaming
20
Consensus Emror
15
20
%
6000
8000
10000
0.00
2000
4.000
6000
10000
Sample Number
Sample Number
(a) Mean Squared Bellman Frror
(b) Consensus Error
Figure 11: Comparison among Algorithms 6-Regular Network
30
TD leaming with local stop Varilla TD leamingg
local
Mean Squared Bellman Eiror
with batch
leamiin
Consensus Error
15
20
0.05
0
0.09
2000
4000
5000
8000
10000
Sample Number
Sample Number
(a) Mean Squared Bellman Error
(b) Consensus Error
Figure 12: Comparison among Algorithms in ER Network
17

---

Under review as a conference paper at ICLR 2023
0.15
TDleaming with stop
TD leaming with local step
Varila TD leaming
Varita TO
Mcan Squared Bellman Error
TD leaming with batch
20
Consensus Error
15
20
2000
4000
600n
8000
10000
0.00
2000
4000
6000
80:00
10000
Sample
Sample Number
(a) Mean Squared Bellman Error
Consensus Error
Figure 13: Comparison among Algorithms Complete Network
In addition, we have compared different pairs of local step and communication round for our pro- posed algorithm and different pairs of batch size and communication round for batch TD algorithm in Figure 14] for cooperative navigation task. In this setting, all algorithms converge to similar Bellman error level. However, the convergence for local TD algorithm is faster than batch TD al- gorithms in all parameter settings. Moreover, with the increase of batch size, batch TD algorithm seems converge slower while with the increase of local step, local TD algorithm convergence increases in general but not significantly.
30
Vorila TD Leaming
Incal TD learing with K-5, 1-2000
local leemiin with K-10, L-1000
Mean Squared Bellman Emao
25
K- L=500
kaming N=5L-2000
leaming N-10,1-1000
20
Satch 1O kaming with H=20,L-500
Twtcc TD leaming with M-10,1-250
2000
4000
6000
8000
10000
Sample Number
Figure 14: Additional Comparisons
B.4 CONVERGENCE PERFORMANCE WITH RESPECT TO COMMUNICATION ROUNDS
In Figure 15 we provide the convergence results with respect to the communication rounds for 20 for local TD-update algorithm and the batch size is
all algorithms, where the local step 10 for batch TD algorithm. We can see that within 500 communication rounds, local TD-update algorithm converges faster than batched TD algorithm and vanilla TD algorithm to a very similar error level. Within 1000 communication rounds, batched TD algorithm and vanilla TD algorithm performs similarly. The performance of these algorithms not affected by the network topology being used.
18

---

Under review as a conference paper at ICLR 2023
Vee Spaand Grorr
1869
180
108
1:00
(a) ring network
(b) 4-regular network
(c) 6-regular network
Veeiaa
Commercation Aain
Communicoatio Aound
(d) ER network
(c) complete network
Figure 15: Convergence Respect to Communication Rounds
B.5 IMPACTS OF THE NUMBER OF LOCAL STEPS ON CONVERGENCE
Next, we illustrate the effect of the number local steps K on the convergence for our proposed algorithm. In Figure [6 we vary the number of local steps from K 10 to K 200. The right column is the consensus error of first 2000 samples, which displays better view. As the number of local steps increases, the mean squared Bellman error converges to a higher error level, on the other hand, the consensus error oscillates more. In summary, larger local steps helps with saving more communication cost while it also result in converging to a higher mean squared Bellman error and greater fluctuation of the consensus error. This conclusion also echoes with the synthetic experiment results in A.3
1000
(a) Mean Squared Bellman Error
(b) Consensus Error
(c) Zoomed Consensus Frror
Figure 16: Comparison among Different Local Steps in 4 Regular Network
B.6 IMPACTS OF STEP SIZE ON CONVERGENCE
Here, we illustrate the effect of step size / on the convergence for our proposed algorithm and batched TD algorithm over a 4-regular network. First of all, we can take a look at batch TD algorithm displayed on Figure 17 19 over various batch sizes. The brown line shows the performance of our proposed algorithm to help compare with batch TD algorithm. In general, in terms of mean squared Bellman error, larger step size 3 leads to faster convergence speed and larger error level. Smaller step size 3 leads slower convergence speed, but could eventually converge to smaller error level. Also, larger step size 3 results in a greater consensus error. Thus, we set step size / = 0.1 and batch size be 10 for batch TD algorithm.
19

---

Under review as a conference paper at ICLR 2023
0.5
5-001
0.05.
F- 0.05
Mcan Squared Bellman Ereor
d- 0.2
0.4
F 0.2
8-0.5
Consensus Error
25
TO with local stop
0.2
TD with local stop
20
15
0.2
10
0.1
2000
4000
600n
2000
10000
0.0
2000
4000
6000
8000
10000
Sample
Number
(a) Mean Squared Bellman Error
(b) Consensus Error
Figure 17: Comparison among Different step sizes for TD Learning with Batch Size in Regular Network
0.5
F- 0.01
0.055
Fmm 0.05
Mean Squared Bellman Error
0.1
0.4
30
8m 0.2
F 0.2
25
TO with local step
Consensus Error
TD with local stop
0.3
20
25
0.2
20
0.1
4000
6000
8000
10000
0.0
2000
4000
6000
8090
10000
Sample Number
Sample Number
(a) Mean Squared Bellman Error
(b) Consensus Error
Figure 18: Comparison among Different step sizes B for TD Learning with Batch Size 10 in
Regular Network
0.5
8-0.01
f- 0.01
35
6.05.5
0.05
Mean Squared Bellman Error
80
0.2
0.4
0.2
Consensus Error
25
TD with local stap
TD with local stop
0.3
20
25
0.2
10
0.1
0
4000
6000
8000
10000
2000
400n
6000
R000
10000
Sample Number
Sample
(a) Mean Squared Bellman Error
(b) Consensus Error
Figure 19: Comparison among Different step size 3 for TD Learning with Batch Size 20 in Regular Network
As shown in Figure 20 similar to batch TD algorithm, larger step size 3 leads to faster conver- gence speed and larger mean squared Bellman and consensus error level in local TD-update algo- rithm. However, the emrr differences among different step sizes are not that significant compared
20

---

Under review as a conference paper at ICLR 2023
to batch TD algorithm. In order to balance among convergence speed, error level, and communica- tion cost, we decide to use step size = 0.05 and local step K 20. In this way, we could have a fast convergence speed, low communication cost, and a relatively low error level.
0.35
0,000
0.005
0-0.01
Mean Squared Bellman Error
23
0-0.05
9-0.1
20
Consensus Error
25
20
2000
4000
6000
8000
10000
Sample Number
Sample Number
(a) Mean Squared Bellman Error
(b) Consensus Error
Figure 20: Comparison among Different step sizes for TD Learning with Local Step K 10 in 4
Regular Network
30
0.005
100.01
Mean Squared Bellman Emror
0 0.05
0-0.1
Consensus Eror
0.21
15
0.14
10
0.07
%
6000
10000
0.00
2000
4000
6000
B000
10000
Sample Number
Sample Number
(a) Mean Squared Bellman Error
(b) Consensus Error
Figure 21: Comparison among Different step sizes B for TD Learning with Local Step 20 in
Regular Network
0.35
$
B .0.00
$ mm0.01
8 0.01
Mean Squared Bellman Errrr
25
$50.05
0.28
f=0.1
20
Consensus Enrr
15
%
2008
4000
6000
800o
10000
Sample Number
Sample Number
(a) Mean Squared Bellman Error
(b) Consensus Error
Figure 22: Comparison among Different step sizes for TD Learning with Local Step K 50 in Regular Network
21

---

Under review as a conference paper at ICLR 2023
C PROOFS OF LEMMAS AND THEOREM
In this section, we provide the derivation for the consensus error. Then, we prove the Lemma provide detailed discussion for Lemma and the proof of Theorem
C.1 THE DERIVATION OF CONSENSUS ERROR
Within each communication round s -- 1, the parameter update wi, for agent at local
step can be written follows
w wi,++ w 36 ((1,.))
= (I+ 30(0),)) ((sL)))²) wi, + (ri.++0((LL))
Bi + cha
(10)
where B1, = - ( ( and cf == 3ri 6(.1)). Then, from local
step 0 to 1, we have
K-1
K-1 K-1
w K
II
BL
+
Σ II
B
k=
k=0 n=k+1
After a consensus update, the parameter for agent will be
wi+10- Σ
A(i,))
wi,K
JEM
K II R=
K-1 K-1
Σ
A(i,))
BL + Σ II BLank
JEM
k=O n=k+1
K-1
K-1 K 1-1
Σ JEN.
A(I,))
II k=
BL.w + Σ
A(i.))
II k=0 n=n++1
BLnd
JEM,
The equation above shows the parameter update between two consecutive communication rounds. Now we consider the average dynamics of the parameters across all agents. Recall W
1 EiEN wi then within each communication round 0 < < L 1, using equation 10 we
N
have
Σ wi
WLA+1
N
iEN
Σ
BL
+ ci,x)
N
iENV
1
Σ ax
Bi, +
N
IEN
= =B, + CL.
(11)
where Cr 1/2 Die Hence, the average dynamics from local step 0 to K 1 will be
K-1
K-1
Wi.K
II
BI 10,0
Σ
II
BL
A=
k=
After a consensus update, we have
11+100 = WY,K-
(12)
Note that the equation above means that consensus step will not change the average dynamics and average dynamic will only be updated during local steps.
22

---

Under review as a conference paper at ICLR 2023
For agent N,, consider the consensus error at communication round I and local step k where 0 Σ & v and recall Qi = wi, wi. Then, we have
Qi,++1 =wi W1,++
=i, + d₂ BI, Ci
=BI, w),k) + Gi Ct,k
=BI + ci,x Cr
Then, for the matrix form Qi,e 1Qi, Qid E ROxN, we have
Q1,++1 Q1, + C.a(I 1 11?)
N
where Ci == lc,, cxyy and 1 denotes the all-1 column vector. Then, for communication round I, we have
K-1 II
K-1K-1
QU,
BI. 11,0 +
E B
N
k=
1 Est
After a consensus update, we have
w
W1+10
Wi,k
Σ A(i.j)u(, L1
JEN:
Σ
A(1.))(wf, 101x)) = Σ Ali.))Q)
JEN.
JEN,
As result, have
- QI,
K-1
K-1K-1 II
II BI.A
Σ
B, A1T)
Est
After T. communication rounds, we have
1-1 K-1
I- ------I
K-IK-1 - N 117 (AT)
Qr.0
II Boo [=U K=D
Σ II
Buss
Bu,ul 1=0 ist
1=0
K=
Note that for the second term when = L 1, inside the summation, the summand becomes K K- 1B.,1;CL-LL(11- AA" other words, the matrix multiplier in front becomes an identity matrix.
C.2 PROOF LEMMA I
The norm of the consensus error is following
l|Qr.ol1
L-1 K-1
L-1--1IK-
K-1K-1
II
II
BL (o,o
Σ
II
I
Buss
II
II
Bi,
1 N
(17)
1=0 K=
K=0
t= Est
L-1K-1
II
II
BL (AT)
I=0 k=
K-IK-1
Bask
II
B
(177)(4)
(13)
N
1=0 Est
23

---

Under review as a conference paper at ICLR 2023
Before obtaining bounds on the terms of the consensus enror in equation 13 useful bounds on Bi, and Ct,k- First, we have
first provide some
B l|
= || + (o(sw))oo(u -((s,)))
2 1 + (s,
(1(()
- 1 + 3(1 7) < < + 2/3
where the second inequality is due to Assumption Then, we have ||Gr,ll S BVNrmax, where Tmax = supi,s,a ('(ss) a) by Assumption
This is because
||Cx,1ll (186(ss))))r)a)
S { I10rk,41>" . N (
= =BVNrmas
Next, inspired by Srikant & Ying 2019 we want to use the following bound
(1+ + x) K $ 1 2x
for small x. Note that
(1+ K
2== = + 2x 20
and when log
a
(1+x)*=
= K(L KL
2) S (k-) 2K Ox
(1 2xK)
Or
where the first inequality is due the fact log(1 + x) for x 2 and the second inequality is
due to the fact
log
Let 23 x and 3 S 2K S log
K
2(K-1)*
For the first term in equation 13 when B S
1. 2k we have that
L-1K-1
L-1K-1
II
II
(A)
S
II II 1=0
BI -100o1/100000))
S x(1 + 233 KL - N-j-
S x(1 + 43K) - -1"
=xp
where define p (1 + 4 - When 0 < 3K minf 2 1(1 1y). have 0 p The second inequality comes from the following two results.
Ny
-
First, consider the case where A is symmetric matrix for simplicity, then we have
1
11Qo,0 4f.11
110 - Q0.0 N ||
=
Σ (A N
Qb
iEN
|A4
N/1 11
NEN
1 17 (N-1)
< N 2
(1 17
N11= JEN
max
11
1 1 N
2N 1 11)
N-1
||Qooll:
17 N-
where the second inequality is from Nedic Ozdaglar 2009
(Proposition 1). Hence, 1|Q
2 1+n - 11
-1) ||Qo.o||
x1(1
17 1
Qo.oll where sn 2N2 1+
v-
1-
24

---

Under review as a conference paper at ICLR 2023
Second, have
T- K-1
1-11 K-1
II B <
II II
|Ball
[=0
k=
[=0 k=
4-1K-1
II 1=0
I1 23) -1 (1+ 2 (1)
0=
To bound the second term of equation 13
have
II where the inequality is also from Nedic & Ozdaglar (2099)
N 11 "1 || -
11"
S 21 17 1 -17
N
(Proposition 1). Then, we also have
K K
II
B - CIall
c=0
ixt
K-1
(1 + 23) 28) K-1-t BV Nax
t=
K-1
=BVN L.VVrmaa mmax
Σ t=0
(1 + +-))
<28K NTmax-
Then, for the multipliers, we have
L-1-iK-1 1-1
II j=1
II
Bishell S (1 28)(4-1-1)K < (1 +1+ 43K)
k=0
Finally, for the second term in consensus error equation 13
we have
1-12-1-IK-1
K-1K-1
ΣΣ
II
II
BAJR
II
B
Cr
1 117)
N
K=
t=0
Est
1-I-I--1
K-IK-1
II
Bl
Σ
II
Br. |1(1 N
11 (AT) (A7)
K=0
1=
+ 4,8K)
B max 11 17N-1)6-1-1
1=0
3523K 3K Σ p
K23K
1 1-p
where K2 = 4(1 + 17 (N- (N) max-
As result, we have the results consensus bound of equation in Lemma
C.3 DETAILS ON LEMMA 2
Recall the average parameter dynamic from equation I1 which is among consecutive communi- cation rounds, and equation [2] after consensus update. The average parameter is signaled by the true average of the rewards, T.e. Vi, = n ΣieN Tie during both the local TD steps and consensus steps. Therefore, it behaves like conventional TD update in a single agent setting. By Theorem 7 in Srikant & Ying 2019) we have following results
E 0r.0 w w0|l < c2(1 ei KL ((100 (11wo w +1
Tmax )a + cg
3
25

---

Under review as a conference paper at ICLR 2023
where 7 is mixing time. Under Assumption |
O }). To specify the constants C1 022 C3+
introduce the Lyapunov equation. Recall the definition of vp in equation 33 which negative definite Titsikkis & Van Roy (1997). So we have a symmetric matrix > OrSkanntt & Ying (2019)
such that
U + U +
which is called the Lyapunov equation. For symmetrie matrix U, there exist largest and smallest eigenvalues Amax and Amin respectively. In addition, Amax and Ami are both positive. So, the constants are
0.9
C1 Amax
C2 2.25 Amax
Amia
21
max (7
max + 55(1 + T'mx)) )m
0.9Amin
C.4 PROOF OF THE THEOREM
For the mean square error, we have
E
1 - ==11
E
| - 1I.. + WI.0 w=
<2E
1/22,0 wr. + 2B
| w [1
1=1
Qr. ol ol 2N Wr. w" [13]
(14)
where the first inequality due to || 2/12 s 2| + 2|yy/ 2 and the second inequality X F S
X|| for X E RdxNN Then, the stated result equation follows from Lemmas and and
equation 14
This concludes the proof.
26


Reviews:
[{"review_id": "nMU43EqP360", "reviewer": "Reviewer_N76j", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper studies the multi-agent policy evaluation problem for a set of networked agents that can communicate through the network. In the linear function approximation regime, the authors apply the standard temporal difference (TD) learning method with no batch samples but multiple local TD updates per communication, and show near-optimal sample complexity and improved communication complexity compared to naive TD updates. Finally, the authors demonstrate the effectiveness of the proposed method in both synthetic and real multi-agent policy evaluation problems. ", "summary_of_the_review": "The paper studies an extension of naive TD method for the multi-agent policy evaluation problem. This extension is limited to a basic TD learning setting, which leaves a question about usefulness in other settings. The analysis also extends existing mean-path analysis in a more direct way, which leaves a question about novelty of analysis. Further study on conditions when the proposed method works and fails due to 'agent drift' is also needed. Since the authors miss many recent works, the novelty hasn't been fully established without a fair comparison. Generalizations to other settings haven't been established in either theory and experiments.  ", "strength_and_weaknesses": "Strengths\n\n- The communication compleixity is a bottleneck for distributed RL algorithms to efficiently work for large-scale networked systems. The studied multi-agent policy evaluation problem is a basic multi-agent RL task, which is real and meaningful. \n\n- The authors particularly focus on a class of temporal learning (TD) methods with local TD updates per communication. Compared with batch-based TD methods, the studied method works simpler and is more useful in practice, since a large amount of batch sampling is expensive in many real-world applications.\n\n- It is useful to establish near-optimal sample complexity of the proposed method as the well-studied batch-based TD methods. The studied communication complexity is also important to understanding pros/cons of the proposed methods. \n\n Weaknesses\n\n- The proposed method is limited to an extension of naive TD methods for multi-agent MDPs. It is unknown about the generality of this method to other TD methods.\n\n- This study is limited to the naive TD method which might not be very useful in some settings, for instance off-policy. Other limitations include the linear function approximation and the synchronous communication network.\n\n- The study assumes a series of technical assumptions on the multi-agent MDPs and the function approximation. It is known that these assumptions provide convenience to analyze TD methods with Markovian data if the underlying MDP has a fast mixing. Hence, the first two claimed challenges are not the main difficulty of analyzing the proposed method. \n\n- For the communication complexity, it is unknown if the proposed method can match batch-based TD methods. It is useful if some lower bound can be established for the proposed methods. \n\n- It is expected to see that the information of network topology should be a big factor in the final error bound. This is missing. Experiments on other network topologies should be included for illustration.  \n\n- The literature review misses many recent works on MARL policy evaluation problems, which is detrimental to the novelty. A more complete comparison is recommended, e.g., the paper:  Taming Communication and Sample Complexities in Decentralized Policy Evaluation for Cooperative Multi-Agent Reinforcement Learning. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "esHHBRbCsFS", "reviewer": "Reviewer_YnpC", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper considers the multi-agent reinforcement learning policy evaluation (MARL-PE) problem, where $N$ agents collaborate to evaluate the value function of the global states for a target policy. It focuses on how to analyze the communication cost among agents when using the local temporal-difference (TD) learning method. \nFirst, this paper theoretically shows that executing multiple local TD steps can lower the communication complexity of MARL-PE compared to vanilla consensus-based decentralized TD learning algorithms.\nSecond, the paper theoretically shows that executing multiple local TD steps has higher communication complexity than the batch approach under same sample complexity condition.\nFinally, executing multiple local TD steps is shown to perform similarly to the batch approach in practice under certain settings. \n", "summary_of_the_review": "My current recommendation is to accept.\n\nMy reasons are the following:\nTechnical novelty: this paper gives a first answer to an open problem under certain settings\nGood quality: the paper is well written: clear presentation, enough motivation. Detailed experiments, etc.\n", "strength_and_weaknesses": "Strength:\n\n1. Result novelty: this paper conducted a theoretical analysis of the approach of multiple local TD steps in terms of communication complexity, and showed that this approach indeed lowers communication complexity, which has not been shown before. This seems novel to me.\n\n2. Technical novelty: the analysis of this paper has its technical novelty. Although the paper borrows technical tools from other works, it faces coupled challenges due to: underlying structure of TD, dynamic setting (i.e. MDP), and reward heterogeneity across agents.\n\n3. Theoretical results are clearly stated without ambiguity.\n\n4. Extensive empirical results are included which supports the theory. \n\n---\nWeakness: \nThere is no major technical weakness of this paper in my opinion. Still, I think the following is worth mentioning. \n\n1. It is not clear to me why Assumption 1 matters. Specifically, what would happen/why analysis fails if the stationary distribution is not unique? \nIs Assumption 1 very practical? \nDoes it simplify the problem? What might be the extra challenges if the assumption does not hold?\n\n---\nMinor comments/Questions:\n\n1. Assumption 4: each agent shares the same value function (i.e. same feature $\\phi$ and parameter $w$)? The current statement is confusing. Why not say the global value function $V$ adopts a linear structure?\n\n2. Typo: above section 3.2: definition of V-function: $\\gamma^t$ instead of $\\gamma$. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "UH7y83oliyd", "reviewer": "Reviewer_stTJ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "Authors present a generalized TD learning for the MARL setting, with local updates occurring for K > 1 iterations for each instance of communication. Sample complexities at the inner loop (local TD updates) and the outer loop (consensus updates) are computed based on mild assumptions. Theoretical formulation predicts a worse complexity for the outer loop for the TD update method to match that of the batch learning method, but experiments produce more optimistic numbers, for reasons not provided/studied in the paper.", "summary_of_the_review": "The paper's main strength lies more in the analyses on the feasibility and comparability of local TD updates in MARL-PE than in designing and implementing a novel algorithm itself. If the paper is indeed best viewed in this light, then it would be pleasant to see some updates on the literature review, complexity analyses in the experiments, and the fairness in comparison.", "strength_and_weaknesses": "The paper addresses a well-defined niche. By allowing for multiple local TD updates, a more general version of the MARL-PE problem is constructed and its complexities calculated.\n\nThe argument made can be even stronger with i) a more comprehensive literature review and a more strategic positioning, ii) some attempts to provide insight as to the conditions under which local TD updates would perform at its computed worst complexity, and iii) discussion on the fairness of the tested algorithms in Figures 1 and 3, perhaps by including Figures 4 and 6 in the main paper.\n\nIt would be interesting to cover an important line of MARL research related to the exchange of state information, and especially the succinct packetization of state information to exchange. Works investigating emergent communication may prove important (and arguably necessary) contenders to the local TD updates in the sense that the message-generating function can also be considered a learnable parametrization. Whereas in this paper, that function would be just the identity function accepting the parameters (after local TD updates), studies such as SchedNet (ICLR 2019) would subject the individual state information to undergo feature extraction via a trainable logic (i.e., neural networks). With the common goal of improving communication efficiency, how does the presented method compare against emergent communication methods?\n\nInvestigation on the following questions would make the paper more insightful: Under what circumstances does the computed (worst-case) communication complexity actually manifest in experiments? Do those circumstances also affect whether batch learning performs at its computed worst?\n\nFigures 1 and 3 can be better explained, with particular emphasis on the fairness of the tested algorithms. Since the x-axis is the communication rounds, Figures 1 and 3 do not correctly reflect the K > 1 \"advantage\" given to the local TD update method. At every x-axis tick, the proposed method runs for K (50 or 100 or etc.) iterations, so the graphical display can be misleading, unless accompanied by graphs such as Figures 4 and 6, which picture a more honest view by taking into account both K and L and plotting the errors against sample numbers. Indeed, it is sometimes the case (Fig. 4(a)) that batch learning does better than local TD updates, depending on the choice of K and L. If that really is the case, a further empirical analysis on the effects of K and L on the competition between batch learning and local TD updates may be an interesting addition.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject