Multi-Agent Reinforcement Learning in Stochastic Networked Systems
Authors: Yiheng Lin
Guannan Qu
Longbo Huang
Adam Wierman
Venue: NeurIPS 2021 Poster (2021)
Keywords: Multi-agent reinforcement learning
networks
state aggregation
actor-critic

Abstract: We study multi-agent reinforcement learning (MARL) in a stochastic network of agents. The objective is to find localized policies that maximize the (discounted) global reward. In general, scalability is a challenge in this setting because the size of the global state/action space can be exponential in the number of agents. Scalable algorithms are only known in cases where dependencies are static, fixed and local, e.g., between neighbors in a fixed, time-invariant underlying graph. In this work, we propose a Scalable Actor Critic framework that applies in settings where the dependencies can be non-local and stochastic, and provide a finite-time error bound that shows how the convergence rate depends on the speed of information spread in the network.  Additionally, as a byproduct of our analysis, we obtain novel finite-time convergence results for a general stochastic approximation scheme and for temporal difference learning with state aggregation, which apply beyond the setting of MARL in networked systems.

Multii-Agent Reinforcement Learning in Stochastic Networked Systems
Yiheng Lin
Guannan Qu CMS, Caltech gquêcaltech. edu
CMS, Caltech riiheng@ecaltcch.ed
Longbo Huang III, Tsinghua University
Adam Wierman CMS, Caltech adamwiccattccin
longjohhanngsta inghua. edu. on
Abstract
We study multi-agent reinforcement learning (MARL) in stochastic network of agents. The objective is to find localized policies that maximize the (discounted) global reward. In general, scalability is challenge in this setting because the size the global state/action space can be exponential in the number of agents. Scalable algorithms only known in cases where dependencies static, fixed and local, e.g.. between neighbors in a fixed, time-invariant underlying graph. In this work, we propose Scalable Actor Critic framework that applies in settings where the dependencies can be non-local and stochastic, and provide a finite-time error bound that shows how the convergence rate depends the speed of information spread in the network. Additionally, as a byproduct of our analysis, we obtain novel finite-time convergence results for general stochastic approximation scheme and for temporal difference learning with state aggregation, which apply beyond the setting of MARL in networked systems.
Introduction
Multi-Agent Reinforcement Learning (MARL) has achieved impressive performance in a wide array of applications including multi-player game play 12 3M multi-robot systems [13, and autonomous driving [25]. In comparison to single-agent reinforcement learning (RL), MARL poses many challenges, chief of which scalability [T7] Even if each agent's local state/action spaces
small, the size of the global state/action space can be large, potentially exponentially large in the number of agents, which renders many RL algorithms such as Q-learning not applicable.
promising approach for addressing the scalability challenge that has received attention in recent years is to exploit application-specific structures, e.g., [18
38 A particularly important example of such a structure is a networked structure, e.g. applications in multi-agent networked systems
35
such social networks 7 27 communication networks 660 51]. queueing networks K and
smart transportation networks (59 In these networked systems, it is often possible to exploit static,
32] e.g., the fact that agents only interact with fixed set of neighboring agents throughout the game. This sort of dependency structure often leads to scalable,
local dependency structures [6
distributed algorithms for optimization and control [6 I 32 and has proven effective for designing
scalable and distributed MARL algorithms, e.g. 35 38
This work was supported by NSF grants CNS-2106403 and NGSDI-2105648, with additional support from Amazon AWS, PIMCO, and Resnick Sustainability Insitute. Yiheng Lin was supported by Kortschak Scholars program. The work of Longbo Huang was supported by the Technology and Innovation Major Project of the Ministry of Science and Technology of China under Grants 2020AAA0108400 and 2020AAA0108403,
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

However, many real-world networked systems have inherently time-varying, non-local dependencies. For example, in the context of wireless networks, each node can send packets other nodes within a fixed transmission range. However, the interference range, in which other nodes can interfere the transmission, can be larger than the transmission range [53.. As a result, due to potential collisions, the local reward of each node not only depends on its own local state/action, but also depends on the actions of other nodes within the interference range, which may be more than one-hop away. In addition, node may be able to observe other nodes' local states before picking its local action [33] Things become even more complex when mobility and stochastic network conditions are considered. These lead to dependencies that are both stochastic and non-local. Although one can always fix and localize the dependence model, this leads to considerably reduced performance. Beyond wireless networks, similar stochastic and non-local dependencies exists in epidemics 60 social networks
7 227
and smart transportation networks (59]
A challenging open question in MARL is to understand how to obtain algorithms that are scalable in settings where the dependencies are stochastic and non-local. Prior work considers exclusively static and local dependencies, e.g., B5 3S
It is clear that hardness results apply when the dependencies are too general [24]. Further, results in the static, local setting to this point rely on the concept of exponential decay 35 16,, meaning the agents' impact each other decays exponentially in their graph distance. This property relies on the fact that the dependencies are purely local and static, and it is not clear whether it can still be exploited when the interactions more general. This motivates an important open question: Is it possible to design scalable algorithms for stochastic, non-local networked MARL?
Contributions. In this paper, we introduce a class of stochastic, non-local dependency structures where every agent is allowed to depend on a random subset of agents. In this context, we propose and analyze a Scalable Actor Critic (SAC) algorithm that provably learns a near-optimal local policy in scalable manner (Theorem 2.5 This result represents the first provably scalable method for stochastic networked MARL. Key to our approach is that the class of dependencies we consider leads to ju-decay property (Definition 2. This property generalizes the exponential decay property underlying recent results such as Bi which does not apply to stochastic non- non-local dependencies, and enables the design of an efficient and scalable algorithm for settings with stochastic, non-local dependencies. Our analysis of the algorithm reveals an important trade-off: as deeper interactions appear more frequently, the "information" can spread more quickly from one part of the network to another, which leads to the efficiency of the proposed method to degrade. This is to be expected, as when the agents are allowed interact globally, the problem becomes single-agent tabular Q-learning problem with an exponentially large state space, which is known to be intractable since the sample complexity polynomial in the size of the state/action space
24
The key technical result underlying our analysis of the Scalable Actor Critic algorithm is a finite-time analysis of a general stochastic approximation scheme featuring infinite- norm contraction and state aggregation (Theorem B.I). We apply this result to networked MARL using the local neighborhood of each agent to provide state aggregation (SA). This result also applies beyond MARL. Specifically, show that it yields finite-time bounds on Temporal Difference (TDYQ learning with state aggregation (Theorem B.2 To the best of our knowledge the resulting bound is the first finite-time bound on asynchronous Q-learning with state aggregation. Additionally, it yields a novel analysis for TD- learning with state aggregation (the first error bound in the infinity norm) that sheds new insight into how the error depends on the quality of state abstraction. These two results are important contributions in their own right. Due space constraints, we discuss asynchronous Q-learning with state aggregation in Appendix D.4
Related literature. The prior work that is most related to our paper is 38 which also studies MARL in a networked setting. The key differrenc is that we allow the dependency structure among agents to be non-local and stochastic, while (M requires the dependency structure be local and static. The generality of setting means techniques from 38) do not apply and adds considerable complexity to the proof in two aspects. First, instead of analyzing the algorithm directly like 38]
we derive a finite-time error bound for TD learning with state aggregation (Section and 3.2 and then establish its connection with the algorithm (Section 2 Second, we need more general decay
and
property (Definition 2.1) than the exponential one used in 38 Defining and establishing this general decay property for the nocal and stochastic setting is highly non-trivial (Section)
2

---

More broadly, MARL has received considerable attention in recent years, see [57] for a survey. The line of work most relevant to the current paper focuses on cooperative MARL. In the cooperative setting, each agent can decide its local actions but share common global state with other agents. The objective is to maximize a global reward by working cooperatively. Notable examples of this approach include GG I0 and the references therein. In contrast, we study situation where each agent has its own state that it acts upon. Despite the differences, like our situation, cooperative MARL problems still face scalability issues since the joint-action space is exponentially large. A variety of methods have been proposed to deal with this, including independent learners M 29) where each agent employs single-agent RL policy. Function approximation is another approach that can significantly reduce the space/computational complexity. One can use linear functions 58 or neural networks [28] in the approximation. A limitation of these approaches is the lack of theoretical guarantees on the approximation error. In contrast, our technique not only reduces the space/computational complexity significantly, but also has theoretical guarantees on the performance loss in settings with stochastic and non-local dependencies.
The mean-field approach 45 56 [ provides another way to address the scalability issue, but under very different settings compared to ours. Specifically, the mean-field approach typically assumes homogeneous agents with identical local state/action space and policies, and each agent depends on other agents through their population or "mean" behavior. In contrast, our approach considers a -nterrrtteaatoon model, where there is underlying graph and each agent depends neighboring agents in the graph. Further, our approach allows heterogeneous agents, which means that the local state/action spaces and policies can differ among the agents.
Another related line of work uses centralized training with decentralized execution, e-g.. 28 where there is a centralized coordinator that can communicate with all the agents and keep track of their experiences and policies. In contrast, our work only requires distributed training, where we constrain the scale of communication in training within the k-hop neighborhood of each agent.
More broadly, this paper contributes scalable algorithms for learning in networked systems. The specific form of exponential decay that we generalize related to the idea of "correlation decay" studied in [16 [7], though their focus is on solving static combinatorial optimization problems whereas ours is on learning policies in dynamic environments. Most related to the current paper 33 which shows an exponential decay property in restricted networked MARL model with purely local dependencies. In contrast, we show more general jı-decay property holds for a general form of stochastic, non-local dependencies.
growing literature that uses exponential decay to derive
The technical work in this paper contributes to the analysis of stochastic approximation (SA), which has received considerable attention over the past decade [54] 44 |II 55) Our work is most related to 37,, which uses an asynchronous nonlinear SA to study the finite-time convergence rate for asynchronous Q-learning on single trajectory. Beyond [37] there are many other works that use SA schemes to study TD learning and Q-learning, e.g.
44 200 The finite-time error bound for TD learning with state aggregation in our work most related to the asymptotic convergence limit given in 49 and the application of SA scheme to asynchronous Q-learning in [7 Beyond these papers, other related work in the broader area of RL with state aggregation includes 226 23
[
We add to this literature with a novel finite-time convergence bound for a general SA with state aggregation. This result, in turn, yields the first finite-time time error bound in the infinity norm for both TD learning with state aggregation and Q-learning with state aggregation.
2 Networked MARL
We consider network of agents that are associated with an underlying undirected graph G = (N, E). where V 21, nu denotes the set of agents and & N N denotes the set of edges. The distance (i.j between two agents i and is defined as the number of edges on the shortest path that connects them on graph G. Each agent is associated with its local state s; E S, and local action a; E A, where S; and A, are finite sets. The global state/action is defined as the combination of all local states/actions, i.e., 8 (81,..., ,.,) E S == S₁ x ... x Sn, and a = (41, .0n) E A == A x ... x An. We use No to denote the hop neighborhood of agent i on G. i.e., No = [j E d) S k). Let (w) == sup, |. For subset M C N, we use 8M / to denote the tuple formed by the states/actions of agents in M.
3

---

Before we define the transitions and rewards, we first define the notion of active link sets, which are directed graphs on the agents A and they characterize the interaction structure among the agents. More specifically, an active link set is set of directed edges that contains all self-loops, i.e., a subset of N V and a super set of (i, i) | E W.. Generally speaking. (i.) E I. means agent j can affect agent in the active link set L. Given an active link set L,, we also use (L) := [j E N (i. i) E L.) to denote the set of all agents (include itself) who can affect agent in the active link set L. In this paper, we consider pair of active link sets (Li, L;) that is independently drawn from some joint distribution D at each time step & where the distribution D will be defined using the underlying graph G later in Section 2.1 The role of Lj/ L; is that they define the dependence structure of state transition/rewwad at time t. which we detail below.
Transitions. At time t, given the current state, action s(t), a(t) and the active link set Li, the next individual state st + 1) is independently generated and only depends on the state/action of the agents in (TgT.). In other words, we have,
((s(t++)) + ())=s(),, a()), L;) L0)
II Pt(ss(t (x))s, REN
Rewards. Each agent is associated with local reward function rs. At time t. it a function of L and the state/action of agents in Nx(T.): rx(T4, (N),))) The global reward r(t) is defined to be the summation of the local rewards rt()).
Policy. Each agent follows a localized policy that depends its 8-hop neighborhood, where 3 2 0 is a fixed integer. Specifically, at time step L, given the global state s(l), agent i adopts a local policy & parameterized by 0g to decide the distribution of (t) based on the the states of agents in N.
Our objective is for all the agents to cooperatively maximize the discounted global reward, i.e., J(0) = Eswao
Eeo )'r(s(t) a(t)) | s(0)- = where To is given distribution on the initial is the global stage reward defined as the sum of all local
global state, and we recall rewards time t.
Examples. To highlight the applicability of the general model, we include two examples of networked systems that feature the dependence structure captured by our model in Appendix A a wireless communication example and an example of controlling a process that spreads over a network.
Note that a limitation of our setting is that the dependence structure we consider is stationary, in the sense that dependencies are sampled i.idd from the distribution D. It is important to consider more general time-varying forms (e.g. Markovian) in future research.
Background. Before moving on, we review few key concepts in RL which will be useful in the rest of the section. We use o. to denote the distribution of s()) under policy 0 given that :()) To. A well-known result 47) is that the gradient of the objective (0) can be computed
by (= (s, a)V log (a s), where distribution x² (s) (1 7) E 7 (s) is the discounted state visitation distribution. Evaluating the Q-function (s, a) plays a key role in approximating (O). The local Q-function for agent is the discounted local reward, i.e. (+(s,a) Eçe
/rr((t) 7ro7(r((t) (0)
s, a(0) = a), where use (t) to denote the local reward
of agent é at time step t. Using local Q- f-functions, we can decompose the global Q-function as (s) = Σm_ Q. (s, a), which allows each node to evaluate its local Q-function separately.
key challenge in our MARL setting is that directly estimating the Q-functions is not scalable since the size of the Q-functions is exponentially large in the number of agents. Therefore, in Section 2. we study structural properties of the f-funtioons resulting from the dependence structure in the transition 1 which enables us to design a scalable RI. algorithm in Section 2.2
2.1 j-decay Property
One of the core challenges for MARL is that the size of the Q function is exponentially large in the number of agents. The key to our algorithm and its analysis the identification of a novel structural
Herr, correlations between LE and LF are possible

---

decay property for the Q-function, which says that the local Q-function of each agent i is mainly decided by the states of the agents who are near This property critical for the design of scalable algorithms because it enables the agents to reduce the dimension of the Q-function by truncating its dependence of the states and actions of far away agents. Recently, exponential decay has been shown to hold in networked MARL when the network is static K8 5G], which is exploited to design scalable RL algorithm. However, in stochastic network settings it is too much to hope for exponential decay in general [4], and so we introduce the more general notion of jı-decay here, where μ is function that converges to as k tends to infinity. The case of exponential decay that has been studied previously corresponds to μu(())
2 /11 7). The formal definition of fı-decay is given below,
where for simplicity, we use i - j to denote (2,j) E L and denote N >>>NNN
Definition 2.1. For function μ N + Et that satisfies lim p((K) 0, the p-decay property holds for any policy 9 and any E NN the local Q function Q2 satisfies |Q2 (s. a) - Q2 (s', a') s p(x) for any (s, a), (s', d') that are identical within NÇ, i.e. SNT s'y:: aN; = d'y..
Intuitively, if the u-decay property holds and μ(K) decays quickly as increases, we can approxi- mately decompose the global Q function Q" (s, 1
n Ex= Q (s. a) R E Q (SN7, (N;;) where Q; only depends on the states and actions within the k-hopp neighborhood of agent i. Before our work, 4d empirically showed that such value decomposition allows efficient training of MARL. Under the assumption that such decomposition exists, [ propose an approach to learn this decomposition. In contrast, as we prove in this section, the μ decay property holds provably and therefore, the global Q function can be directly decomposed in the networked MARL model and that the error of such decomposition is provably small.
Our first result is Theorem 2. which shows the relationship between the random active link sets and the p-decay property. The proof of Theorem 2.1 is deferred to Appendix B.I
Theorem 2.1. Define L as the static active link set that contains all pairs (i.j) whose graph distance on G is less than or equal to 3, which is the dependency of local policy. Let random variable X, (x) denote the smallest E IN such that there exists chain of agents
15
La
14
L1
1, 3 L" 15.
J6
52
that satisfies jä E N and jt " i. The p-decay property holds for m(() [[x[[]
To make the j-decay result more concrete, we provide several scenarios that yield different upper bounds on the term E xx())) In the first scenario, we study the case where long range links do not exist in Corollary 2 In this case, obtain exponential decay property that generalizes the result in [38. A proof is in Appendix [.2
Corollary 2.2 (Exponential Decay). Consider a distribution D of active link sets that satisfies
Pue,,ry-p((1))) ((..)) E L") 0, for all i,j E N s.f. dg (i, 2
PuAAem ((..)) E T.'} 0, for all i,j N s.f. dg (1, oz.
Then, [((e) S Cpp, where p 2/(a = - =2)(a++
In the second scenario, long range active links can occur, but with exponentially small probability with respect to their distance. In this case, we can obtain a near-exponential decay property where (*x) = ((p²/ x)) for some E (0, 1). A proof can be found in Appendix B.3
Theorem 2.3 (Near-Exponentia) Decay). Suppose the distribution D of active link sets satisfies
Pite (i, E L" UL S cxd666.3) for all i, EN,
where e 2 1,1 >> O are constants. If the largest size of the k. neighborhood in the underlying graph G can be bounded by polynomial of k, ie., there exists some constants co 2 1, ng such
that [tj E N dg(i.j) = xH] I <c(xx+ + 1)m0 holds for all i, then E[ E[>x.(c- I Cp Cp= (1+tott for some positive constant C and decay rate p < 1.
is interesting to compare the result above with models of the so-called "small world phenomena" in social networks, e.g., [4]. In these models, a link (i,j) occurs with probability 1/poly(dg (i,
Thhe explicit expression of C and p can be found in Appendix B.3
5

---

Algorithm Scalable Actor Critic
1: for m m==00 0, 2, do
2: Sample initial global state s(0) n0-
3: Each node takes action (0( ~ <. (m)) (- Ng (0)) to obtain the global state s(1.
4: Each node records N (0), aN (0), r: and initialize Q to be all zero vector.
5:
for = .... T do
6:
Each node takes action a; (t) :: (m)) (- Nyp (t))
(t)(()) to obtain the global state s(t + 1).
7:
Each node update the local estimation Q; with step size a 1-1+2
H
(SNT (t- a), (t 10-1) 1))
a)-1) (Sxz (1 1), aNp (t- 1)) ai (Ti(1) 2 aN) (0))
Q (8x7, (sNg, aNz) for (sN) + (SNz (t 1), aNy (t 1)).
8: Each node approximate Vo, (0) by (m)) Ei NE O (sNy (t), aNy (t)) log (ogc. (m (a:(t) (xxe(()))
9: Each node conducts gradient ascent by (m + 1) = 8m(m) + (m))
opposed to the exponential dependence in Lemma 2.3 In this case, is lower bounded by (r), which leads us to conjecture that μ(()) is also upper bounded by ((1/poly( Thus, when information spreads "slowly" it helps a localized algorithm to learn efficiently.
function μτx))
2.2 A Scalable Actor Critic Algorithm
Motivated by the ı-decay property of the Q-functions, we design a novel Scalable Actor Critic algorithm (Algorithm M1 for networked MARL problem, which exploits the μ-decay result in the previous section. The Critic part (from line 2 to line 7 uses the local trajectory {(SNT, ONr ( to evaluate the local Q-functions under parameter (m). Intuitively, the p-decay property guarantees that we can achieve good approximation error even when K is not large. The Actor part (from line gto to line ( computes the estimated partial derivative using the estimated local Q-functions, and
uses the partial derivative to update local parameter 0,. The step size sequence {mm) will be defindd in Theorem
B.2 Compared with the Scalable Actor Critic algorithm proposed in B8) Algorithm I extends the policy dependency structure considered. No longer is the dependency completely local; it now extends to all agents within the 8-hop neighborhood. Interestingly, the time-varying dependencies do not add complexity into the algorithm (though the analysis is more complex).
Algorithm is highly scalable. Each agent needs only to query and store the information within its k-hop neighborhood during the learning process. The parameter can be set balance accuracy and complexity. Specifically, as k increases, the error bound becomes tighter at the expense of increasing computation, communication, and space complexity.
2.3 Convergence
We now present our main result, a finite-time error bound for the Scalable Actor Critic algorithm (Algorithm[I | that holds under general (non-local) dependencies. To that end, we first describe the assumption needed our result. It focuses on the Markov chain formed by the global state-action pair (s. under fixed policy parameter 0 and is standard for finite-time convergence results in RL, e.g., 37
Assumption 2.1. Under any fixed policy 8, {2(t) = (s(t), a(t)) is an aperiodic and ir-
reducible Markov chain on state space 2 S x A with unique stationary distribution de = (de E 2). which satisfies d² > 0,Yz E Z. Define d de = >' >E d8 (2)
and dk()) = iny dl (2'). There exists positive constants K1, K2 such that K2 > and Zz' Z, Vt 0,spKKz2 Esex de EsexP(z(t
z(0) = z')l s K/e-

---

We next analyze the Critic part of Algorithm I within given outer loop iteration m. Since the policy fixed in the inner loop, the global state/action pair (s.a) a) in the original MDP can be viewed as the state of a Markov chain. We observe that each local estimate ( aNF) can be viewed as a form of state aggregation, where the global state (s, a) is "compressed" to lisss) := (#N7, dN;; ). Broadly speaking, the technique of state aggregation is one of the casiest-to-deplo schemes for state space compression 21 [R while its final performance relies heavily on whether the state aggregation map h only aggregates "similar" states. To have a good approximate equivalence, we need to find good h, i.e., if two states are mapped to the same abstract state, their value functions are required to be close (to be discussed in Theorem 3.2). In the context of networked MARL,, the ja decay property (Definition 2.1) provides a natural mapping for state aggregation h(s, a) == (s aNy)) ) which we defined earherr This mapping h maps the global state/action to the local states/actions in agent i's k-hop neighborhood and the y-decay property guarantees that if l1(8, a) = his',, aa),, the difference in their Q-functions is upper bounded by ((x), which is vanishing as k increases. This shows that the mapping h we used is "good" in the sense it aggregates very similar global state-action pairs. This idea leads to the following theorem about the Critic part of Scalable Actor Critic (Algorithm DD]
Theorem 2.4. Suppose Assumption 2. and u-decay property (Definition 2.7 hold. Let the step 2
Define constant C2- := 4K (1 + 2K₂ + 4H). Then, inside outer loop iteration m, for each i E NN, with probability
size be a2 = z+to with to = max 4H, 2Kg I), and H Z (1-7)o'(())
at least 1 - 8, we have (uP(s.))SXAA)
( (s)a) - Q7 (SNT, aNt) S VT+
Co + T46 I-7
mla)
10H where the constants given by Ca
K2 log T log
( [lo (1S(m)k22)) + log log and C.a
(1->)²
(1-7)2 max 144KsH logT + Cb, 2K2 log T + to
(1s))
The proof of Theorem 2.4 can be found in Appendix B.4 The most related result in the literature to
Theorem 2 is Theorem in [38. In comparison, Theorem 2. applies for more general, potentially non-local, dependencies and, also, improves the constant term by a factor of 1/(1- - 7).
To analyze the Actor part of Algorithm ! we make the following additional boundedness and Lipschitz continuity assumptions on the gradients. These are standard assumptions in the literature.
Assumption 2.2. For any i, 023 8 N. and Oz, we assume |e, e. log Sh (a: (x
}| S W. Then, for any Lg. Vo log (a |>]]| < W VE W.P. We further assume V is W -iischitz in O.
Intuitively, since the quality of the estimated policy gradient depends on the quality of the estimation of Q-functions, if every agent has learned good approximation of its local Q-function in the Critic part of Algorithm D the policy gradient can be approximated well. Therefore, the Actor part can obtain a good approximation of a stationary point of the objective function. We state the sample complexity result in Theorem
2.3 and defer the detailed bounds and a proof to Appendix B.5
Theorem 2.5. Under Assumption at least 1- 8, we need to choose such that μ(K) = O( 2(1 -))²)). The number of required iterations of the outer loop should satisfy M [E( 2poly (W, W ) and the number of required iterations of the inner loop is T = 52(c=2poly(M) (W, ... K2, - log f (og(/))))))
2.2 reach an O -aproxipt stationary point with probability
Note that W scales with the number of agents n. Thus, Theorem 2.5 shows that the complexity of our algorithm scales with the largest state-action space size of any k-hop neighborhood and the number of agents n, which avoids the exponential blowup in n when the graph is sparse and achieves scalable RL for networked agents even under stochastic, non-local settings.
3 Proof Idea: Stochastic Approximation and State Aggregation
In this section, we present the key technical innovation underlying our results on MARL in Theorem 2.4] a new finite-time analysis of a general asynchronous stochastic approximation (SA) scheme. As we mention in Section 2 the truncation enabled by p-decay provides a form of state aggregation, which we analyze via a general SA scheme in Section 3.1 Further, this SA scheme is of interest more broadly, e.g., to the settings TD learning with state aggregation (Section 3.2) and asynchronous Q-learning with state aggregation (Appendix D.4
7

---

3.1 Stochastic Approximation
Consider finite-state Markov chain whose state space is given by N (1. .n. Let fiel be the sequence of states visited by this Markov chain. Our focus is generalizing the following asynchronous stochastic approximation (SA) scheme, which is studied in [48] A1 52 Let parameter
R.V, and F : R RR-V be 7-contraction in the infinity norm. The update rule of the SA scheme is given by
F4, (t + 1) = Fi, (o.
24, (t) w(t)),
(2)
I (t + 1) = (t) for j + 4.j E.
where wt) is noise sequence. It is shown in 37 that parameter zr()) converges to the unique fixed point of F' at the rate of (1/VE).
While general, in many cases, including networked MARL, we do not wish to calculate an entry for every state in A in parameter æ, but instead, wish to calculate "aggregated entries." Specifically, at each time step, after & is generated, we use a surjection h to decide which dimension of parameter should be updated. This technique, referred to as state aggregation, is one of the easiest-to to-deploy schemes for state space compression in the RL literature 221 3 In the generalized SA scheme, our objective is to specify the convergence point well obtain a finite-time error bound.
Formally, define the generalization of (2. let A [1,-... n be the state space of {it} and M = {1, [.. m), (m S. n) be the abstract state space. The surjection h .N - . is used to convert every state in V its abstraction in MM. Given parameter x E RM and function F RR-V + RA, we consider the generalized SA scheme that updates xtt) E RMM starting from
x<0)= 0,
(M(c)(L+ + 1) = (l) + an (F, ING w())) 2z(t+ + =z)) for j + h(t). M,
(3)
where the feature matrix & E &R- is defined as
1 0
h(1) = WIEN.JEM. otherwise
2
(4)
In order to state our main result characterizing the convergence of B we must first state a few definitions and assumptions. To begin, we define the weighted infimity norm as in [37,, except that extend its definition so to define the contraction of function F. The reason infinity norm as opposed to the standard infinity norm is that its generality can be used in certain settings for undiscounted RL, as shown in 48
the weighted
Definition 3.1 (Weighted Infinity Norm). Fix a positive vector u E RR.. For I E R.M, we define ||~||, := suPseM
For x E RRVV we define |æ||, == sup (wce)
Jzd.
Next, we state our assumption on the mixing rate of the Markov chain {ie), which is common in the literature (50 44 It holds for any finite-state Markov chain which is aperiodic and irreducible (5).
Assumption 3.1 (Stationary Distribution and Geometric Mixing Rate). {ir an aperiodic and irreducible Markov chain on state space N with stationary distribution d = (di,d2.-.. .d,))) Let d' -EEn-'() de and o' inf jeM d'.. There exists positive constants K2, K2 which satisfy that SuPSCN Ee E P(i i in = j)} < K1 exp(-t/X/3) Vj E A Vt 2 O and K₂ 2 1.
Our next assumption ensures contraction of F. It is also standard, e.g., 48 F has a unique fixed point y² Assumption 3.2 (Contraction). Operator F is a y contraction in I1-Il i.e., for any x, y E R-V, we II < 7||x yll,.- Further, there exists some constant C. > O such that for any I. E R.A we have [[F(z))l, I 7 |x||, C.
and ensures that
for
have [x) - -Fly),,
In Assumption 3.2 notice that the first sentence directly implies the second with C = (1 + 7) I1y" Il. ll where y" RR- is the unique fixed point of F. Further, while Assumption 3.2 implies that F has a unique fixed point y", we do not expect our stochastic approximation scheme to converge to Instead, we show that the convergence is to the unique x² that solves
IIF (1x") = z², where II == (4) DΦ)
-1 4 D.
(5)
8

---

Here D = diag(d1. d2..... dn)) denotes the steady-state probabilities for the process {4 [. Note that x' is well-defined because the operator IIF (-),, which defines a mapping from R to R.M, is also
contraction in I|- We state and prove this as Proposition C.1 in Appendix C.1
Our last assumption is the noise sequence ve(t). It is also standard, e.g.- Assumption 3.3 (Martingale Difference Sequence). wy is Fit1 measurable and satisfies Ew(() | Fi = O. Further, [w(t] I W almost surely for constant tt.
We are now ready state our finite-time convergence result for stochastic approximation.
Theorem 3.1. Suppose Assumptions 3.7
3.2 hold. Further, assume there exists constant
_H_ with to I 2 ||=* ll, such that Vt, ||x(()]|, S I almost surely Let the step size be a 1446
max( max(4H, 2Kg T), and H 2 a'(1-7) Let x² be the unique solution of equation [IF((x)) x²,
C2 == 4F 4F+ and define constants C1 2 + C+
2, Cs 2Kg (2 C) 4H).
e
Then, with probability at least
C.
C.
[Tx(T) - ='11,. S
+
to to
T+
where the constants are given by Ca = 4HC² I-7
K2 log T (log( 4mkKyY) + log log T) and C²
4 max 18K,O, log T Ca 28(2Kg log T+ta) }.
7)o'
1-7
A proof of Theorem 3.1 can be found in Appendix C Compared with Theorem 4 in B7). Theorem 3.1 holds for a more general SA scheme where state aggregation is used to reduce the dimension of the parameter The proof technique used in Br does not apply to setting because our stationary point x² has a more complex form To do the generalization, we need to use a different error decomposition method compared to 37 that leverages the stationary distribution D rather than the distribution of & condition on 4 (see Appendix C.2 for details). Because of this generality, Theorem 3.1 requires stronger but standard assumption on the mixing rate of the Markov chain {
3.2 State Aggregation
To illustrate the impact of our analysis of SA (Theorem 3.1 beyond the network setting, we study simpler application to the cases of TD-learnng and Q-learning with state aggregation in this section. Understanding state aggregation methods is a foundational goal of analysis in the RL literature and it has been studied in many previous works, e.g., 26 23 22
Further, the result extremely useful in the analysis in networked MARL that follows since the ju-decay property we introduce (Definition 2.T) provides a natural state aggregation in the network setting (see Corollary 2.4). Due to space constraints, in this section we only introduce the results on TD-learning: the results on Q-learning are given in Appendix D.4
In TD learning with state aggregation
13
49
given the sequence of states visited by the Markov
chain is } the update rule of TD( is given by
On(i)) (t + 1) (n(i)(() ar(re 70( (t)) (t + (t) for + h(is), M,
(6)
where h : V + MM is surjection that maps each state in N to abstract state in M and r; is the reward at time step such that EE|r,] = r(ir, 4t41).
Taking F' as the Bellman Policy Operator, i.e., the i'th dimension of function F' is given by F((V) = Ep- [r(,, 8') + W.
The value function (vector) V* is defined as V E|>:= 7'r(is, det1) i0 i0 49 By defining the feature matrix Ob as 4 and the noise sequence as
((t)= T. 10((0)01)))) - -V--PP(-a.) [r i') + Once (()e)())]}
we can rewrite the update rule of (D( in (6) in the form of an SA scheme B Therefore, we can
apply Theorem 3.T to obtain a finite-time error bound for TD learning with state aggregation. A proof
of Theorem 3.2 can be found in Appendix D.2
'The assumption follows from Assumptions
3.2 and
3.3 See Proposition C.2 in Appendix
C33

---

Theorem 3.2. Let Assumption 3.1 hold for the Markov chain {it} and let the stage reward rt be upper bounded by almost surety. y. Assume that if h((i) = h(z') i, E N,, we have V V - C for constant Ç. Consider (D) with the step size at L+16' where to = ma 2K₂ log T) and
2 H 2 v'-1 Define constant C4 4K1(1 (1 + 2K + +HH). Then, with probability at least 6,
Co
C.
[ - ol 1
+
VT+ + to
+
where the constanty given by C. 8F (1-))2 max 148KgH Tog + Ca, 2K2 log + to).
40Hr [1-1)²
K2 log T (log( (#makT)) + log log T) and C.
The most related prior results to Theorem 3.2 are 4
In contrast to these, Theorem considers the infinity norm, which is more natural for measuring error when using state aggregation. Further, our analysis is different and extends to the case Q-learning with state aggregation (see Appendix D.4p, where we obtain the first finite-time error bound. Moreover, unlike [], our TD-learning algorithm does not require a projection step.
Concluding Remarks
In this paper, we propose and analyze the Scalable Actor Critic Algorithm that provably learns near-optimal local policy in a setting where every agent is allowed to interact with a random subset of agents. The f-decay property, which enables the decentralized approximation of local Q functions, is the key to our approach.
There are a number of future directions motivated by the results in this paper. For example, we allow the interaction structure among the agents to change in a stochastic way in this work. It is interesting to see if such structure can be tame-varying in more general ways (e.g., Markovian or adversarial). Besides, although our Scalable Actor Critic algorithm consumes much less memory than a centralized tabular approach, the memory space required by each agent i to store Q₂ grows exponentially with respect to f()), which denotes the size of the largest k-hop neighborhood. Thus, memory problems may still arise if f grows quickly as x increases. Therefore, an interesting open truncated state/action pair
problem is whether can apply additional function approximations (SNg, aNz). ), and obtain similar finite-time convergence guarantees as Scalable Actor Critic.
References
[1] B. Bamich, F. Paganini, and M. A. Dahleh. Distributed control of spatially invariant systems. IEEE Transactions on automatic control, 47(7):1091-1107, 2002.
[2] D. P. Bertsekas. Dynamic Programmingg and Optimal Control, Vol. II. Athena Scientific, 3rd edition, 2007.
[3] D. P. Bertsekas and J. N. Tsitsiklis. Neuro-dynamic programming, volume 5, Athena Scientific Belmont, MA, 1996.
[4] J. Bhandari, D. Russo, and R. Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference On Learning T'heory, pages 1691-1692. PMLR, 2018.
[5] Bremaud. Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues. Texts in Applied Mathematics. Springer New York, 2013.
[6] L. Bu, R. Babu, B. De Schutter, al. A comprehensive survey of multiagent reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 38(2):156-172 2008
[7] D. Chakrabarti, Y. Wang, C. Wang, J. Leskovec, and C. Faloutsos. Epidemic thresholds in real networks. ACM Transactions on Information and System Security (TISSEC), 10(4):1, 2008.
[8] C. Claus and C. Boutilier. The dynamics of reinforcement learning cooperative multiagent systems. AAAI/IAAI. 19EEL.1999:00 1998:746-752, 1998.
10

---

[9] C. Dann, N. Jiang, A. Krishnamurthy, A. Agarwal, J. Langford, and R. E. Schapire. On oracle- efficient pac rl with rich observations. Advances in Neural Information Processing Systems, pages 1422-1432, 2018.
[10] T. Doan, S. Maguluri, and J. Romberg. Finite-time analysis of distributed TD(0) with lin- ear function approximation on multi-agent reinforcement learning. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learn- ing, volume 97 of Proceedings of Machine Learning Research, pages 1626-1635, Long Beach, California, USA, 09-15 Jun 2019, PMLR.
[11] T. Doan. Fimite-time analysis and restarting scheme for linear two-time-scale stochastic approximation, 2019.
[12] K. Dong, Y. Wang, X. Chen, and L. Wang. Q-learning with ucb exploration is sample efficient for sofiite-hhrizon mdp. arXiv preprint arXiv:1901.0933 2019.
[13] Y. Duan, X. Chen, R. Houthooft, J. Schulman, and P. Abbeel. Benchmarking deep reinforcement learning for continuous control. In International Conference on Machine Learning, pages 1329- 1338, 2016.
[14] D. Easley, J. Kleinberg, et al. Networks, crowds, and markets: Reasoning about highly connected world. Significance, 9:43-44, 2012.
[15] J. Foerster, G. Farquhar, T. Afouras, N. Nardelli, and S. Whiteson. Counterfactual multi-agent policy gradients. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[16] D. Gamarnik. Correlation decay method for decision, optimization, and inference in large-scale networks. In Theory Driven by Influential Applications, pages 108-121. INFORMS, 2013.
[17] D. Gamarnik,
Goldberg, and Weber. Correlation decay in random decision networks. Mathematics of Operations Research, 39(2):229-20) 261, 2014.
[18] H. Gu, X. Guo, X. Wei, and R. Xu. Q-learning for mean-field controls, 2020.
[19] H. Gu, X. Guo, X. Wei, and R. Xu. Q-learning for mean-field controls. arXiv preprint arXi::2002.04131 2020.
[20] D. hwan Lee and N. Hc. A unified switching system perspective and o.d.e. analysis of g-laarning algorithms. ArXiv, abs/1912.00227, 2019.
[21] N. Jiang. Notes on state abstractions. http://nan web. engr. 1l innoisss meo.sseece edu/ #1les/cs598/note// pdf 2018
[22] N. Jiang, A. Kulesza, and S. Singh. Abstraction selection in mosel-based reinforcement learning. In International Conference on Machine Learning, pages 179-188, 2015.
[23] N. K. Jong and P. Stone. State abstraction discovery from irrelevant state variables. In IJCAI, volume 8, pages 752-757, 2005.
[24] T. Lattimore and M. Hutter. Pac bounds for discounted mdps. In N. H. Bshouty, G. Stoltz, N. Vayatis, and Zeugmann, editors, Algorithmic Learning Theory, pages 220-334, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.
[25] D. Li, D. Zhao, Q. Zhang, and Y. Chen. Reinforcement learning and deep learning based lateral control for autonomous driving [application notes]. IEEE Computational Intelligence Magazine, 14(2):83-98, 2019.
[26] L. Li. T. J. Walsh, and M. L. Littman. Towards unified theory of state abstraction for MDPs. In ISAIM, 2006.
[27] M. Llas, P. M. Gleiser, J. M. López, and A. Díaz-Guilera. Nonequilibrium phase transition in a model for the propagation of innovations among economic agents. Physical Review E, 68(6):066101, 2003.

---

[28] R. Lowe, Y. Wu, A. Tamar, J. Harb, O. P. Abbeel, and I. Mordatch. Multi-agent actor-critic for mixed cooperative-compeitiee environments. In Advances in Neural Information Processing Systems, pages 6379-6390, 2017.
[29] I.. Matignon, G. Laurent, and Le Fort-Piat. Independent reinforcement learners in coopera- tive markov games: a survey regarding coordination problems. The Knowledge Engineering Review, 27(1):1-31, 2012.
[30] W. Mei, S. Mohagheghi, S. Zampieri, and F. Bullo. On the dynamics of deterministic epidemic propagation over networks. Annual Reviews in Control, 44:116-128, 2017.
[31] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al. Human-level control through deep rein- forcement learning. Nature, 518(7540):529, 2015.
[32] N. Motee and A. Jadbabaie, Optimal control of spatially distributed systems. IEEE Transactions on Automatic Control, 53(7):1616-15)) 2008.
[33] M. J. Neely. Optimal backpressure routing for wireless networks with multi-receiver diversity. In 2006 40th Annual Conference on Information Sciences and Systems, pages 18-25, 2006.
[34] C. H. Papadimitriou and J. N. Tsitsiklis. The complexity of optimal queuing network control. Mathematics of Operations Research, 24(2):293-305, 1999.
[35] G. Qu and N. Li. Exploiting fast decaying and locality in multi-agent mdp with tree dependence structure. In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 6479-6486. IEEE, 2019.
[36] G. Qu, Y. Lin, A. Wierman, and N. Li. Scalable multi-agent reinforcement learning for networked systems with average reward. Advances in Neural Information Processing Systems, 33, 2020.
[37] G. Qu and A. Wierman. Finite-time analysis of asynchronous stochastic approximation and g-learning. In Conference on Learning Theory, pages 3185-3205. PMLR, 2020.
[38] G. Qu, A. Wierman, and N. Li. Scalable reinforcement learning of localized policies for multi-agent networked systems. In Learning for Dynamics and Control, pages 256-266. PMLR, 2020.
[39] L. G. Roberts. Aloha packet system with and without slots and capture. ACM SIGCOMM Computer Communication Review, 5(2):28 42, 1975.
[40] N. A. Ruhi, C. Thrampoulidis, and B. Hassibi. Improved bounds on the epidemic threshold of exact sis models complex networks. In 2016 IEEE 55th Conference on Decision and Control (CDC), pages 3560-3565. IEEE, 2016.
[41] D. Shah and Q Xie. Q-learning with nearest neighbors. In Advances in Neural Information Processing Systems, pages 31 11-111,,, 2018.
[42] D. Silver, A. Huang, J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, Schritwieser,, I. Antonoglou, V. Panneershelvam, M. Lanetot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):444, 2016.
[43] S. P. Singh, T. Jaakkola, and M. I. Jordan. Reinforcement learning with soft state aggregation.
In Advances in neural information processing systems, pages 361-368, 1995.
[44] R. Srikant and L. Ying. Finite-timg timte-timeeee error bounds for linear stochastic approximation andtd learning. pages 2803-2830, 2019.
[45] J. Subramanian and A. Mahajan. Reinforcement learning in stationary mean-field games. In Proceedings of the 18th International Conference on Autonomous Agents and MulriAgent Systems, pages 251- 2019.
12

---

[46] P. Sunehag, G. Lever, A. Gruslys, W. M. Czarnecki, V. F. Zambaldi, M. Jaderberg, M. Lanctot, N. Sonnerat, Z. Leibo, K. Tuyls, et al. Value-decompositio networks for cooperative multi-agent learning based on team reward. In AAMAS, pages 2085-2087, 2018.
[47] R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour. Policy gradient methods for reinforce- ment learning with function approximation. In Proceedings of the 12th International Conference on Neural Information Processing Systems, NIPS 99, page 1057-1063, Cambridge, MA, USA, 1999. MIT Press.
[48] J. N. Tsitsiklis. Asynchronous stochastic approximation and Q-learning Machine learning, 16(3):185-222, 1994.
[49] N. Tsitsiklis and B. Van Roy. An analysis of temporal-difference learning with function approximation. IEEE Transactions on Automatic Control, 42(5):674-690) 1997.
[50] J. N. Tsitsiklis and B. Van Roy. Analysis of lerforal-differrence learning with function approximation. In Advances neural information processing systems, pages 1075-1081, 1997.
[51] W. Vogels, R. van Renesse, and K. Birman. The power of epidemics: Robust communication for large-scale distributed systems. SIGCOMM Comput. Commun. Rev., 33(1):1311135, Jan. 2003.
[52] M. J. Wainwright. Stochastic approximation with cone-contractive operators: Sharp fnffly- bounds for Q-learning. arXiv preprini arXiv:1905.06266 2019.
[53] S. Wang, V. Venkateswaran, and X. Zhang. Fundamental analysis of full-duplex gains in wireless networks. IEEE/ACM Transactions on Networking, 25(3):1401-1416 2017.
[54] Y. Wu, W. Zhang, P. Xu, and Q. Gu. A finite time analysis of two time-scale actor critic methods, 2020.
[55] T. Xu, S. Zou, and Y. Liang. Two time-scale off-policy td learning: Non-asymptotic analysis over markovian samples. In Advances in Neural Information Processing Systems 32, pages 0664-10644, Curran Associates, Inc., 2019.
[56] Y. Yang, R. Luo, M. Li, M. Zhou, W. Zhang, and J. Wang. Mean field multi-agent reinforcement learning. In International Conference on Machine Learning, pages 5571-5580. PMLR, 2018.
[57] K. Zhang, Z. Yang, and T. Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. arXiv preprint arXiv: 2019.
[58] K. Zhang, Z. Yang. H. Liu, T. Zhang, and T. Başar. Fully decentralized multi-agent reinforcement learning with networked agents. arXiv preprint arXiv:1802.08757, 2018.
[59] R. Zhang and M. Pavone. Control of robotic mobilit--on-eemand systems: a queueing- theoretical perspective. The International Journal of Roboties Research, 35(1-3):186-203 2016.
[60] A. Zocca. Temporal starvation in multi-channel csma networks: an analytical framework. Queueing Systems, 9133-4):241-233, 2019.
13


Reviews:
[{"review_id": "yqF0px6RPWy", "reviewer": "Reviewer_fBbm", "summary": "In this paper, the authors propose a scalable actor-critic framework for a class of multi-agent reinforcement learning (MARL) problems with a stochastic and non-local network of agents. The authors provide a finite-time error bound for the algorithm and show the dependency of the convergence rate on the speed of information spread in the network.", "questions": "", "limitations": "", "rating": 7, "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": "Pros:\n\nMARL with network structure is an important and challenging problem. Stochastic and nonlocal networks are even harder problems to tackle under the MARL framework. The theoretical contributions of this paper are solid and the techniques used are different from the work with deterministic networks [a].\t\t\t\t\n\n[a] G. Qu, Y. Lin, A. Wierman, and N. Li. Scalable multi-agent reinforcement learning for networked systems with average reward. Advances in Neural Information Processing Systems, 33, 2020. \n\nComments:\n\n(1) Is it possible to include a neural-network-type-of functional approximation (see [b] and [c])? This will make the framework more general and applicable to broader problems.\n[b] Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence.arXiv preprint arXiv:1909.01150, 2019.\n[c] Qi Cai, Zhuoran Yang, Jason D Lee, and Zhaoran Wang. Neural temporal-difference learning converges to global optima.Advances in Neural Information Processing Systems, 32, 2019.\n\n\n(2) I understand the importance of the preliminary analysis in Section 2 (for stochastic approximation) and Section 3 (for state aggregation). However, the main framework of networked MARL is not introduced until page 5. The authors may consider restructuring the materials a bit.\n\n\n=============After authors' response=============\nThanks for the response. I read the comments from other reviewers and the authors' responses to all reviewers. RL with stochastic networked systems is a hard problem and I think this paper has a solid contribution to the theoretical front of MARL. My only concern was the organization of the original submission and the authors agreed to rearrange the materials, which I believe is quite achievable for the camera-ready version.\n\nTherefore I will maintain my original score of 7.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "SXJWV6ct1Gu", "reviewer": "Reviewer_savS", "summary": "The paper addresses a class of MARL problems where a stochastic network of agents interacts cooperatively. The give a scalable actor-critic algorithm with finite-time convergence guarantees. The guarantees are obtained via a general stochastic approximation scheme that incorporates state aggregation.", "questions": "", "limitations": "", "rating": 7, "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": "The paper is well written and overall I think it is well organized, though one could argue that Section 4 should be presented a bit earlier, since it gives much of the setting for the paper. However, I don't feel strongly either way, and I am fine with starting from the abstract/general techniques in Section 2. If the paper gets accepted, I recommend fleshing out the description of the algorithm if the conference allows additional space for the final version. \n\nI think the authors do a good job at motivating the new setting. I very much appreciated the results in Section 4, I think they are articulated very clearly and at the right pace. The SA scheme given in Section 2 seems fairly general, though I should note that I am not an expert on this specific sub-area, so it's hard for me to evaluate whether all relevant literature has been appropriately cited and how much incremental the results are. \n\nAll in all, I found the conceptual setup convincing, the paper well written and the results of interest, at least theoretically. To me, the biggest weakness of the paper is its lack of experimental evaluation, which seems standard and expected at this venue. In particular, I think that the paper would be significantly stronger if the authors could also show positive experimental results, possibly comparing to the related work by Qu et al [38]---the latter provides experimental data in their Section 4. However, I think the paper brings enough to the table that I am happy to suggest acceptance nonetheless. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "IFWhCkD4nM1", "reviewer": "Reviewer_QTUD", "summary": "This paper first study the finite time analysis of linear SA with Markov noise, then apply the result to study TD with state aggregation. This paper further study the convegence of MARL based on exp-decay assumption.\n\nThe result is not strong and the author did not make sufficient comparison with the state-of-the-art. Specifically, the rate of linear SA/TD is not compared with the state-of-the-art in terms of conditional number dependence. The rate of AC algorithm seems to be very slow but the author did not make justification for that.", "questions": "", "limitations": "", "rating": 6, "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": "(1) The linear SA with “aggregated entries\" is very similar to TD with linear function approximation setting, which has be extensitvely studied before. The author did not make it clear the technical novelity compare with previous proof.\n\n(2) In (4), the author implicitly assume that $\\Phi^\\top D \\Phi$ is invertable. This assumption is fine for linear TD with independent features, but seems to be strong in the setting considered in this paper. The author should at least provide some justifications here.\n\n(3) It is not clear whether the author obtain a tighter bound for TD learning compare with the state-of-art [1].\n\n(4) Although it is a theorecial paper, empirical verification is also needed becasue this paper proposes a new algorithm here.\n\n\n\n[1] Kotsalis, G., Lan, G., & Li, T. (2020). Simple and optimal methods for stochastic variational inequalities, II: Markovian noise and policy evaluation in reinforcement learning. arXiv preprint arXiv:2011.08434.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper does not have potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "4h"}, "extra_text": {}}, {"review_id": "0w0jClf_lvC", "reviewer": "Reviewer_pJBQ", "summary": "The paper proposes a Scalable Actor-Critic algorithm for a stochastic network of agents. First of all, the authors introduce a new finite-time analysis of stochastic approximation. Then they show how stochastic approximation can be used for state aggregation. Finally they proposed the main algorithms and the theoretical results.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "The paper takes into account the problem of learning the optimal policies for stochastic network agents. \nThe problem is interesting, and the authors show by examples that real-world problems can be cast into this framework. I appreciated the effort of the authors to motivate the considered setting.\n\nHowever, I have found the paper difficult to follow and hard to read. I think that the main problem is due to the space spent for the stochastic approximation part instead then the main objective of the paper, i.e., the algorithm for stochastic network agent. In fact, until page 6, the network setting is still not presented, and so the reader does not understand what the goal of the paper is. Moreover, the main algorithm is presented only on page 8 and this leads to having only one page to discuss it. I would like to strongly suggest removing the part on state aggregation to give more space to the main part of the paper.\n\nGoing into details, the main difference between the setting proposed in this paper and the one of Du et al. is that the transitions and the rewards do not depend on static links between the agent, but that the links are sampled by a distribution $D$. An interesting aspect that is not enough discussed in the paper is: what happens to the proposed algorithm if it is in the setting considered by Du et al? Does it achieve better theoretical performance?\n\nI have found particularly nice the fact that the $\\mu$ decay property enjoys small-world phenomena. \n\nI think that this paper needs an experimental evaluation to compare the proposed approach with the one of Du et al. when it is in the same setting of Du et al. (since the considered setting is a generalization of the one of Du et al.). I will suggest following the same line of experiments as in Du et al. and constructing similar scenarios also for the generalized setting considered in this paper.\n\nI will also suggest adding a conclusive section to underline the main results of this paper and to highlight the differences with the state-of-the-art works.\n\n\nPost author response:\nI would like to thank the authors for their detailed answers. I accordingly increase my score (5 --> 6). I am confident that the authors will follow my suggestion to move the experimental evaluation to the main paper and to add a conclusive section.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In my opinion, this paper has not potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: While the initial reviews were contrasting, the rebuttals helped the reviewers to appreciate better the work. The major issue raised by the Reviewers concerns the organization of the work. All the Reviewers feel that the paper should be re-organized as the authors discuss in their rebuttals. I invite the authors to do that in the camera ready. A further, but secondary, issue concerns the lack of empirical results. My opinion is that this are not strictly necessary as the paper is mainly theoretical. However, having them in the paper would make it stronger. So, I invite the authors to add some empirical results in the final version of the paper.

Decision: Accept (Poster)