Multi-Agent Reinforcement Learning in Stochastic Networked Systems
Year: 2022

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.

heading: 1 Introduction
text: Multi-Agent Reinforcement Learning (MARL) has achieved impressive performance in a wide array of applications including multi-player game play [42, 31], multi-robot systems [13], and autonomous driving [25]. In comparison to single-agent reinforcement learning (RL), MARL poses many challenges, chief of which is scalability [57]. Even if each agent’s local state/action spaces are 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.
A promising approach for addressing the scalability challenge that has received attention in recent years is to exploit application-specific structures, e.g., [18, 35, 38]. A particularly important example of such a structure is a networked structure, e.g., applications in multi-agent networked systems such as social networks [7, 27], communication networks [60, 51], queueing networks [34], and smart transportation networks [59]. In these networked systems, it is often possible to exploit static, local dependency structures [16, 17, 1, 32], e.g., the fact that agents only interact with a fixed set of neighboring agents throughout the game. This sort of dependency structure often leads to scalable, distributed algorithms for optimization and control [16, 1, 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 the 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 (NeurIPS 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 to 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, a 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 [30], social networks [7, 27], 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., [35, 38]. 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 on 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 are 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 a 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 a µ-decay property (Definition 2.1). This property generalizes the exponential decay property underlying recent results such as [35, 16], which does not apply to stochastic 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 to interact globally, the problem becomes a single-agent tabular Q-learning problem with an exponentially large state space, which is known to be intractable since the sample complexity is polynomial in the size of the state/action space [12, 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 3.1). 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, we show that it yields finite-time bounds on Temporal Difference (TD)/Q learning with state aggregation (Theorem 3.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 TDlearning 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 to 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 difference is that we allow the dependency structure among agents to be non-local and stochastic, while [38] requires the dependency structure to 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 3.1 and 3.2), and then establish its connection with the algorithm (Section 2.3). Second, we need a more general decay property (Definition 2.1) than the exponential one used in [38]. Defining and establishing this general decay property for the non-local and stochastic setting is highly non-trivial (Section 2.1).
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 a common global state with other agents. The objective is to maximize a global reward by working cooperatively. Notable examples of this approach include [6, 10] and the references therein. In contrast, we study a 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 [8, 29], where each agent employs a 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, 19] 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 local-interaction model, where there is an underlying graph and each agent depends on 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, 15], 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 -hop neighborhood of each agent.
More broadly, this paper contributes to a growing literature that uses exponential decay to derive scalable algorithms for learning in networked systems. The specific form of exponential decay that we generalize is related to the idea of “correlation decay” studied in [16, 17], 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 is [38], which shows an exponential decay property in a restricted networked MARL model with purely local dependencies. In contrast, we show a more general µ-decay property holds for a general form of stochastic, non-local dependencies.
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, 11, 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 a single trajectory. Beyond [37], there are many other works that use SA schemes to study TD learning and Q-learning, e.g. [44, 52, 20]. The finite-time error bound for TD learning with state aggregation in our work is most related to the asymptotic convergence limit given in [49] and the application of SA scheme to asynchronous Q-learning in [37]. Beyond these papers, other related work in the broader area of RL with state aggregation includes [26, 23, 22, 9, 43]. 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 error bound in the infinity norm for both TD learning with state aggregation and Q-learning with state aggregation.

heading: 2 Networked MARL
text: We consider a network of agents that are associated with an underlying undirected graph G = (N , E), where N = {1, 2, · · · , n} denotes the set of agents and E ✓ N ⇥ N denotes the set of edges. The distance dG(i, j) between two agents i and j 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 si 2 Si and local action ai 2 Ai where Si and Ai are finite sets. The global state/action is defined as the combination of all local states/actions, i.e., s = (s1, · · · , sn) 2 S := S1 ⇥ · · · ⇥ Sn, and a = (a1, · · · , an) 2 A := A1 ⇥ · · ·⇥An. We use Ni to denote the -hop neighborhood of agent i on G, i.e., N
i := {j 2 N | dG(i, j)  }. Let f() := supi |Ni |. For a subset M ✓ N , we use sM/aM
to denote the tuple formed by the states/actions of agents in M .
Before we define the transitions and rewards, we first define the notion of active link sets, which are directed graphs on the agents N and they characterize the interaction structure among the agents. More specifically, an active link set is a set of directed edges that contains all self-loops, i.e., a subset of N ⇥N and a super set of {(i, i) | i 2 N}. Generally speaking, (j, i) 2 L means agent j can affect agent i in the active link set L. Given an active link set L, we also use Ni(L) := {j 2 N | (j, i) 2 L} to denote the set of all agents (include itself) who can affect agent i in the active link set L. In this paper, we consider a pair of active link sets (Ls
t , Lr t ) that is independently drawn from some joint
distribution D at each time step t,1 where the distribution D will be defined using the underlying graph G later in Section 2.1. The role of Ls
t /Lr t is that they define the dependence structure of state
transition/reward 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 Ls t , the next individual state si(t + 1) is independently generated and only depends on the state/action of the agents in Ni(Lst ). In other words, we have,
P (s(t+ 1)|s(t), a(t), Ls t ) =
Y i2N Pi(si(t+ 1)|sNi(Lst )(t), aNi(Lst )(t), L s t ). (1)
Rewards. Each agent is associated with a local reward function ri. At time t, it is a function of Lrt and the state/action of agents in Ni(Lrt ): ri(Lrt , sNi(Lrt )(t), aNi(Lrt )(t)). The global reward r(t) is defined to be the summation of the local rewards ri(t).
Policy. Each agent follows a localized policy that depends on its -hop neighborhood, where 0 is a fixed integer. Specifically, at time step t, given the global state s(t), agent i adopts a local policy ⇣i parameterized by ✓i to decide the distribution of ai(t) based on the the states of agents in N i .
Our objective is for all the agents to cooperatively maximize the discounted global reward, i.e., J(✓) = Es⇠⇡0 P1 t=0 tr(s(t), a(t)) | s(0) = s , where ⇡0 is a given distribution on the initial
global state, and we recall r(s(t), a(t)) is the global stage reward defined as the sum of all local rewards at 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.i.d. 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 a few key concepts in RL which will be useful in the rest of the section. We use ⇡✓
t to denote the distribution of s(t) under policy ✓ given that
s(0) ⇠ ⇡0. A well-known result [47] is that the gradient of the objective rJ(✓) can be computed by 11 Es⇠⇡✓,a⇠⇣✓(·|s)Q ✓(s, a)r log ⇣✓(a | s), where distribution ⇡✓(s) = (1 ) P1 t=0 t⇡✓ t (s) is the discounted state visitation distribution. Evaluating the Q-function Q✓(s, a) plays a key role in approximating rJ(✓). The local Q-function for agent i is the discounted local reward, i.e.
Q✓ i (s, a) = E⇣✓ P1 t=0 tri(t) | s(0) = s, a(0) = a , where we use ri(t) to denote the local reward
of agent i at time step t. Using local Q-functions, we can decompose the global Q-function as Q✓(s, a) = 1
n
P n
i=1 Q ✓ i (s, a), which allows each node to evaluate its local Q-function separately.
A 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.1, we study structural properties of the Q-functions resulting from the dependence structure in the transition (1), which enables us to design a scalable RL algorithm in Section 2.2.

heading: 2.1 µ-decay Property
text: 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 is the identification of a novel structural
1Here, correlations between Lst and Lrt 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 i. This property is 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 [38, 36], which is exploited to design a scalable RL algorithm. However, in stochastic network settings it is too much to hope for exponential decay in general [14], and so we introduce the more general notion of µ-decay here, where µ is a function that converges to 0 as  tends to infinity. The case of exponential decay that has been studied previously corresponds to µ() = /(1 ). The formal definition of µ-decay is given below, where for simplicity, we use i L ! j to denote (i, j) 2 L and denote N i := N \Ni . Definition 2.1. For a function µ : N ! R+ that satisfies lim!+1 µ() = 0, the µ-decay property holds if for any policy ✓ and any i 2 N , the local Q function Q✓
i satisfies Q✓ i (s, a) Q✓ i (s0, a0)  µ() for any (s, a), (s0, a0) that are identical within N
i , i.e. sNi = s 0 N  i , aNi = a 0 N  i .
Intuitively, if the µ-decay property holds and µ() decays quickly as  increases, we can approximately decompose the global Q function as Q✓(s, a) = 1
n
P n
i=1 Q ✓ i (s, a) ⇡ 1 n
P n
i=1 Q̂ ✓ i (sNi , aNi ),
where Q̂i only depends on the states and actions within the -hop neighborhood of agent i. Before our work, [46] empirically showed that such a value decomposition allows efficient training of MARL. Under the assumption that such decomposition exists, [46] 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.1 which shows the relationship between the random active link sets and the µ-decay property. The proof of Theorem 2.1 is deferred to Appendix B.1. Theorem 2.1. Define La as the static active link set that contains all pairs (i, j) whose graph distance on G is less than or equal to , which is the dependency of local policy. Let random variable Xi() denote the smallest t 2 N such that there exists a chain of agents
ja0 L s 0 ! js1 L a ! ja1 L s 1 ! · · · L s t 1 ! jst L a ! jat ,
that satisfies ja0 2 N i and jat L r t ! i. The µ-decay property holds for µ() = 11 E
⇥ Xi() ⇤ .
To make the µ-decay result more concrete, we provide several scenarios that yield different upper bounds on the term E ⇥ Xi() ⇤ . In the first scenario, we study the case where long range links do not exist in Corollary 2.2. In this case, we obtain an exponential decay property that generalizes the result in [38]. A proof is in Appendix B.2. Corollary 2.2 (Exponential Decay). Consider a distribution D of active link sets that satisfies
P(Ls,Lr)⇠D{(i, j) 2 Ls} = 0, for all i, j 2 N s.t. dG(i, j) ↵1, P(Ls,Lr)⇠D{(i, j) 2 Lr} = 0, for all i, j 2 N s.t. dG(i, j) ↵2.
Then, E ⇥ Xi() ⇤  C⇢, where ⇢ = 1/(↵1+ ), C = ↵2/(↵1+ ).
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 µ() = O(⇢/ log )) for some ⇢ 2 (0, 1). A proof can be found in Appendix B.3. Theorem 2.3 (Near-Exponential Decay). Suppose the distribution D of active link sets satisfies
P(Ls,Lr)⇠D{(i, j) 2 Ls [ Lr}  c dG(i,j), for all i, j 2 N ,
where c 1, 1 > > 0 are constants. If the largest size of the  neighborhood in the underlying graph G can be bounded by a polynomial of , i.e., there exists some constants c0 1, n0 2 N such that |{j 2 N | dG(i, j) = }|  c0(+ 1)n0 holds for all i, then E ⇥ Xi( 1) ⇤  C⇢/(1+ln(+1)) for some positive constant C and decay rate ⇢ < 1. 2
It is interesting to compare the result above with models of the so-called “small world phenomena" in social networks, e.g., [14]. In these models, a link (i, j) occurs with probability 1/poly(dG(i, j)),
2The explicit expression of C and ⇢ can be found in Appendix B.3.
Algorithm 1 Scalable Actor Critic 1: for m = 0, 1, 2, · · · do 2: Sample initial global state s(0) ⇠ ⇡0. 3: Each node i takes action ai(0) ⇠ ⇣✓i(m)i (· | sN i (0)) to obtain the global state s(1). 4: Each node i records sNi (0), aNi (0), ri(0) and initialize Q̂ 0 i
to be all zero vector. 5: for t = 1, · · · , T do 6: Each node i takes action ai(t) ⇠ ⇣✓i(m)i (· | sN i (t)) to obtain the global state s(t+ 1). 7: Each node i update the local estimation Q̂i with step size ↵t 1 = Ht 1+t0 ,
Q̂ti sNi (t 1), aNi (t 1) =
(1 ↵t 1)Q̂t 1i sNi (t 1), aNi (t 1) + ↵t 1
⇣ ri(t) + Q̂ t 1 i sNi (t), aNi (t) ⌘ ,
Q̂ti sNi , aNi = Q̂t 1i sNi , aNi for sNi , aNi 6= sNi (t 1), aNi (t 1) .
8: Each node i approximate r✓iJ(✓) by ĝi(m) = P T
t=0 t 1 n P j2Ni Q̂Tj sNj (t), aNj (t) r✓i log ⇣ ✓i(m) i ai(t) | s N i (t) .
9: Each node i conducts gradient ascent by ✓i(m+ 1) = ✓i(m) + ⌘mĝi(m).
as opposed to the exponential dependence in Lemma 2.3. In this case, one can see function µ() is lower bounded by 1/poly(), which leads us to conjecture that µ() is also upper bounded by O(1/poly()). Thus, when information spreads “slowly” it helps a localized algorithm to learn efficiently.

heading: 2.2 A Scalable Actor Critic Algorithm
text: Motivated by the µ-decay property of the Q-functions, we design a novel Scalable Actor Critic algorithm (Algorithm 1) 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 {(sNi , aNi , ri)} to evaluate the local Q-functions under parameter ✓(m). Intuitively, the µ-decay property guarantees that we can achieve good approximation error even when  is not large. The Actor part (from line 8 to line 9) computes the estimated partial derivative using the estimated local Q-functions, and uses the partial derivative to update local parameter ✓i. The step size sequence {⌘m} will be defined in Theorem B.2. Compared with the Scalable Actor Critic algorithm proposed in [38], Algorithm 1 extends the policy dependency structure considered. No longer is the dependency completely local; it now extends to all agents within the -hop neighborhood. Interestingly, the time-varying dependencies do not add complexity into the algorithm (though the analysis is more complex).
Algorithm 1 is highly scalable. Each agent i needs only to query and store the information within its -hop neighborhood during the learning process. The parameter  can be set to balance accuracy and complexity. Specifically, as  increases, the error bound becomes tighter at the expense of increasing computation, communication, and space complexity.

heading: 2.3 Convergence
text: We now present our main result, a finite-time error bound for the Scalable Actor Critic algorithm (Algorithm 1) that holds under general (non-local) dependencies. To that end, we first describe the assumption needed in our result. It focuses on the Markov chain formed by the global state-action pair (s, a) under a fixed policy parameter ✓ and is standard for finite-time convergence results in RL, e.g., [44, 5, 37]. Assumption 2.1. Under any fixed policy ✓, {z(t) := (s(t), a(t))} is an aperiodic and irreducible Markov chain on state space Z := S ⇥ A with a unique stationary distribution d✓ = (d✓
z , z 2 Z), which satisfies d✓ z > 0, 8z 2 Z . Define d✓(z0) = P z2Z:zNi =z 0 d✓(z)
and 0() := infz02ZNi d✓(z0). There exists positive constants K1,K2 such that K2 1 and
8z0 2 Z, 8t 0, supK✓Z P z2K d ✓ z P z2K P(z(t) = z | z(0) = z0)  K1e t/K2 .
We next analyze the Critic part of Algorithm 1 within a given outer loop iteration m. Since the policy is fixed in the inner loop, the global state/action pair (s, a) in the original MDP can be viewed as the state of a Markov chain. We observe that each local estimate Q̂t
i sNi , aNi can be viewed as a form
of state aggregation, where the global state (s, a) is “compressed” to h(s, a) := (sNi , aNi ). Broadly speaking, the technique of state aggregation is one of the easiest-to-deploy schemes for state space compression [21, 43], 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 a 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 µ decay property (Definition 2.1) provides a natural mapping for state aggregation h(s, a) := (sNi , aNi ) which we defined earlier. This mapping h maps the global state/action to the local states/actions in agent i’s -hop neighborhood and the µ-decay property guarantees that if h(s, a) = h(s0, a0), the difference in their Q-functions is upper bounded by µ(), which is vanishing as  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 1). Theorem 2.4. Suppose Assumption 2.1 and µ-decay property (Definition 2.1) hold. Let the step size be ↵t = H
t+t0 with t0 = max(4H, 2K2 log T ), and H 2(1 ) 0() . Define constant Cb :=
4K1(1 + 2K2 + 4H). Then, inside outer loop iteration m, for each i 2 N , with probability at least 1 , we have sup(s,a)2S⇥A Q✓(m)i (s, a) Q̂Ti (sNi , aNi )  Cap T+t0 + C 0 a T+t0 + µ()1 ,
where the constants are given by Ca = 40H
(1 )2
r K2 log T ⇣ log ⇣ 4f()K2T ⌘ + log log T ⌘ and C 0 a =
8 (1 )2 max{ 144K2H log T 0() + Cb, 2K2 log T + t0}.
The proof of Theorem 2.4 can be found in Appendix B.4. The most related result in the literature to Theorem 2.4 is Theorem 7 in [38]. In comparison, Theorem 2.4 applies for more general, potentially non-local, dependencies and, also, improves the constant term by a factor of 1/(1 ). To analyze the Actor part of Algorithm 1, 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, ai, sN i and ✓i, we assume r✓i log ⇣ ✓i i (ai | sN i )  Wi. Then, for any La
t , r✓ log ⇣✓(a | s)  W :=
pP n
i=1 W 2 i . We further assume rJ(✓) is W 0-Lipschitz in ✓.
Intuitively, since the quality of the estimated policy gradient depends on the quality of the estimation of Q-functions, if every agent i has learned a good approximation of its local Q-function in the Critic part of Algorithm 1, 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.5 and defer the detailed bounds and a proof to Appendix B.5. Theorem 2.5. Under Assumption 2.2, to reach an O(✏)-approximate stationary point with probability at least 1 , we need to choose  such that µ() = O W 2(1 )4✏ . The number of required
iterations of the outer loop should satisfy M = ⌦̃ ✏ 2poly(W,W 0, 11 ) and the number of required iterations of the inner loop is T = ⌦̃ ✏ 2poly(W, 1
0() ,K2, 1 1 , log f(), log(1/ )) .
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 -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.

heading: 3 Proof Idea: Stochastic Approximation and State Aggregation
text: 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 µ-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 of TD learning with state aggregation (Section 3.2) and asynchronous Q-learning with state aggregation (Appendix D.4).

heading: 3.1 Stochastic Approximation
text: Consider a finite-state Markov chain whose state space is given by N = {1, 2, · · · , n}. Let {it}1t=0 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, 41, 52]: Let parameter x 2 RN , and F : RN ! RN be a -contraction in the infinity norm. The update rule of the SA scheme is given by
xit(t+ 1) = xit(t) + ↵t(Fit(x(t)) xit(t) + w(t)), xj(t+ 1) = xj(t) for j 6= it, j 2 N ,
(2)
where w(t) is a noise sequence. It is shown in [37] that parameter x(t) converges to the unique fixed point of F at the rate of O 1/ p t .
While general, in many cases, including networked MARL, we do not wish to calculate an entry for every state in N in parameter x, but instead, wish to calculate “aggregated entries.” Specifically, at each time step, after it is generated, we use a surjection h to decide which dimension of parameter x should be updated. This technique, referred to as state aggregation, is one of the easiest-to-deploy schemes for state space compression in the RL literature [21, 43]. In the generalized SA scheme, our objective is to specify the convergence point as well as obtain a finite-time error bound.
Formally, to define the generalization of (2), let N = {1, · · · , n} be the state space of {it} and M = {1, · · · ,m}, (m  n) be the abstract state space. The surjection h : N ! M is used to convert every state in N to its abstraction in M. Given parameter x 2 RM and function F : RN ! RN , we consider the generalized SA scheme that updates x(t) 2 RM starting from x(0) = 0,
xh(it)(t+ 1) = xh(it)(t) + ↵t Fit( x(t)) xh(it)(t) + w(t) ,
xj(t+ 1) = xj(t) for j 6= h(it), j 2 M, (3)
where the feature matrix 2 RN⇥M is defined as
ij = ⇢ 1 if h(i) = j 0 otherwise , 8i 2 N , j 2 M. (4)
In order to state our main result characterizing the convergence of (3), we must first state a few definitions and assumptions. To begin, we define the weighted infinity norm as in [37], except that we extend its definition so as to define the contraction of function F . The reason we use the weighted 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, 2]. Definition 3.1 (Weighted Infinity Norm). Fix a positive vector v 2 RM. For x 2 RM, we define kxk
v := sup i2M |xi| vi . For x 2 RN , we define kxk v := sup i2N |xi| vh(i) .
Next, we state our assumption on the mixing rate of the Markov chain {it}, 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). {it} is an aperiodic and irreducible Markov chain on state space N with stationary distribution d = (d1, d2, · · · , dn). Let d0 j = P i2h 1(j) di and 0 = infj2M d0j . There exists positive constants K1,K2 which satisfy that supS✓N P i2S di P i2S P(it = i | i0 = j)  K1 exp( t/K2), 8j 2 N , 8t 0 and K2 1.
Our next assumption ensures contraction of F . It is also standard, e.g., [48, 52, 37], and ensures that F has a unique fixed point y⇤. Assumption 3.2 (Contraction). Operator F is a contraction in k·k
v , i.e., for any x, y 2 RN , we
have kF (x) F (y)k v  kx yk v . Further, there exists some constant C > 0 such that for any x 2 RN , we have kF (x)k v  kxk v + C.
In Assumption 3.2, notice that the first sentence directly implies the second with C = (1 + )ky⇤k v , where y⇤ 2 RN 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 it. Instead, we show that the convergence is to the unique x⇤ that solves
⇧F ( x⇤) = x⇤, where ⇧ := >D
1 >D. (5)
Here D = diag(d1, d2, · · · , dn) denotes the steady-state probabilities for the process {it}. Note that x⇤ is well-defined because the operator ⇧F ( ·), which defines a mapping from RM to RM, is also a contraction in k·k
v . We state and prove this as Proposition C.1 in Appendix C.1.
Our last assumption is on the noise sequence w(t). It is also standard, e.g., [41, 37]. Assumption 3.3 (Martingale Difference Sequence). wt is Ft+1 measurable and satisfies Ew(t) | Ft = 0. Further, |w(t)|  w̄ almost surely for constant w̄.
We are now ready to state our finite-time convergence result for stochastic approximation. Theorem 3.1. Suppose Assumptions 3.1, 3.2, 3.3 hold. Further, assume there exists constant x̄ kx⇤k
v such that 8t, kx(t)k v  x̄ almost surely.3 Let the step size be ↵t = Ht+t0 with t0 =
max(4H, 2K2 log T ), and H 2 0(1 ) . Let x ⇤ be the unique solution of equation ⇧F ( x⇤) = x⇤, and define constants C1 := 2x̄+C+ w̄
v , C2 := 4x̄+2C+
w̄ v , C3 := 2K1(2x̄+C)(1+2K2+4H).
Then, with probability at least 1 ,
kx(T ) x⇤k v  Cap
T + t0 + C0a T + t0 = Õ ✓ 1p T ◆ ,
where the constants are given by Ca = 4HC2 1 q K2 log T log 4mK2T + log log T and C 0 a = 4max{ 48K2C1H log T+ 0 C3
(1 ) 0 , 2x̄(2K2 log T+t0) 1 }.
A proof of Theorem 3.1 can be found in Appendix C.2. Compared with Theorem 4 in [37], Theorem 3.1 holds for a more general SA scheme where state aggregation is used to reduce the dimension of the parameter x. The proof technique used in [37] does not apply to our setting because our stationary point x⇤ has a more complex form (4). 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 it condition on it ⌧ (see Appendix C.2 for details). Because of this generality, Theorem 3.1 requires a stronger but standard assumption on the mixing rate of the Markov chain {it}.

heading: 3.2 State Aggregation
text: To illustrate the impact of our analysis of SA (Theorem 3.1) beyond the network setting, we study a simpler application to the cases of TD-learning 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, 9, 43]. Further, the result is extremely useful in the analysis in networked MARL that follows since the µ-decay property we introduce (Definition 2.1) 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 [43, 49], given the sequence of states visited by the Markov chain is {it}, the update rule of TD(0) is given by
✓h(it)(t+ 1) = ✓h(it)(t) + ↵t rt + ✓h(it+1)(t) ✓h(it)(t) ,
✓j(t+ 1) = ✓j(t) for j 6= h(it), j 2 M, (6)
where h : N ! M is a surjection that maps each state in N to an abstract state in M and rt is the reward at time step t such that E[rt] = r(it, it+1). Taking F as the Bellman Policy Operator, i.e., the i’th dimension of function F is given by
Fi(V ) = Ei0⇠P(·|i)[r(i, i0) + Vi0 ], 8i 2 N , V 2 RN . The value function (vector) V ⇤ is defined as V ⇤
i = E[ P1 t=0
tr(it, it+1) | i0 = i], i 2 N [49]. By defining the feature matrix as (4) and the noise sequence as
w(t) = rt + ✓h(it+1)(t) Ei0⇠P(·|it)[r(it, i0) + ✓h(i0)(t)], we can rewrite the update rule of TD(0) in (6) in the form of an SA scheme (3). Therefore, we can apply Theorem 3.1 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.
3The assumption on x̄ follows from Assumptions 3.2 and 3.3. See Proposition C.2 in Appendix C.3.
Theorem 3.2. Let Assumption 3.1 hold for the Markov chain {it} and let the stage reward rt be upper bounded by r̄ almost surely. Assume that if h(i) = h(i0) for i, i0 2 N , we have |V ⇤
i V ⇤ i0 |  ⇣ for a constant ⇣ . Consider TD(0) with the step size ↵t = H
t+t0 , where t0 = max(4H, 2K2 log T ) and
H 2 0(1 ) . Define constant C4 := 4K1(1 + 2K2 + 4H). Then, with probability at least 1 ,
k · ✓(T ) V ⇤k1  Cap T + t0
+ C0a
T + t0 + ⇣ 1 ,
where the constants are given by Ca = 40Hr̄(1 )2
q K2 log T log 4mK2T + log log T and C0a =
8r̄ (1 )2 max{ 144K2H log T 0 + C4, 2K2 log T + t0}.
The most related prior results to Theorem 3.2 are [44, 4]. In contrast to these, Theorem 3.2 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 of Q-learning with state aggregation (see Appendix D.4), where we obtain the first finite-time error bound. Moreover, unlike [4], our TD-learning algorithm does not require a projection step.

heading: 4 Concluding Remarks
text: In this paper, we propose and analyze the Scalable Actor Critic Algorithm that provably learns a near-optimal local policy in a setting where every agent is allowed to interact with a random subset of agents. The µ-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 time-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̂i grows exponentially with respect to f(), which denotes the size of the largest -hop neighborhood. Thus, memory problems may still arise if f grows quickly as  increases. Therefore, an interesting open problem is whether we can apply additional function approximations on truncated state/action pair (sNi , aNi ), and obtain similar finite-time convergence guarantees as Scalable Actor Critic.

Review summaries:
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.

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

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.