# Decentralized Multiagent Actor-Critic Algorithm Based on Message Diffusion

Authors: Siyuan Ding; Shengxiang Li; Guangyi Liu; Ou Li; Ke Ke; Yijie Bai; Weiye Chen
Journal: Journal of Sensors
 (2021)

---

## Abstract

The exponential explosion of joint actions and massive data collection are two main challenges in multiagent reinforcement learning algorithms with centralized training. To overcome these problems, in this paper, we propose a model-free and fully decentralized actor-critic multiagent reinforcement learning algorithm based on message diffusion. To this end, the agents are assumed to be placed in a time-varying communication network. Each agent makes limited observations regarding the global state and joint actions; therefore, it needs to obtain and share information with others over the network. In the proposed algorithm, agents hold local estimations of the global state and joint actions and update them with local observations and the messages received from neighbors. Under the hypothesis of the global value decomposition, the gradient of the global objective function to an individual agent is derived. The convergence of the proposed algorithm with linear function approximation is guaranteed according to the stochastic approximation theory. In the experiments, the proposed algorithm was applied to a passive location task multiagent environment and achieved superior performance compared to state-of-the-art algorithms.


---

## Body

## 1. Introduction

An agent of reinforcement learning (RL) masters skills in a trial-and-error way. The agent is settled in an environment that gives the responses and rewards corresponding to its actions over discrete time steps. The learning process is modeled as a Markov decision process (MDP) [1, 2]. The goal of the agent is to find an optimal policy that maximizes the expectation of long-term gain without the knowledge of the world (model-free [3]). Traditional tabular RL fails to handle situations with large or continuous state space, which limits its wider application. Recent theoretical and practical development has revealed that deep learning (DL) techniques with the powerful representation ability can deal with such situations efficiently. Deep reinforcement learning (DRL), a combination of RL and DL, has made remarkable achievements in the fields of chess [4], video games [5], and physical control tasks [6]. At the same time, using DRL to solve multiagent problems [7, 8] has gradually broadened so that it has now introduced a new research field, called multiagent deep reinforcement learning (MARL) [9]. A series of recent studies have indicated that MARL algorithms have reached the top human levels in multiplayer real-time strategy games [10]. An important problem in MARL is to learn cooperation on team tasks [7], i.e., the MARL cooperation problem. So far, the most popular solution to this problem is centralized training and decentralized execution [11, 12]. Methods in this fashion need a global value function [13, 14] or a global critic [11] in the training stage and assume the existence of a control center that is able to access the global state [15]. However, due to the constraints of real-world factors such as energy, geographical limitations, and communication ability, it is hard to collect the data of all agents to a center with a large number of agents.Fully decentralized MARL algorithms yield promising results in large-scale multiagent cooperation problems, where agents learn and execute actions based on local observations. Independent Q-learning (IQL) [16, 17], as a simple and scalability algorithm, is a typical fully decentralized MARL algorithm. An IQL agent is trained through its local observations and executes an independent local policy. However, in the perspective of an individual agent, other agents’ actions are nonstationary [18], which makes the IQL fail in many tasks. In [19], the authors proposed a decentralized multiagent version of the tabular Q-learning algorithm called QD-learning, where each agent is only aware of its own local reward, exchanges information with others, but observes the global state and joint actions. [20] assumes that all the agents are placed in a time-varying network, and it proposes a fully distributed MARL actor-critic algorithm, in which each agent has its own value function that is parameterized and updated with a weighted sum of other agents’ parameters. The main limitation of this algorithm is that it also assumes that the global state and the joint actions of all agents can be obtained directly, which is still difficult to satisfy in many actual scenarios.The problem addressed in this paper is to reduce the problem of MARL algorithms caused by centralized training. To this end, this paper proposes a model-free and completely decentralized MARL algorithm based on message diffusion. In the method, all agents are assumed to be in a time-varying communication network, where each agent obtains information from its neighbors and spreads its local observation and action in a fashion of diffusion [21]. Each agent has its own reward function, and the global reward is computed as the mean of local rewards. Each agent is designed as an actor-critic reinforcement learner and maintains a local estimation of the global state and joint actions. These estimated variables are updated with their own observations as well as messages received from neighbors, namely, in a diffusion style. We leverage stochastic approximation to analyze the convergence of the update process in the proposed algorithm with linear function approximation, and the convergence is guaranteed under reasonable assumptions. The proposed algorithm is evaluated on multiagent passive location tasks, and the results demonstrate its convergence and effectiveness.


## 2. Actor-Critic for a Single Agent

The reinforcement learning process can be described by an MDPM=S,A,P,r, where S represents the set of states and A is the set of actions. Ps′∣s,a:S×A×S⟶0,1 denotes the state transition probability. The reward function is denoted as Rs,a:S×A⟶ℝ, and the instant reward at t is rt+1=Rst,at. The agent’s policy is represented as π:S×A⟶0,1, which is parameterized to π·,·;θ or πθ for short, with θ representing the parameters. The task of the agent is to learn a policy πθ to maximize the expectation of the cumulative reward, i.e., the objective function
(1)Jθ=limTE∑t=0T−1rt+1T=∑s∈Sdθs∑a∈Aπθs,aRs,a,where dθs=limtPst=s∣πθ represents the stationary state distribution of the Markov chain for policy π. For policy πθ, the action value function is defined by
(2)Qθs,a=E∑trt+1−Jθ∣s,a;πθ,which represents the expectation of the cumulative reward in the future since state s and taking action a. Qθs,a is parameterized as Qθs,a;ω or Qθω for short, with ω denoting the parameters of the action value function. The state value function is defined based on Qθs,a;ω, i.e., Vθs=∑a∈Aπθs,aQθs,a, and the advantage function is Aθs,a=Qθs,a−Vθs, which can be regarded as a measure of advantage of taking action a over other actions. According to [22], the gradient of the objective function Jθ can be computed by
(3)∇Jθ=Es~dθ,a~πθ∇θlogπθs,aAθs,a.The policy parameters are updated with the policy gradient:(4)θ⟵θ+β∇θJθ,where β>0 is the step size, and ψθ=∇θlogπθs,a is referred to as the score function of policy πθ.


## 3. Agents in Time-Varying Networks

Definition 1 (Networked agents).
Consider a finite directed graphGt=V,Ct, where V and Ct represent the set of agents and the set of communication relations, respectively. The number of agents is N=V, and the set of communication pairs is denoted as Ct=i,j∣i≠j,i,j∈V, with Ct=cti,jN×N denoting the connection matrix of agents. The multiagent Markov decision process with networked agents is denoted by S,Aii=1N,P,Rii=1N,Gtt≥0. There is at least one path for any pair of agents, and each agent can obtain the observations and actions of neighbors.At timet, the observation of agent i is sti∈Si, where Si⊆ℝKs represents the observation space and Ks∈ℕ+ refers to the dimension of the observation vector. The observations of all agents contribute to the global state st=st1,⋯,stN∈S⊆ℝKsN, S=∏i=1NSi. The action of agent i is defined as ati∈Ai⊆ℝKa, where Ka∈ℕ+ represents the dimension of the action space. The joint actions of all agents can be expressed as at=at1,⋯,atN∈A⊆ℝKaN, A=∏i=1NAi. Agent i holds a local estimation of the global state st,i∈S and a local estimation of joint actions at,i∈A (if t is not emphasized, they are denoted as si and ai, respectively). The reward obtained by agent i is denoted by rt+1i, which is assumed to be bounded. The joint policy, π:S×A⟶0,1, maps the global state onto the joint actions of all agents. Actions among agents are independent, and the relationship of the joint policy and local policies satisfies
(5)πθst,at=∏i∈Vπθist,i,at,i,where πθi·,·:S×A⟶0,1 is the local policy of agent i, which is parameterized by θi∈Θi⊆ℝK, with K∈ℕ+ being the dimension of agent i’s parameter space. The policy parameters of all agents are represented as θ=θ1Τ,⋯,θNΤΤ∈Θ, where Θ=∏i=1NΘi. The set of agent i’s neighbors is defined by Ni≜j∣j∈V,i,j∈C.Assumption 2.
For anyi∈V, si∈S, and ai∈A, the policy function πθisi,ai>0 is continuously differentiable at θi∈Θi. For any θ∈Θ, the Markov chain stt≥0 induced by πθ·,· is irreducible and aperiodic.The policyπθi·,· is differentiable for parameter θi so as to use deep neural networks. Furthermore, the Markov chain induced by policy πθ·,·, being aperiodic and irreducible [23], has stationary distribution.The task in the multiagent cooperation problem is to find a joint policy to maximize the expectation of the averaged long-term reward over all agents:(6)maximizeθJθ=limT1TE∑t=0T−11N∑i∈Vrt+1i=∑s∈Sdθs∑a∈Aπθs,aR¯s,a,where R¯=1/N∑Ris,a represents the global averaged reward function, and its value at time t takes r¯t=1/N∑i∈Vrti. Then, the global action value function Q is defined by
(7)Qtst,at=E∑t′≥1r¯t+t′−Jθ∣st,at;πθ.The local action value functionQi of agent i is
(8)Qtist,i,at,i=E∑t′≥1rt+t′i−Jθ∣st,i,at,i;πθi,which is parameterized as Qtist,i,at,i;ωti. Since Vs=∑a∈Aπs,a;θQs,a;ω, the local advantage function Ai is defined as
(9)Aist,i,at,i=Qtist,i,at,i;ωti−∑a′∈Aiπθisi,a′,at,−iQtisi,a′,at,−i;ωti,where at,−i represents the joint actions of all agents except for i.Assumption 3.
The global value function can be decomposed into a weighted sum of the local value functions over agents, namely,(10)Qs1,⋯,sN,a1,⋯,aN=∑i=1NciQisi,ai,where ci reflects the importance of individual action value function Qi·,·. Note that the action value function Qi·,· of agent i depends only on its local observation and action.Assumption3 is similar to [14], under which the following theorem about the gradient of the global objective function to a single agent holds.Theorem 4.
Under the conditions of Definition1, Assumption 2, and Assumption 3, the gradient of the global objective function to agent i’s policy is computed by
(11)∇θiJθ=Es~dθs,a~πθs,·ψiN−1∑j=1NAjst,i,at,i,where ψi=∇θilogπθist,i,at,i is the score function, and Aj is the local advantage function defined by (9).The proof of Theorem4 follows a similar scheme to [22], and the complete proof is provided in Appendix A. Theorem 4 indicates that the gradient of global objective function Jθ can be estimated by the agent’s local score function ψi and local advantage function Aj. Although there is a certain deviation between the local observation of a single agent and the global state, in a time-varying network, an agent can improve the accuracy of the global state estimation by exchanging messages. In the next section, a completely decentralized multiagent reinforcement learning algorithm based on message diffusion over a communication network is proposed.


## 4. Distributed Actor-Critic Based on Message Diffusion

Suppose that, for a group of intelligent agents with communication abilities, each agent expects to obtain more information from other agents to estimate the value function and optimize its policy more accurately. But it can only obtain partial observations and receive messages via the communication network. In this section, a message diffusion-based distributed MARL algorithm is proposed to ensure agents gain global information and spread their observations efficiently.In the algorithm, at time stept, each agent holds a global state estimation st,i and joint action estimation at,i, which are updated by
(12)μt+1i=1−βω,t·μti+βω,t·rt+1i,(13)st,i⟵ei⊗sti+1N−ei⊗1Ks·st,i,(14)at,i⟵ei⊗ati+1N−ei⊗1Ka·at,i,(15)st+1,i=∑j∈Nicti,jst,j,at+1,i=∑j∈Nicti,jat,j,where μti is an estimation of the long-term return of the agent i with the bootstrapping update, and βω,t>0 is the step size. The agent i’s global state estimation is updated in two steps. In step one, the corresponding part of the global state estimation is replaced according to (13), where ei is a unit vector with the dimension of N with only element i being 1. ⊗ represents the Kronecker product. 1N is an N-dimension vector with all the elements being 1, and 1Ks is defined similarly. The operation “·” in (13) and (14) is the element-wise product. In step two, the global state estimation is updated with message diffusion according to (15). The parameters in the value function of agent i are updated through the following equation:
(16)ωt+1i=ωti+βω,tδti∇ωiQtist,i,at,i;ωti,where δti denotes the local temporal difference error of agent i, i.e., δti⟵rt+1i−μti+Qt+1ist+1,i,at+1,i;ωti−Qtist,i,at,i;ωti. According to Theorem 4, the policy of agent i is improved via gradient ascend:
(17)θt+1i=θti+βθ,tψti1N∑j∈VAjst,i,at,i,where βθ,t is the step size, Aist,i,at,i is the local advantage function defined by (9), and ψti=∇θilogπθist,i,at,i is the score function. Algorithm 1 summarizes the steps of the proposed approach. The algorithm works in an on-policy fashion; i.e., transitions are discarded once utilized in the update of policy parameters.Algorithm 1: Multiagent actor-critic algorithm based on message diffusion.
Input: Initialize parameters μ0i,ω0i,θ0i,∀i∈V and step sizes βω,t,βθ,t. Agent i initializes a0i and obtains observation s0i, then initializes estimations s0,i,a0,i. Initialize the counter t⟵0.1:repeat2:fori=1,⋯,Ndo3:  Sample and execute an actionati from the policy function πθist,i,·, and obtain st+1i,rt+1i;4:  Update the rewardμt+1i⟵1−βω,tμti+βω,trt+1i;5:  Update the local statest,i⟵ei⊗sti+1N−ei⊗1Ks·st,i;6:  Update the local actionat,i⟵ei⊗ati+1N−ei⊗1Ka·at,i;7:  Sendst,i and at,i to neighbors.8:end for9:fori=1,⋯,Ndo10:  Update the estimation of the global statest+1,i⟵∑j∈Nicti,jst,j;11:  Update the estimation of the joint actionat+1,i⟵∑j∈Nicti,jat,j;12:end for13:fori=1,⋯,Ndo14:  Calculate the temporal difference errorδti⟵rt+1i−μti+Qt+1ist+1,i,at+1,i;ωti−Qtist,i,at,i;ωti.15:  Update the criticωt+1i⟵ωti+βω,tδti∇ωiQtist,i,at,i;ωti;16:  Update the advantage functionAist,i,at,i=Qtist,i,at,i;ωti−∑a′∈Aiπθisi,a′,at,−iQtisi,a′,at,−i;ωti;17:  Update the score functionψti⟵∇θilogπθist,i,at,i;18:  Update the actorθt+1i⟵θti+βθ,tβθ,tψti1/N∑j∈VAjst,i,at,i;19:end for20:t⟵t+1;21:until the algorithm converges.


## 5. Convergence Analysis

To analyze the convergence of Algorithm1, we make several assumptions on the policy update and the step sizes. Under these assumptions and linear function approximations, it is shown that both the value function and the policy function in Algorithm 1 converge almost surely.Assumption 5.
For agenti, the update of policy θi is a projection operator Γi:ℝK⟶Θi⊆ℝK. Moreover, Θ=∏i∈VΘi includes at least one local maximum of Jθ.This assumption is commonly used in the analysis of transient behavior with stochastic approximation [24, 25]. In fact, this assumption is only for the convenience of analysis and is not necessary for experiments.Assumption 6.
The step sizesβω,t and βθ,t satisfy ∑tβω,t=∑tβθ,t=∞, ∑tβω,t2+βθ,t2<∞, limt⟶∞βθ,tβω,t−1=0, and limt⟶∞βω,tβω,t+1−1=1.Assumption6 is essential for stochastic approximation and other stochastic bootstrapping algorithms. It ensures that the correction of each step becomes smaller and smaller; however, the reduction speed is not too fast to converge independently without respect to the initial states.The action value function of agenti is approximated by a linear function family Qis,a;ωi=ωiΤϕis,a, where ϕis,a=ϕ1is,a,⋯,ϕKis,aΤ∈ℝK is the feature corresponding to the state-action pair s,a, which is uniformly bounded. The feature matrix Φ∈ℝSA×K has full column rank, and the kth column of which is denoted by ϕks,a,s∈S,a∈AΤ. For convenience, ϕsi,ai is abbreviated as ϕi.Theorem 7.
Under Assumptions2, 3, 5, and 6, for any policy πθ, the value parameter sequence ωti generated by (16) converges to ωθi with probability 1, where ωθi is related to policy πθ.Proof.
With linear function approximation, the update process of parameterωti is
(18)ωt+1i=ωti+βω,tδtiϕti.
The gradientδϕ in the update process can be seen as the error caused by current parameter ωti. We construct the square of it as Zωti=1/2δϕΤδϕ. When Zωti takes the minimum value, δϕ=0 holds. Hence, the convergence point of ωti can be found through optimizing Zωti. The gradient of Zωti is ∇ωtiZωti=ϕϕ′−ϕΤΤδϕ, where ϕ′=ϕt+1. Rewrite (16) via introducing a random variable ξt to estimate δtϕt:
(19)ξt+1i=ξti+βξ,tδtiϕti−ξti,ωt+1i=ωti+βω,tϕt+1i−ϕtiϕtiΤξti,where βξ,t>0 is the update step size, which satisfies Assumption 6. We assume that the second-order moments of ϕti and ϕt+1i are bounded. Let A=Eϕtϕt−ϕt+1Τ, b=Ert−μtϕt, vt=ξt/η, η>0, ρtΤ=vtΤ,ωtΤ, and gt+1Τ=rt−μtϕtΤ,0Τ. Rewrite the update process in (19) by
(20)ρt+1=ρt+βω,tηGt+1ρt+gt+1,where
(21)Gt+1=−ηIϕtϕt+1−ϕtΤϕt+1−ϕtϕtΤ0.
We analyze the convergence of (20) with the stochastic approximation theory [26]. Let
(22)G=EGt=−ηIAAΤ0,g=Egt=b0.
AsEδϕ=0 and Gρ+g=0, we rewrite (20) as
(23)ρt+1=ρt+βω,tηGρt+g+Gt+1−Gρt+gt+1−g=ρt+βω,t′hρt+Mt+1,where βω,t′=βω,tη, hρ=Gρ+g, Mt+1=Gt+1−Gρt+gt+1−g, and Ft=σρ1,M1,⋯,ρt−1,Mt. The stochastic approximation theory requires the following:
(1)
Functionh is Lipschitz continuous, and h∞ρ=limc⟶∞hcρ/c exists(2)
Mt,Ft is a martingale difference sequence, and there exits C0>0 so that E∥Mt+1∥2∣Ft≤C01+∥ρt∥2 for any ρ1(3)
The step sizeβω,t′ satisfies Assumption 6(4)
Ordinary differential equationρ̇=hρ has origin as the unique global asymptotically stable equilibrium
The update process described by (20) obviously satisfies conditions (2) and (3). To satisfy condition (1), it only needs to judge whether limc⟶∞r−μϕ/c is bounded. It is rational to let ϕ be bounded, and ϕ′ is updated based on message diffusion and bounded because Ct is a stochastic matrix. According to Definition 1, the instant reward r is bounded. We proved the convergence analysis of r, which indicates that μ is bounded, in Appendix B.
Since the feature matrixϕ has full rank, A is a nonsingular matrix. Let G=AΤA, and then detG=detAΤA≠0, and the eigenvalues of G are nonzero. Denote an eigenvalue of G by λ∈ℂ, λ≠0, and the corresponding feature vector by x∈ℂ2K, ∥x∥2=x∗x=1. Let xΤ=x1Τ,x2Τ, where x1,x2∈ℂK. According to the definition of G, λ=x∗Gx=−η∥x1∥2+x2∗AΤx1−x1∗Ax2. Because A is a real matrix, x2∗AΤx1∗=x1∗Ax2. The real part of feature vector λ is Reλ=−η∥x1∥2<0. So ρ̇=hρ has global asymptotically stable equilibria. According to the stochastic approximation theory [26], the update described by (21) converges; thus, ωti converges almost surely.Theorem 8.
Under Assumptions2, 5, and 6, the policy parameter θi updated through (17) converges to the asymptotically stable equilibrium of the following ordinary differential equation (ODE) with the probability of 1:
(24)θ̇i=Γ∧iEst~dθ,at~πθAti·ψti,∀i∈V,where Γ∧igθ=lim0<η⟶0Γiθi+ηgθ−θi/η, and g:Θ⟶Θ is a continuous function, e.g., gθ=Atiψti.Proof.
Denote theσ field generated by θτ,τ≤t as Ft,2=σθτ,τ≤t. Define two random variables:
(25)ζt+1,1=Atψt−EAtψt∣Ft,2,ζt+1,2=EAt−At,θtψt∣Ft,2,where
(26)At,θti=ϕtΤωθ−∑ai∈Aiπθist,i,ai,at,−iϕst,i,ai,at,−iΤωθ.
The update process of (17) is represented in projection as
(27)θt+1i=Γiθti+βθ,tEAt,θtiψti∣Ft,2+ζt+1,1i+ζt+1,2i.
Due to the convergence of the policy evaluation,ωti⟶ωθi, we have Ati⟶At,θti. Let Mti=∑τ=0tβθ,tζt+1,1i, and then Mti is a martingale difference sequence. Since ωti, ψti, and ϕti are bounded, Mti is bounded. Based on Assumption 6, it holds that
(28)∑tE∥Mt+1i−Mti∥2∣Ft,2=∑∥βθ,tζt+1,1∥2<∞.
Furthermore,Mti converges according to the convergence theory of the martingale difference sequence [23]. Thus, for any ε>0,
(29)limtℙsupn≥t∥∑τ=tnβθ,τζτ+1,1i∥>ε=0.
Therefore, (27) satisfies the necessary conditions of the Kushner-Clark theory [28, 29], and the policy parameter θi will converge to the asymptotically stable equilibrium of ODE (24).


## 6. Experiments

In this section, from two aspects, our proposed method is evaluated:(i)
Ablation study, which investigates the influence of the agent number on the performance(ii)
Comparison study, which studies the advantages of the proposed method, compared with existing methods


### 6.1. Multiagent RL for Passive Location Tasks

The experiments are performed with a passive location task environment, which is a reinforcement learning environment where agents need to automatically find an optimal geometry to improve the positioning precision. The environment is introduced by [27], where all the agents are controlled by a brain that maps the global observation into joint actions. We modified the environment into a multiagent one by limiting the observation so that each agent can only access its own radio signals and position. Furthermore, each agent has a distinct brain that consists of an actor and a critic, learning and making decisions independently.The whole scheme of the environment is shown in Figure1. Consider a circular region with a radius of 6 km, at the center of which is a transmitter that emits radio signals all the time. The area within 1 km of the transmitter is a forbidden area, filled with the blue grid. Each agent is equipped with a radio receiver that can intercept wireless signals to estimate the position of the transmitter. All the radio receivers are assumed to have the same performance in processing wireless signals. According to the sensitivity of the radio receiver, when agents go beyond a distance of 4 km away from the transmitter, nothing can be received. So, it is better for the agents to optimize the geometry within a closer region to the transmitter, which is shown as the dark gray area in Figure 1. Considering the multipath and interference of electromagnetic propagation, there are three low signal-to-noise ratio (SNR) regions, where signals received by the agents are contaminated by strong noises, leading to low positioning precision. The position of the transmitter is estimated in two steps: firstly, figuring out the time lag of signal propagation of each pair of agents, and secondly, estimating the transmitter’s position that satisfies the time lags obtained in the first step with least square algorithms. The task of the agents is to navigate to an optimal geometry configuration step-by-step, avoiding low SNR and forbidden regions, improving positioning precision.Figure 1
Multiagent passive location task environment. Agents need to find an optimal geometry to improve the positioning precision collaboratively. Each agent can only access partial observation, i.e., signals received by itself as well as its own position information. An agent can communicate with other agents within 2 km (neighbors), sharing individual observations. The light gray area shows the physical feasible area for all the agents, and the dark gray area shows where the agents can receive valid signals for passive positioning.


### 6.2. Setup

We model the passive location task as a multiagent decision-making problem, on which we evaluate our proposed method. According to the key components of reinforcement learning, the observation, action, and reward function are defined as follows.


#### 6.2.1. Observations

The observation of agenti comprises the features of the received signals fzi and its position xi,yi. The state of agent i is presented by si=fzi,xi,yi, where f· is a function that extracts features from the signals. In the experiment, the features of received signals refer to the SNRs.


#### 6.2.2. Action

The action of agenti is the position adjustment of itself, Δxi,Δyi. Hence, the agent will move to xi+Δxi,yi+Δyi in the next time step. In the experiment, actions are clipped within an interval of −50,50.


#### 6.2.3. Reward

All the agents share the same reward in each time step. The reward function reflects the positioning precision, which is defined by(30)rRMSEp,på=−10log101+1Nest∑k=1Nest∥påk−på∥2,where på is the position of the transmitter, påk is the kth estimation of på, and Nest denotes the estimation time in each time step. In the experiment, we have Nest=100.For each agent, both the actor and the critic are designed as fully connected neural networks, which have two hidden layers of 256 neural units, and each layer is followed by an activation layer oftanh function. The actor maps the observation into actions. Specifically, it takes in the observation, then generates a two-dimensional Gaussian distribution, from which the action is sampled. The structure of the critic is similar to that of the actor, but the output is the value function that is used to optimize the actor according to the policy gradient theory.The diffusion processes are completed one by one among agents but in a random order, and each agent updates its global state estimation from neighbors only once at each time step. Agents within 2 km are called neighbors. As shown in Figure1, agent 2 is a neighbor of agent 1. Under the setting of Figure 1, agent 1 is able to access the observation and last action of agent 2 but cannot obtain these information of agent 3.


### 6.3. Ablation Study

To understand the influence of the agent number on the performance, we performed a series of experiments with different agent numbers (N=3,5,7,10) on the passive location task described above. Concretely, we focus on these indices that reflect the process of training across all the agents: averaged episode return, averaged episode length, policy entropy, and averaged number of neighbors. The maximum number of steps in an epoch is 800, with each episode executing no more than 100 steps.Figure2 shows the training curves after 1000 epochs across 5 random seeds 0,100,200,300,400,500 that initialize the agents. The optimizer and learning rate are Adam and 1×10−4, respectively. Averaged episode return is a key indicator that reflects the ability of agents to accomplish the given task. From Figure 2(a), it can be seen that when N=3, agents cannot master useful skills to obtain a higher episode return. But the performance is improved with the increase of the agent number (N=5,7,10). It is consistent with Figure 2(b), in which the averaged number of neighbors increases as the scale of agents becomes larger. The averaged number of neighbors reflects the connectivity of agents, which determines the diffusion efficiency of messages between agents. When agent number N=3, agents may be scattered with distances out of the ability to exchange information. In that case, our message diffusion-based method reduced to independent agents, not being able to handle the cooperative task in a partial observation environment.Figure 2
Training curves for the passive location tasks over different scales of agents across 5 random seeds. (a) The averaged episode return. (b) The averaged number of neighbors. (c) Mean policy entropy across all the agents. (d) Mean loss of value function across all the agents.
(a)(b)(c)(d)Figures2(c) and 2(d) demonstrate the trend of mean policy entropy as well as the averaged episode length over agents across 1000 epochs of training. Both these two indicators drop as more agents take part in the task. The decrease of episode length indicates that agents can accomplish the task with fewer steps and find more elegant paths to optimal geometries collaboratively. The decline of policy entropy suggests that the agents become more confident in decision-making.


### 6.4. Comparison Study

In the comparison study, we investigate the advantages of our proposed method with two kinds of algorithms that are popular in the field of decentralized multiagent reinforcement learning. One is independent agents developed by algorithms such as IQL [16]. But in the passive location task, the action space is continuous, and we have every agent learning with its own actor-critic structure for handling partial observation, called independent actor-critic (IAC). Another similar decentralized algorithm that we make a comparison to is proposed in [20], where the agents update their neural networks by directly combining the parameters of neighbors. We refer to this method by weight sharing (WS).The proposed method in this paper facilitates the collaboration of agents by message diffusion, which makes individual estimation of the global state more accurate. We performed our method (Diffu for short) and the contrast methods (IAC and WS) with different numbers of agents (N=3,5,7,10), and the results are demonstrated in Figure 3. In general, our method has superior performance in the experiments. It can be seen that for the proposed method, the more agents there are, the more advantages can be obtained. IAC failed in all the experiments due to the inherent challenge faced with a multiagent environment; i.e., from the perspective of an individual agent, the actions of other agents become nonstationary. WS attempts to address the challenge by introducing weight sharing among agents. It obtained the information of neighbors in an indirect way that combines neural network parameters of neighbors, but it is not so effective in the experiments. In the task of passive location, with more agents, message diffusion becomes easier so that each agent has a more accurate estimation of the global state, which is helpful to tackle the nonstationary problem.Figure 3
Performance curves compared to IAC and WS over different numbers of agents. (a)N=3. (b) N=5. (c) N=7. (d) N=10.
(a)(b)(c)(d)The learned agents are able to perform passive location tasks effectively. Figure4 shows the trajectories that navigate to an optimal geometry with different numbers of agents (N=7,10). In these two scenarios, agents can adjust the geometry collaboratively to improve the positioning precision and even master the skills such as taking a detour to avoid low forbidden regions or sacrifice immediate reward for a better geometry configuration.Figure 4
How trained agents accomplish passive location tasks collaboratively. (a) Number of agentsN=7. (b) Number of agents N=10.
(a)(b)


## 6.1. Multiagent RL for Passive Location Tasks

The experiments are performed with a passive location task environment, which is a reinforcement learning environment where agents need to automatically find an optimal geometry to improve the positioning precision. The environment is introduced by [27], where all the agents are controlled by a brain that maps the global observation into joint actions. We modified the environment into a multiagent one by limiting the observation so that each agent can only access its own radio signals and position. Furthermore, each agent has a distinct brain that consists of an actor and a critic, learning and making decisions independently.The whole scheme of the environment is shown in Figure1. Consider a circular region with a radius of 6 km, at the center of which is a transmitter that emits radio signals all the time. The area within 1 km of the transmitter is a forbidden area, filled with the blue grid. Each agent is equipped with a radio receiver that can intercept wireless signals to estimate the position of the transmitter. All the radio receivers are assumed to have the same performance in processing wireless signals. According to the sensitivity of the radio receiver, when agents go beyond a distance of 4 km away from the transmitter, nothing can be received. So, it is better for the agents to optimize the geometry within a closer region to the transmitter, which is shown as the dark gray area in Figure 1. Considering the multipath and interference of electromagnetic propagation, there are three low signal-to-noise ratio (SNR) regions, where signals received by the agents are contaminated by strong noises, leading to low positioning precision. The position of the transmitter is estimated in two steps: firstly, figuring out the time lag of signal propagation of each pair of agents, and secondly, estimating the transmitter’s position that satisfies the time lags obtained in the first step with least square algorithms. The task of the agents is to navigate to an optimal geometry configuration step-by-step, avoiding low SNR and forbidden regions, improving positioning precision.Figure 1
Multiagent passive location task environment. Agents need to find an optimal geometry to improve the positioning precision collaboratively. Each agent can only access partial observation, i.e., signals received by itself as well as its own position information. An agent can communicate with other agents within 2 km (neighbors), sharing individual observations. The light gray area shows the physical feasible area for all the agents, and the dark gray area shows where the agents can receive valid signals for passive positioning.


## 6.2. Setup

We model the passive location task as a multiagent decision-making problem, on which we evaluate our proposed method. According to the key components of reinforcement learning, the observation, action, and reward function are defined as follows.


### 6.2.1. Observations

The observation of agenti comprises the features of the received signals fzi and its position xi,yi. The state of agent i is presented by si=fzi,xi,yi, where f· is a function that extracts features from the signals. In the experiment, the features of received signals refer to the SNRs.


### 6.2.2. Action

The action of agenti is the position adjustment of itself, Δxi,Δyi. Hence, the agent will move to xi+Δxi,yi+Δyi in the next time step. In the experiment, actions are clipped within an interval of −50,50.


### 6.2.3. Reward

All the agents share the same reward in each time step. The reward function reflects the positioning precision, which is defined by(30)rRMSEp,på=−10log101+1Nest∑k=1Nest∥påk−på∥2,where på is the position of the transmitter, påk is the kth estimation of på, and Nest denotes the estimation time in each time step. In the experiment, we have Nest=100.For each agent, both the actor and the critic are designed as fully connected neural networks, which have two hidden layers of 256 neural units, and each layer is followed by an activation layer oftanh function. The actor maps the observation into actions. Specifically, it takes in the observation, then generates a two-dimensional Gaussian distribution, from which the action is sampled. The structure of the critic is similar to that of the actor, but the output is the value function that is used to optimize the actor according to the policy gradient theory.The diffusion processes are completed one by one among agents but in a random order, and each agent updates its global state estimation from neighbors only once at each time step. Agents within 2 km are called neighbors. As shown in Figure1, agent 2 is a neighbor of agent 1. Under the setting of Figure 1, agent 1 is able to access the observation and last action of agent 2 but cannot obtain these information of agent 3.


## 6.2.1. Observations

The observation of agenti comprises the features of the received signals fzi and its position xi,yi. The state of agent i is presented by si=fzi,xi,yi, where f· is a function that extracts features from the signals. In the experiment, the features of received signals refer to the SNRs.


## 6.2.2. Action

The action of agenti is the position adjustment of itself, Δxi,Δyi. Hence, the agent will move to xi+Δxi,yi+Δyi in the next time step. In the experiment, actions are clipped within an interval of −50,50.


## 6.2.3. Reward

All the agents share the same reward in each time step. The reward function reflects the positioning precision, which is defined by(30)rRMSEp,på=−10log101+1Nest∑k=1Nest∥påk−på∥2,where på is the position of the transmitter, påk is the kth estimation of på, and Nest denotes the estimation time in each time step. In the experiment, we have Nest=100.For each agent, both the actor and the critic are designed as fully connected neural networks, which have two hidden layers of 256 neural units, and each layer is followed by an activation layer oftanh function. The actor maps the observation into actions. Specifically, it takes in the observation, then generates a two-dimensional Gaussian distribution, from which the action is sampled. The structure of the critic is similar to that of the actor, but the output is the value function that is used to optimize the actor according to the policy gradient theory.The diffusion processes are completed one by one among agents but in a random order, and each agent updates its global state estimation from neighbors only once at each time step. Agents within 2 km are called neighbors. As shown in Figure1, agent 2 is a neighbor of agent 1. Under the setting of Figure 1, agent 1 is able to access the observation and last action of agent 2 but cannot obtain these information of agent 3.


## 6.3. Ablation Study

To understand the influence of the agent number on the performance, we performed a series of experiments with different agent numbers (N=3,5,7,10) on the passive location task described above. Concretely, we focus on these indices that reflect the process of training across all the agents: averaged episode return, averaged episode length, policy entropy, and averaged number of neighbors. The maximum number of steps in an epoch is 800, with each episode executing no more than 100 steps.Figure2 shows the training curves after 1000 epochs across 5 random seeds 0,100,200,300,400,500 that initialize the agents. The optimizer and learning rate are Adam and 1×10−4, respectively. Averaged episode return is a key indicator that reflects the ability of agents to accomplish the given task. From Figure 2(a), it can be seen that when N=3, agents cannot master useful skills to obtain a higher episode return. But the performance is improved with the increase of the agent number (N=5,7,10). It is consistent with Figure 2(b), in which the averaged number of neighbors increases as the scale of agents becomes larger. The averaged number of neighbors reflects the connectivity of agents, which determines the diffusion efficiency of messages between agents. When agent number N=3, agents may be scattered with distances out of the ability to exchange information. In that case, our message diffusion-based method reduced to independent agents, not being able to handle the cooperative task in a partial observation environment.Figure 2
Training curves for the passive location tasks over different scales of agents across 5 random seeds. (a) The averaged episode return. (b) The averaged number of neighbors. (c) Mean policy entropy across all the agents. (d) Mean loss of value function across all the agents.
(a)(b)(c)(d)Figures2(c) and 2(d) demonstrate the trend of mean policy entropy as well as the averaged episode length over agents across 1000 epochs of training. Both these two indicators drop as more agents take part in the task. The decrease of episode length indicates that agents can accomplish the task with fewer steps and find more elegant paths to optimal geometries collaboratively. The decline of policy entropy suggests that the agents become more confident in decision-making.


## 6.4. Comparison Study

In the comparison study, we investigate the advantages of our proposed method with two kinds of algorithms that are popular in the field of decentralized multiagent reinforcement learning. One is independent agents developed by algorithms such as IQL [16]. But in the passive location task, the action space is continuous, and we have every agent learning with its own actor-critic structure for handling partial observation, called independent actor-critic (IAC). Another similar decentralized algorithm that we make a comparison to is proposed in [20], where the agents update their neural networks by directly combining the parameters of neighbors. We refer to this method by weight sharing (WS).The proposed method in this paper facilitates the collaboration of agents by message diffusion, which makes individual estimation of the global state more accurate. We performed our method (Diffu for short) and the contrast methods (IAC and WS) with different numbers of agents (N=3,5,7,10), and the results are demonstrated in Figure 3. In general, our method has superior performance in the experiments. It can be seen that for the proposed method, the more agents there are, the more advantages can be obtained. IAC failed in all the experiments due to the inherent challenge faced with a multiagent environment; i.e., from the perspective of an individual agent, the actions of other agents become nonstationary. WS attempts to address the challenge by introducing weight sharing among agents. It obtained the information of neighbors in an indirect way that combines neural network parameters of neighbors, but it is not so effective in the experiments. In the task of passive location, with more agents, message diffusion becomes easier so that each agent has a more accurate estimation of the global state, which is helpful to tackle the nonstationary problem.Figure 3
Performance curves compared to IAC and WS over different numbers of agents. (a)N=3. (b) N=5. (c) N=7. (d) N=10.
(a)(b)(c)(d)The learned agents are able to perform passive location tasks effectively. Figure4 shows the trajectories that navigate to an optimal geometry with different numbers of agents (N=7,10). In these two scenarios, agents can adjust the geometry collaboratively to improve the positioning precision and even master the skills such as taking a detour to avoid low forbidden regions or sacrifice immediate reward for a better geometry configuration.Figure 4
How trained agents accomplish passive location tasks collaboratively. (a) Number of agentsN=7. (b) Number of agents N=10.
(a)(b)


## 7. Conclusion

This paper investigated the multiagent problem in a time-varying network, where agents only observe partial information and exchange information with neighbors. A fully decentralized actor-critic multiagent reinforcement learning algorithm based on message diffusion is proposed. Each agent is trained to make decisions depending on its own local observations and messages received from neighbors. This completely noncentral training and execution method overcomes the data collection challenges, especially when both the state space and the action space are massive. The convergence of the proposed algorithm with linear function approximation is guaranteed. Experimental results confirmed the convergence and effectiveness of the proposed algorithm. This decentralized method can be used in many other areas, such as packet routing in computer/wireless communications. In future work, more general function approximations will be employed to analyze the convergence of the algorithm.



---

*Source: 8739206-2021-12-08.xml*