3DPG: Distributed Deep Deterministic Policy Gradient Algorithms for Networked Multi-Agent Systems

We present Distributed Deep Deterministic Policy Gradient (3DPG), a multi-agent actor-critic (MAAC) algorithm for Markov games. Unlike previous MAAC algorithms, 3DPG is fully distributed during both training and deployment. 3DPG agents calculate local policy gradients based on the most recently available local data (states, actions) and local policies of other agents. During training, this information is exchanged using a potentially lossy and delaying communication network. The network therefore induces Age of Information (AoI) for data and policies. We prove the asymptotic convergence of 3DPG even in the presence of potentially unbounded Age of Information (AoI). This provides an important step towards practical online and distributed multi-agent learning since 3DPG does not assume information to be available deterministically. We analyze 3DPG in the presence of policy and data transfer under mild practical assumptions. Our analysis shows that 3DPG agents converge to a local Nash equilibrium of Markov games in terms of utility functions expressed as the expected value of the agents local approximate action-value functions (Q-functions). The expectations of the local Q-functions are with respect to limiting distributions over the global state-action space shaped by the agents' accumulated local experiences. Our results also shed light on the policies obtained by general MAAC algorithms. We show through a heuristic argument and numerical experiments that 3DPG improves convergence over previous MAAC algorithms that use old actions instead of old policies during training. Further, we show that 3DPG is robust to AoI; it learns competitive policies even with large AoI and low data availability.

multi-agent learning. 3DPG learns distributed but coordinated policies by using global data during training that has been collected by agents using communication over an available network.
Notably, the agents only use local data to take decisions. In other words, individual actions are not globally coordinated, but the agents joint average behavior is coordinated.
3DPG only requires that the agents can exchange information (local states, actions and policies) in an imperfect manner: it might be lost, or experience significant delay, causing data to have random age once it arrives -this is commonly described by so-called Age of Information (AoI) random variables [6]. We analyze 3DPG under practical sufficient conditions, in particular very weak communication assumptions for the MAS. Our modest communication assumptions even allow for potentially unbounded asymptotic growth of the AoI and make no deterministic requirements regarding data availability.
To guarantee convergence of 3DPG, we address another problem. Despite their popularity and usefulness in many practical scenarios, the conditions under which AC and MAAC algorithms converge are not well studied -we address this gap and present practically verifiable and sufficient conditions for DDPG, 3DPG and MADDPG to converge asymptotically. Our result is based on recent progress in understanding the convergence behavior of Deep Q-Learning [7]. Such convergence guarantees and analyses are in general difficult, even for traditional single-agent DeepRL algorithms. In the single-agent case, RL algorithms with linear function approximations are well studied, but algorithms that use non-linear function approximators like Deep Neural Networks (DNNs) are not well understood. At best, convergence is only characterized under strict assumptions that are difficult to verify in practice, e.g., [8] assumes that the state transition kernel of the Markov decision process is regular; this questions the practical usefulness of such algorithms. The behavior of multi-agent DeepRL algorithms is even more challenging since the various agents' training processes are intertwined. It is thus pertinent, both from a theoretical and from a practical standpoint, to analyze, under practical assumptions, the asymptotic properties of multi-agent DeepRL algorithms.

A. The 3DPG Algorithm
To get a first idea (Section III provides details), let us view 3DPG as a multi-agent version of DDPG [5], the most popular AC DeepRL algorithm. DDPG involves two DNNs, an actor (policy) network and a critic (Q-function) network. The actor network is trained to approximate the optimal policy, and the critic network is trained to approximate an objective function. More specifically, the critic network is trained to minimize a variant of the squared Bellman error, while the actor network is trained to pick actions that maximize the approximation of the optimal Q-function, as found by the critic. Notably, both the critic and actor networks are trained simultaneously.
In 3DPG, each agent only has access to a locally observable state (a part of the global state), can exchange information with other agents in an imperfect manner, and takes actions that affect both its local state and states observable by other agents. To take actions, each agent uses a local actor/policy. To train its local policy, each agent uses a local critic/Q-function approximation.
The local policies are functions of the local agent states, which in turn constitute the global (multi-agent) system state. At every discrete time step, after all agents take actions, they obtain local rewards. Each agent then uses a local copy of DDPG (as explained above) to train a local actor, while simultaneously training a local critic with respect to (w.r.t.) the global decision making problem associated with its local reward structure.
To perform the actor training step, the agents use local policies from other agents transferred via a potentially imperfect communication network that, e.g., causes delays. At each agent, the training step may be viewed as calculating a local policy gradient using the best available approximation of the current global policy. The 3DPG architecture at agent 1 of a D agent system is illustrated in Figure 1. In addition to the old policies of other agents, all local actor and critic training steps use data (states, actions) of other agents transferred via the communication network.
This gives a quasi-centralized view but based on information with potentially large age; this view facilitates online training and execution of 3DPG.
The aforementioned actor training step is in stark contrast to the corresponding one in MAD-DPG from [2]. Here the actor training step is based on past actions of other agents. Since these actions are sampled from old transitions, they sometimes include random actions due to exploration. Theses actions, however, do not represent actual agent behavior and can thus negatively impact the policies found by the algorithm (see Sections III-A and VIII for details).
Using old policies of other agents, as in 3DPG, may initially increase the training variance.
However, we show that for 3DPG the effect of unrepresentative behavior from old policies as well as the effect of potentially random actions does not effect the policies found by 3DPG. For MADDPG, we show that the presence of randomly explored actions can have a negative impact π 2 · ; φ 2 n−τ21(n) Q 1 · , · ; θ 1 n π D · ; φ D n−τD1(n)  To study the convergence of 3DPG, we use recent asymptotic analyses of Deep Q-Learning under practical and mild assumptions [7]. Since DDPG may be as a viewed special case of 3DPG involving a single agent, our analysis can be directly used to understand DDPG.
Paper organization. In Section II, we define the Markov game setting considered in this work. In Section III, we describe the 3DPG Algorithm and the required assumptions to prove its convergence. Sections V and VII present our main convergence analysis. Afterwards, we analyze the difference between the 3DPG and MADDPG algorithm in Section VIII, which we support with numerical experiments section IX. We close with conclusions and future work in Section X.

II. MARKOV GAMES
In multi-agent systems, the global state of the environment is typically the concatenation of the agents' local states. However, the global state is usually unobservable by any agent. The global state transitions to a new state after each agent has taken its local action. After the global state transition, the agents receive local feedback/reward signals. The structure of the local reward signals depend on the nature of interaction between the agents: do they cooperate or compete?
In the following, we always use superscripts i for the agent index in the multi-agent system, and we use subscripts n as discrete time steps. We assume that the multi-agent system under consideration can be modeled as a D-agent Markov game [9], which is formally defined as the where an action a = (a 1 , . . . , a D ) ∈ A denotes the joint action as a concatenation of local actions p is the Markov transition kernel, i.e. p(· | s, a) is the distribution of the successor state of state s after action a is executed. r i is the local scalar reward function associated with agent i. Specifically, r i (s, a) is the local reward that agent i observes when the system is in state s and the global action a is taken.
In many cooperative Markov games, the local reward functions coincide, i.e., r i ≡ r for 1 ≤ i ≤ D. Such models are called factored decentralized MDPs [10].
Consider a D-agent Markov game as defined in above. The D agents interact with the environment at discrete time steps n ∈ N. At every time step n, agent i observes a local state s i n ∈ S i , based upon which it must take a local (continuous) action a i n ∈ A i ⊆ R d i , for which it receives a reward r i n . Suppose that the local behavior of agent i is defined by a local DNN policy π i (s i ; φ i ), parameterized by a vector φ i . Define the associated global policy as π := (π 1 , . . . , π D ). (1) For each local reward function r i , the return starting from time step 1 is defined by R i := ∞ n=1 γ n−1 r i (s n , a n ) with discount factor 0 < γ < 1. Given a global policy π, the associated action-value function Q i of agent i is given by Q i (s, a) := E π [R i | s 1 = s, a 1 = a]. For each local reward function r i , the associated optimal policy is characterized by the optimal action-value function Q i * (s, a), which is defined as a solution to Bellman's equation [11]: The problem is to find local policy parametrizations φ i * for each local policy π i (s i ; φ i ), such that for every agent i: In other words, all local policies should act optimally conditioned on the local policies obtained by all other agents.

III. DISTRIBUTED DEEP DETERMINISTIC POLICY GRADIENT ALGORITHM (3DPG)
In this section, we define the 3DPG algorithm.

A. Multi-Agent Actor-Critic Gradients
Suppose each agent i uses a local DNN approximator Q i (s, a; θ i ) for its local critic; θ i represents the associated vector of network weights. The local critic is trained using the Deep Q-Learning algorithm [12] to find θ i * such that Q i (s, a; θ i * ) ≈ Q i * (s, a) for all state-action pairs (s, a). As mentioned before, each local actor/policy π i (s i ; φ i ) is parameterized by φ i . The goal is to train the local critics and local actors jointly such that (3) holds. This is challenging due to the potential conflicting rewards of the agents.
Consider that at some time step n, the local critic and actor parametrizations are θ i n and φ i n . Further, suppose agent i gets access to a global data tuple from some transition from time m to m + 1 with m n. The availability of at least some global tuples must be ensured by coordinated communication between the agents. This will be discussed further in the following subsections. Now, if agent i had access to the parametrizations of the other agents, then it could calculate a local critic gradient Equation (5) is a sample gradient of the local squared Bellman error of Q i for the observed global tuple t m , which follows from the associated error in Bellmans equation (2). Now, there two possible ways to formulate a "natural" distributed version of the policy gradient in the DDPG algorithm [5]. The first one is the local policy gradient which is used in the MADDPG algorithm of [2]. The second one is the local policy gradient which will be used in our 3DPG algorithm. The MADDPG local policy gradient uses the actions a j =i m from the other agents from the global tuple t i m , while the local policy gradients in 3DPG use the policies φ j =i n from the other agents. In the following, we use ∇ φ i g i for (7) to simplify the notation. Remark 1. The subtle difference between (6) and (7) will be analyzed extensively in Section VIII.
We discuss a heuristic argument based on our asymptotic convergence analysis of MADDPG and 3DPG that shows that a multi-agent actor-critic algorithm based on (7) has a higher probability of obtaining a better policy faster compared to a multi-agent actor-critic algorithm based on (6). This is because (7) takes precisely into account how other agents would behave in certain sampled states. Equation (6), on the other hand, also considers the sampled actions that may arise from randomly explored actions. Our numerical experiment in Section IX supports this theoretical prediction.
Remark 2. The local policy gradient (7) seems to have a more direct motivation from the deterministic policy gradient theorem (DPGT) [13] in comparison to (6). The DDPG alogrithm was inspired by taking samples from the DPGT 1 . Similarly, the gradient (7) can be motivated by inserting the global product policy (1) into the DPGT. Thus Equation (7) is in essence the policy gradient from the DDPG algorithm [5], where the policy is defined in product form (1). 1 Be aware that the sample gradients used in the DDPG algorithm are not true sample gradients from the deterministic policy gradient [14] The idea behind 3DPG is to approximate (5) and (7) using old information from other agents to train Q i and π i locally. To implement this, the agents require: 1) Local access to global data tuples t i m , 2) Local access to the global policy π(s; φ m ), for m n "frequently" (the precise network assumptions are presented in section III-D). Recall that in MADDPG the above information are required for all agents at every time step. These are reasonable assumptions for simulated environments or under the paradigm of centralized training with decentralized execution, but not for online fully distributed learning.

B. Approximate Global Policy induced by local AoI
We now decentralize the implementation of (5) and (7) using communication. Most notably, we use communicated but potentially aged local policies as an approximation for the true global policy φ n .
Suppose that the D-agent Markov game is networked, such that the agents can exchange data by communication. We suggest a communication paradigm where agents cooperatively forward local data to other agents, such that local policies and local data (states and actions) can flow via the network to all other agents. To guarantee this, the agents must use some forwarding protocol [15] to forward old policies φ i n between the agents as well as coordinated communication protocol to ensure that at least some global tuples (4) reach each agent "frequently". The coordinated communication protocol may be some broadcast protocol coupled with a central coordinator, or it could also be a distributed snapshot protocol [16], which, however, would cost more communication resources. For now, we suppose that the agents run suitable protocols of this kind. Specifically, protocols that guarantee that our network assumptions (A1), as to be defined in the next section, are satisfied.
Let us now suppose that each agent runs a local algorithm to train its policy and thereby generates a sequence φ i n of associated policy parametrizations. Equipped with the ability to transfer data via the available network, the agents exchange the local parametrization φ i n as well as local tuples t i n := (s i n , a i n , s i n+1 ) using the communication network that possibly delays or looses data for extended periods of time. Hence, agent i has only access to φ j n−τ ij (n) for every agent j = i at every time step n. Here, φ j n−τ ij (n) denotes the latest available policy parametrization from agent j at agent i at time n and we refer to τ ij (n) as the associated Age of Information (AoI) random variable as a consequence of the potentially uncertain and delaying communication. 2 For every agent i, we can then define a global policy parametrization associated with the aged information at time n by This global policy will serve as an approximation to the true global policy φ n .

C. The 3DPG Algorithm
As discussed in the previous section, we suppose that the D-agent multi-agent system uses an available network to exchange their local policy parametrizations φ i n and their local tuples (s i n , a i n , s i n+1 ). We can now state the 3DPG iteration. Suppose that every agent i maintains a local replay memory R i n . At every time step n, the memory can contain up to N old global transitions t i m . At time step n, agent i samples a random minibatch of M < N transitions from its replay memory. Agent i then updates its actor and critic using step-size sequences α(n) and β(n) as follows: Notice that for a single sample t i m , the gradients used in (9) are the gradients (5) and (7) where the global policy φ n has been replaced by the local approximation of the global policy φ τ i (n) induced by the aged parametrization (8). The resulting training architecture is presented in Figure 1. Pseudocode for the algorithm is presented in Section B. We will now present our assumptions to prove the convergence of (9). We begin with the required network assumptions.

D. Network Assumptions
The communication network needs to ensure two things. First, it needs to ensure that every agent i receives the policy parametrizations φ j n for all j = i "sufficiently" often. Second, it needs to ensure that the available samples in the replay memories R i n are not too old. To capture the age of the samples in the replay memories, define another AoI random variable ∆ i (n) as the age of the oldest sample in the replay memory R i n of agent i at time n ≥ 0.

Definition 1.
A non-negative integer-valued random variable X is said to be stochastically dominated by a random variable X if P (X > m) ≤ P X > m for all m ≥ 0.
(A1) (a) Policy communication assumptions: There exists a non-negative integer-valued random variable τ that stochastically dominates There exists a non-negative integer-valued random variable ∆ that stochastically dominates (A1)(a) and (A2)(b) require that the tail distributions of the AoI variables τ ij (n) and ∆ i (n) decay uniformly, such that at least a dominating random variable with finite mean exists. This ensures that the growth of each AoI variable cannot exceed any fraction of n after some potentially large time step. We prove this in Lemma 2 and show in Lemma 3 that the use of the approximate global policies φ τ i (n) in (9) does not cause gradient errors asymptotically.
Finally, (A2)(b) is used in Lemma 7 to show that the agents experiences converge to a stationary distribution. Here (A2)(b) ensures that the agents receive enough global tuples asymptotically to "track" the Markov game state distribution.
(b) sup n≥0 s n < ∞ a.s. and the action space A is compact.
(A5) The actor policies π i and the critics Q i are fully connected feedforward neural networks with twice continuously differentiable activation functions such as Gaussian Error Linear Units (GELUs).
(A6) The reward functions r i : S × A → R are continuous.
Assumption (A3)(a) is the strongest assumption as it requires almost sure stability of the algorithm. We devote the next subsection to its discussion. The compactness of the action space in (A3)(b) will usually be satisfied in many applications, e.g. in robotics.
In (A2)(b) we require that the critic and actor step-size sequences are chosen such the β(n) α(n) → 1. This is not a traditional assumption for actor-critc algorithms [18]. We will present a proof based on a single-timescale analysis of (9) w.r.t. the timescale of the critic iterations. In practice, we want the critic to converge faster so we would initially choose α(n) larger than β(n). (A2)(b) requires that afterwards the iterations asymptotically take steps of the same size. The more complex analysis using a two-timescale step-size schedule will be presented in an upcoming paper.
In (A5), we require twice continuously differentiability of the activations used by the policy and actor networks. GELUs are well-known examples that satisfy this property [19]. Additionally, GELUs are one of the well-known neural network activation functions with similar high performance across different tasks compared to other well-known activations like ELUs or LeakyReLUs [20].

F. Discussion of Assumption (A3)(a) and Related Work
Ideally, when one is dealing with a specific algorithm, it should be guaranteed or provenrather than assumed up-front -that the algorithm iterations are stable. Assuming stability is, nonetheless, a typical first step towards understanding the convergence behavior of optimization algorithms. Especially in deep RL, stability of algorithms like Deep Q-Learning or DDPG are not well understood. Most notably, there is a significant gap between the assumptions made in theory compared to assumptions verifiable in practice. Lets review some results on MAAC learning.
In [4] the authors use linear function approximation and assume that the MA learning problem can be described by finite state ergodic Markov process. They further assume assume the existence of projection operator with knowledge of a compact set that includes a local minima of the objective. [21] provides very interesting rate of convergence results for AC methods. However, they assume that samples (s n , a n , r n , s n+1 ) are drawn from a known stationary distribution of the state Markov process. We instead show that our AC iterates converge such that the experience of the agents give rise to stationary distributions of the state Markov process. In addition, knowledge of the bias of the policy gradient and the bias of the critic estimates is required in [21], while the critic should again be a linear combination of features. That work also assumes that the policy gradient is Lipschitz continuous, which would require (A3)(a), since most DNNs are only locally Lipschitz.
The assumptions made in the above works will be very hard to verify for most data-driven applications in practice. Even worse, we fear that guaranteeing stability for practical data-driven RL problems may always require assumptions that are not easily verifiable in practice. However, a practitioner may not even be highly interested in stability. Usually, practitioners will design their DNN parameterizations and their hyperparameter configurations using their experience, such that they roughly observe stable behavior. Afterwards, practitioners would like to know what limit they can expect from their algorithm. This is where our work comes into play.
In contrast to the assumptions made in the literature, our assumptions, except (A3)(a), are very week, easily verifiable in practice and represent well how users apply DQN, DDPG and its variants in practice. For this setting, our work answers to where one can expect the 3DPG iterations (9) to converge asymptotically. Specifically, our analysis gives a comprehensive characterization of the found limit using a limiting distributions of the state-action process. These limiting distributions are shown to be stationary distributions of state Markov process and are shaped by the experience of the agents. We now present our convergence result.

IV. MAIN RESULTS
where µ i ∞ is a limiting distribution of a continuous time measure process (defined in Section VII) that captures the experience of agent i sampled from its local experience replay R i n during training. Further, all µ i ∞ are stationary distributions of the state Markov process: Since stochastic gradient descent schemes tend to avoid unstable equlibria [22], [23], [24], we can expect that the aforementioned stationary points are local minima with high probability.
This can be made more precise using an avoidance of traps analysis [25,Ch. 4]. This shows that 3DPG converges to local solution of the objective (3) with high probability. In other words, given their local reward structure the agents converge to an equilibrium where they have locally no desire to change their policies given their local experience and the final policies of the other agents. More precisely, it follows that the agents converge to a local Nash equilibrium w.r.t. to their locally approximated action-value functions.
Abbreviate the final local policies as π i In other words, Π i ∞ (U) is the set of policies in the U neighborhood of π i ∞ (s).
Corollary 1 shows that the local policies converge to a local approximate Nash equilibrium w.r.t. the experience gathered by each agent locally. The experience is again represented by the limiting distributions µ i ∞ . Specifically, the local policies converge to a local Nash equilibrium w.r.t. the local expected action-value functions S Q i (s, · ; θ i ∞ )µ i ∞ (s, A). In game theoretic terms, these are the payoff (or utility) functions w.r.t. which the agents converge to a local Nash equilibrium.
Remark 4. Corollary 1 holds when the local policies π i are linear functions of pretrained nonlinear features. This is common in the literature as e.g. used in the discussed references [4] and [21]. The significance of Corollary 1 is that the agents converge to a local approximate Nash equilibrium without assuming that the samples used in training are from a known stationary distribution of the state Markov process. We instead show that the experience of the agents give rise to stationary distributions of the state Markov process. This is important, as deep RL algorithms are typically employed in complex environments with multiple stationary distributions

V. PRELIMINARIES AND AGE OF INFORMATION ANALYSIS
In the following two sections, we prove Theorem 1. The proof builds on the analysis of single agent deep Q-learning presented in [7]. To simplify the presentation, we will assume from now on that the state space S is compact. All results can be generalized to d-dimensional real spaces under the almost sure boundedness condition in (A3)(b), for which we refer to techniques presented in [7, Section IV.A.2].
At its core, we will now present a convergence proof for the DDPG algorithm [5], using a single timescale analysis. We begin with preliminary reductions and the analysis of the AoI processes τ ij (n).

A. Reduction to mini batches of size 1
First, we make a simplifying reduction. We consider that the agents have ready access to the global tuples (s n , a n , r i (s n , a n ), s n+1 ) during runtime and that merely the local policies φ i n are communicated via the communication network. Further, we merely consider that the agents use the global tuple from time n to update its critic and actor network. We therefore simplify iteration (9) to: In Section VII, we will extend our analysis to the setting presented in Section III.

B. Reduction to zero AoI
As the second step, we define the gradient errors that occur since we use the aged global policies φ τ i (n) instead of the true global policy: Hence, (14) can be written as C. Reduction to marginalized critic gradient As the third step, we rewrite the critic iterations in (16) further by integrating over the the successor state s n+1 in t n given state s n . The resulting new loss gradient is With a slight abuse of notation, we use p(ds | s n , φ n ) instead of p(ds | s n , φ n (s n )) to highlight the dependency of the action a n on the policy φ n and potential additional random noise for exploration.
Define the induced error from using ∇ θ il i instead of ∇ θ i l i as ψ i n := ∇ θ il i − ∇ θ i l i , we can then rewrite (16) as θ i n+1 = θ i n + α(n) ∇ θ il i (θ i n , φ n , s n , a n ) + ψ i n + e θ i n , D. e θ i n , e φ i n and ψ i n vanish asymptotically In summary, we have rewritten (14) using: 1) The errors e θ i n and e φ i n induced by not considering the AoI random variables τ ij (n), 2) The errors ψ i n induced by marginalizing out the successor states s n+1 . We will now show that these errors vanish asymptotically. For this, we first present properties of the loss gradients ∇ φ i g i , ∇ θ i l i and ∇ θ il i .
n , φ n , t n ) and ∇ θ il i (θ i n , φ n , s n , a n ) are continuous and locally Lipschitz continuous in the θ i and φ-coordinate.
(ii) ∇ φ i g(θ i n , φ n , s n , a n ) is locally Lipschitz continuous in every coordinate.
Proof: See Appendix A.
We can now show that the errors e θ i n and e φ i n due to AoI vanish asymptotically. For this we need a technical lemma. Lemma 2. Under (A1)(a) it follows that for every ε ∈ (0, 1) and all agent pairs (i, j), with τ from (A1)(a).
Proof: See Appendix A.
The lemma shows that the AoI processes τ ij (n) do not exceed any fraction of n 1 q 1 asymptotically. More precisely, it now follows from the Borel-Cantelli Lemma that P τ ij (n) > εn The following Lemma shows that the gradient errors vanish asymptotically. follows that for a sample path dependent constant C > 0. We will now show that which thus implies that lim n→∞ e θ i n = 0. By (A2)(b), we assume that β(n) ∈ O(n − 1 q ) with q ≤ q 1 Hence, there are constants c > 0 and N ∈ N, such that Fix ε ∈ (0, 1). Equations (20) and (23) for all n with n ≥ N (ε) and n − εn Taking the lim sup on both sides above yields that The statement follows since the choice of ε was arbitrary. The proof for e φ i n follows analogously.
The next lemma shows that the accumulated errors due to the marginalization of the successor states in (18) is convergent almost surely. It therefore follows that ψ i n vanishes. It now follows from Lemma 3 and Lemma 4 that we can study the convergence of (18) without the additional error terms e θ i n , e φ i n and ψ i n . This is because the error terms will contribute additional asymptotically negligible errors in the following proof of Lemma 5. With a slide abuse of notation we now redefine the critic loss gradients ∇ θ i l i as the marginalized critic loss gradient ∇ θ il i .

VI. CONVERGENCE ANALYSIS
To analyze the asymptotic behavior of (18), we follow the ODE approach from SA [25], i.e.
we construct a continuous-time trajectory with the same limiting behavior as (18). First, we divide the time axis using α(n) as follows: Now define θ i (t n ) := θ i n , n ≥ 0 and φ i (t n ) := φ i n , n ≥ 0.
Let R p i θ and R p i φ be the parameter spaces of the θ i n 's and φ i n 's, respectively. Then define respectively.
To analyze the training process, we formulate a measure process that captures the encountered state-action pairs when using the global policy π(s n ; φ n ). Therefore, define where δ (x,a) denotes the Dirac measure. This defines a process of probability measures on S ×A.
It follows from Lemma 1 that all∇l i and∇g i are continuous in all coordinates and locally Lipschitz in both the θ i -and φ-coordinate.
We can now define the associated continuous time trajectories in C([0, ∞), that capture the training process starting from time t n for n ≥ 0: where µ n (t) := µ(t n + t). The combination of the continuous-time trajectories in (31) results in the aforementioned single trajectory with the same limiting behavior as (18).
Per definition, the trajectories define solutions to the following families of non-autonomous ordinary differential equations (ODEs): By construction, we obtain that the limiting behavior of (18) is captured by the limits of the sequences {θ i ([t n , ∞))} n≥0 and {φ i ([t n , ∞))} n≥0 defined by (28). Further, the sequences defined in (31) can be analyzed as solutions to the ODEs in (32). If (28) and (31) behave asymptotically identical, then the limiting behavior of (18) is thus captured by the solutions to the ODEs in (32). This is formalized by the following important technical Lemma 5. This lemma is the key component to enable a single-timescale analysis of DDPG style actor-critic algorithms along the line of argument presented in [7] for Deep Q-Learning. To prove Lemma 5, we use that the step size sequences are related by β(n) α(n) → 1 from (A2)(b). This is essential since we just constructed the continuous trajectories w.r.t. the timescale induced by α(n). The assumption in essence requires that the critic and actor updates asymptotically run on the same time scale.
The stability of the algorithm and the compactness of the state-action space, i.e. (A3), show that since α(n) is monotonic and β(n) α(n) → 1. Similarly, we can show that To show (34), we now need to show that Using a telescoping series, φ The last step follows from α(m) = t m+1 − t m and using that . Now rewrite the second term in (39): We now evaluate the difference of the terms under the integrals in (40) and (41).
for some sample path dependent constant C < ∞ using the stability from (A3). The last step adds zeros and uses the Lippschitz continuity of∇g i . The combination of (39), (40), (41) and (42) thus gives: The first term in the above expression converges to zero as n → ∞, since n+k−1 m=n α(m) ≤ T by construction and since lim  (43), and for all θ i : where D is the number of agents. We now apply the discrete version of Gronwall inequality [25] to x n . It follows that x n ≤ o(1)e 2LD n+k−1 m=n a(m) . By construction n+k−1 m=n a(m) ≤ T for all n ≥ 0, thus x n → 0, which proves the lemma.
Lemma 5 shows that we can analyze the limits of (18) as the limits of the continuous-time trajectories defined in (28) in conjunction with the measure process (29). By construction, the trajectories θ i n (t) and φ i n (t) are equicontinuous. Moreover, they are point-wise bounded from (A3)(a). It now follows from the Arzela-Ascoli theorem, [26], that the families of trajectories are sequentially compact in C([0, ∞), R p i θ ) and C([0, ∞), R p i φ ), respectively. Further, it can be shown that the space of measurable functions from [0, ∞) to the space of probability measures on S × A is compact metrizable [27]. It now follows that the product space of all trajectories θ i n (t) and φ i n (t) together with the aforementioned space of measurable functions is sequentially compact. Hence, there is a common subsequence such that all considered sequences converge simultaneously, i.e. we obtain (with a slight abuse of notation) that and µ n → µ ∞ in the space of measurable functions. Analogously to [7,Lemma 4], we can show that µ n (t) also converges in distribution to µ ∞ (t) in P(S × A), t almost everywhere.
The following lemma now shows that the limits θ i ∞ , φ i ∞ and µ ∞ are solutions to the limits of the families of non-autonomous ordinary differential equations (32).
Proof: See Appendix A.
We can now study the limit of 3DPG as a solution to the aforementioned non-autonomous ODE's. Specifically, append the ODEs to form a new ODE in the appended parameter space.

VII. EXTENSION TO EXPERIENCE REPLAYS
Experience replay buffers play an important role in stabilization of RL algorithms [12]. The fundamental idea is to learn from past experiences to reduce the bias of an RL algorithm towards the interactions of an agent with its environment. For 3DPG this means that at time n an agent does not use the transition t i n to calculate the loss gradients, but it uses a random minibatch of past transitions t i m from old time steps m ≤ n. As a consequence, the training algorithm is not overtly biased agents interaction with the environment, reducing learning variance, thereby improving stability.
In the previous section, we analyzed 3DPG for centralized training where the global transitions t i n are locally available for every agent i. Additionally, we only used an experience replay of size one. To accommodate the use of experience replays in Section V, the probability measure µ(t) needs to be redefined. In (9), each agent i samples M < N global tuples independently from its (local) random experience replay R i n at every iteration n. The sampling processes of the agents will in general be different. Further, we will experience R i n = R j n , since the global tuples are communicated by the agents in a potentially delaying manner.
We now define a new measure process µ i (t) for each agent. For t ∈ [t n , t n+1 ), define δ (s m(n,j,i) ,a m(n,j,i) ) .
Hence, µ i (t) is the probability measure on S × A that places a mass of 1 /M on each pair (s m(n,j,i) , a m(n,j,i) ) for 1 ≤ j ≤ M , where each m(n, j, i) denotes one of the time indices sampled by agent i at time n from its memory R i n . Notice that in the presence of communication and AoI, each experience replay is a random sequence of sets. If we use the redefined measures in (30) we get for every t = t n that The analysis presented in Section V is also true for then new measure processes, where now every agent has its own measure process. This shows the first part of Theorem 1. It is left to characterize the properties of the limiting measure processes µ i ∞ , which are the limits of the convergent subsequence extracted from µ i n (t) := µ i (t n + t).
Lemma 7. For all t ∈ [0, ∞) and for all agents i In other words, the limiting marginals constitute stationary distributions over the state Markov process.
Proof: Without loss of generality, assume a batch-size M = 1. The cases M > 1 will only require additional bookkeeping. Recall that the samples used in the 3DPG iterations (9) are potentially old and from random time-steps, such that (A1)(b) holds. 3 Fix some agent i. In the following, we will drop the agent index i. Since M = 1, the agent uses a global transition t kn with random time index k n for its 3DPG training step at time n.
Pick f ∈ C b (S), the convergence determining class for distributions on S. We analyze as n → ∞. The error terms (49) consider the deviation between states sampled from µ(t) and the associated expected transition under the policy that uses the sample during training. This is the perspective of an experimenter that observes the Markov game and the 3DPG algorithm during runtime.
for every n ≥ 0 with i∈∅ = 0. Recall that α(n) ∈ O(n − 1 q ) with q ∈ [1, 2), then since at time n a sample from the replay memory can be at most n time steps old. It then follows , which in turn implies that γ(k) ∈ O n − 1 q and thus that γ(m) is square summable.
To analyze (50), we now consider the sequence and the filtration Then ξ n is a Martingale w.r.t F n−1 . Since f is bounded and γ(m) is square summable, the quadratic variation process associated with the Martingale ξ n is convergent. It then follows from the Martingale Convergence Theorem [28] that ξ n converges almost surely.
Recall that we denote by ∆(n) the age of the oldest sample in the replay memory. Lemma 2 now also holds for ∆(n) using (A1)(b), i.e. fix ε ∈ (0, 1) then there is a sample path dependent constant N (ε) ∈ N, such that ∆(n) ≤ εn 1 q 2 for all n ≥ N (ε) with q 2 from (A1)(b). In other words, Since ξ n converges, it follows that for every t > 0 δ(n,t) m=n−εn converges to zero a.s., where δ(n, t) := min{m ≥ n | t m ≥ t n + t}.
Next, spread out and rearrange the aggregated samples in (56). Specifically, use (55) and separate the samples as the following three terms, whose sum converges to zero a.s.: Notably, the rearrangement is mathematically valid since (56) is a finite sum for each n. Since q 2 ≥ q, it follows that the second and third term converge to zero. The proofs use the same line of argument as to show (22) in Lemma 3. We can therefore conclude that converges to zero a.s. Equation (58) now also holds, if we replace φ km by φ m since the resulting error terms when taking the difference between (58) and the version with φ m converges to zero. To see this, note that δ(n,t)−1 m=n α(m) ∈ O(t) by construction. Further, all individual error terms in the aforementioned difference converge to zero using weak convergence by continuity of (s, φ) → p(· | s, φ) and since φ km −φ m → 0 a.s. Finally, α(n) is eventually decreasing, hence δ(n,t) m=n [α(m) − α(m + 1)] f (s km+1 ) → 0 a.s.. In summary, we have thus shown that In this section, we discuss the difference between 3DPG and MADDPG for the centralized training scenario with global information access.

A. The MADDPG policy gradient iteration
An MADDPG agent i updates its policy using the gradient for 1 ≤ m ≤ M sampled transitions, with ∇ φ i g i MADDPG as defined in (6). Please again observe the difference compared to the second iteration in our 3DPG algorithm (9). In MADDPG old actions a j m for all j = i are used from the samples of the experience replay. In contrast the true current policy a j = π φ j n (s j m ) is used in the 3DPG policy gradient iteration (assuming the centralized setting). MADDPG still uses the policies of other agents in the critic iteration. Hence, availability of the policies from other agents is anyway required.
Lets try to understand the subtle difference between 3DPG and MADDPG intuitively.
as the sample policy gradient. The expression averages over sampled actions of the other agents.
These actions will sometimes include random actions due to exploration. 4 This indicates that agents would learn polices that also act well for random behavior of other agents. This seems to be undesirable for cooperative learning. We will now make the above heuristic precise using Theorem 1 and its variant for MADDPG.

B. The MADDPG limit vs. the 3DPG limit
First, we discuss the analog of Theorem 1 for MADDPG Specifically, consider (9) with (7). To analyze MADDPG with experience replays, we use the same measure processes (46) as in the Section VII. However, we need to redefine the average policy gradient in (30) tõ The analysis from Sections V and VII can now be emulated for this gradient with the measure processes µ i (t). Due to the new average policy gradient the conclusion of the convergence theorem are now fundamentally different. MADDPG converges to limits θ i MA and φ i MA , such that Here, µ i MA are the local limiting distribution of the sampled experience at agent i under MAD-DPG. Recall that the 3DPG limit satisfies: In (64), the behavior of the other agents is solely present in the limiting measures µ i MA . When exploration is stopped after some time, then the asymptotic properties of MADDPG and 3DPG are the same. However, when the exploration probability is not decayed to zero asymptotically, the the limiting measures µ i M A are also shaped by random actions. This formalizes the heuristic from the previous subsection: the presence of exploration can deteriorate the policies found by MADDPG agents. The agents would adapt their policies to random actions that are not representative of the other agents. This is clearly an undesirable property. 3DPG fares better in this regard as it does not have this negative property! 3DPG allows a high exploration probability asymptotically without a negative effect on the found policies. Next, we discuss the moving target problem.
Remark 5. In practice, the aforementioned negative property of MADDPG due random actions is exacerbated due to the fact that training is stopped in finite time, possibly in a premature manner. During training the other agents may have initially behaved in a certain way, which was then well represented in the replay memory an agent. During later stages of learning, the other agents may "quickly" converge to a different policy. Since the agent uses outdated samples to calculate local gradients, the policy evolution is significantly biased towards the old behavior of the other agents. This is particularly undesirable in cooperative problems. Again, 3DPG circumvents such scenarios by the using the latest available agent policies. MADDPG can overcome these issues by stopping exploration after some time and by using decaying learning rates.

C. The moving target problem in MARL
Multi-agent RL algorithms are effected by non-stationarity due to the change of other agents behavior from the perspective of one agent (the so called moving target problem). Here, 3DPG is no exception. The authors of [2], discuss that using the local policy gradients ∇ φ i g i MADDPG based on old actions of other agents removes the non-stationarity from the perspective of each agent. We believe that this not wholly true. MADDPG smooths out the non-stationarity, as the behavior of other agents is observed via the sampled actions from the experience replays. But this does not remove the non-stationarity. Intuitively, it takes longer for the behavior of an agent to manifest in the replay memory (in form of samples) compared to directly using the behavior of an agent using its policy as in 3DPG.
Since 3DPG does use the policies of other agents, we expect that 3DPG has more variance due to the changing behavior of other agents. However, since the 3DPG agents use more accurate information from the other agents' policies and are not affected by exploration as described in the previous section, we expect a faster convergence rate compared to MADDPG. Both predictions, are validated in our experiments in the following Section IX. Finally, notice that the moving target problem has no impact on Corollary 1. The 3DPG agents converge to a local Nash equilibrium.

IX. NUMERICAL EXPERIMENTS
For our numerical experiments, we first compare 3DPG and MADDPG in a centralized training setting with global information access. Afterwards, we evaluate 3DPG with communication, where local states, actions and policies have to be communicated.

A. Experiment 1
For the comparison of 3DPG and MADDPG, we consider a multi-agent coordination problem. We add an additional coordination layer to a version of the simple spread multi particle environment (SSMPE) presented in [2]. In the SSMPE, particles (the agents) move in the plane to cover a number of landmarks and the landmarks are episodically reset to new positions. The agents get a global reward exp (−average closest distance to the landmarks) ∈ (0, 1).
In this particular scenario, we did not observe any significant difference between 3DPG and MADDPG. This is because in SSMPE, the agents' actions do not require any form of coordination and the global reward at every time-step is only a function of the global state.
We now add another coordination layer to the environment. We now consider two agents that move around in the plane with the objective to minimize their average distance to three landmarks as before. However, the agents only get rewarded if they move/watch in the same direction. Specifically, the previous global reward gets weighted by exp (−angle between the orientation of the agents). (66) The new reward structure therefore requires that the agents coordinate their decisions. More details and algorithm hyperparameters used for training are presented in Appendix B. obtains better policies faster than MADDPG at the cost of higher training variance.

B. Experiment 2
In our second experiment, we show that 3DPG with communication is robust to large AoI and that 3DPG may even benefit from using older policies of other agents similar to how target networks improve training in single agent RL [5].
We again consider the two agent, three landmark problem from Experiment 1. In addition, we consider that each of the two agents uses an independent communication channel for communication. Specifically, each agent has a fixed communication budget of 15000 bits/slot to communicate with the other agent whenever their channel access is success. could be exchanged during the same time. We let each agent cycle between communicating a policy update followed by communicating 33 local tuples. In that sense we give "equal weight" to policy and data communication.
In Figure 3(a), we show the average reward per epoch. We see that 3DPG with even λ = e −4 is able to learn decent policies compared to centralized 3DPG, albeit at a slower convergence rate. Notably, the λ = e −4 run achieves this with AoIs frequently over 500 time steps (20 epochs) as shown in Figure 3(b). In addition, 3DPG with λ = e −4 has only access to 1 /3 of the global data tuples that are used by 3DPG with centralized training. This shows that 3DPG is highly robust to AoI and low data availability. Finally, an interesting observation is that the 3DPG runs with λ = e −1 , e −2 or e −3 consistently performed similar or even better than 3DPG centralized.
This indicates that 3DPG may even benefit from using older policies of other agents.

X. CONCLUSIONS AND FUTURE WORK
In this paper, we presented and analyzed 3DPG, a multi-agent reinforcement learning algorithm for decentralized, online learning in networked systems. We showed that our analysis can be modified to understand the popular MADDPG algorithm [2]. Our analysis and numerical examples show that 3DPG should be preferred when a multi-agent decision making problem requires coordinated decisions or a high degree of exploration.
In addition, we presented the first set of data availability assumptions (A1) for distributed online actor-critic learning in network systems. The assumptions describe how old locally available global data tuples are allowed to be so that 3DPG converges. Our numerical experiments show that 3DPG is highly robust to the use of this old information, which makes it attractive for distributed online multi-agent learning.
For future work, we plan to analyze the trade off between using network resources for policy communication vs. using network resources for data communication. In addition, we are working on an analysis of 3DPG an its variants under a traditional two-timescale step-size schedule.
Proof of Lemma 2: Fix ε ∈ (0, 1). By (A1)(a) there is a non-negative integer-valued random variable τ , such that P τ ij (n) > εn we have therefore shown that ∞ n=0 P τ ij (n) > εn The last inequality follows since τ is a non-negative integer-valued random variable, using the following proposition: Proposition 1. Suppose X is a non-negative integer-valued random variable, then for every q > 0: ((m + 1) q − m q )P (X > m) .
Define the filtration F n−1 := σ(s m , a m , θ m , φ m | m ≤ n) for n ≥ 1. It then follows that {Ψ n } is a zero-mean martingale. It follows from (A3) and the C 2 condition in (A5) that sup n≥0 ψ i n ≤ K < ∞ for a sample path dependent constant K. It then follows from the martingale convergence theorem [28] that Ψ i n converges, since n m=0 α 2 (m) ψ i m 2 < ∞ almost surely by (A2)(a).
Proof: of Lemma 6: Consider the sequence θ i n . The proof for the other parameter sequences are identical. Fix T > 0. We need to show that converges to zero. The norm in (76) is bounded by We can now expand the second term, by successively adding zeros for each policy of each agent j = i. We can then use Lemma 1 to bound the resulting expanison by a term Additionally, we are left with one term of the form Due to the compact convergence of every parameter sequences (Arzela-Ascoli theorem) every parameter sequence will converge uniformly over [0, T ]. This shows that (78) converges to zero.
Finally, (79) converges to zero as µ n → µ ∞ in distribution and since θ i ∞ (t), φ ∞ (t) are bounded almost surely by (A3)(a) and Lemma 5. Receive current state s i n ; Execute action a i n = µ i (s i n ; φ i n ) + N i n ; Observe r i n+1 and s i n+1 ; Allocate local data (s i n , a i n , s i n+1 ) and current local policy φ n i for transmission to other agents ;

Run communication protocols ;
Store completely received global tuples t i m in R i n ; Sample M transitions from R i n ; Apply iteration (9) using the sampled transitions ; end For our experiments, we consider a simplified version of the simple spread multi particle coordination problem in [2]. Agents and landmarks are represented by points in [−1, 1] 2 . Moreover, agents can move around by choosing a displacement from the set [−0.1, 0.1] 2 . Agents