# Distributed Policy Evaluation with Fractional Order Dynamics in Multiagent Reinforcement Learning

Authors: Wei Dai; Wei Wang; Zhongtian Mao; Ruwen Jiang; Fudong Nian; Teng Li
Journal: Security and Communication Networks
 (2021)

---

## Abstract

The main objective of multiagent reinforcement learning is to achieve a global optimal policy. It is difficult to evaluate the value function with high-dimensional state space. Therefore, we transfer the problem of multiagent reinforcement learning into a distributed optimization problem with constraint terms. In this problem, all agents share the space of states and actions, but each agent only obtains its own local reward. Then, we propose a distributed optimization with fractional order dynamics to solve this problem. Moreover, we prove the convergence of the proposed algorithm and illustrate its effectiveness with a numerical example.


---

## Body

## 1. Introduction

In recent years, reinforcement learning [1] has received much attention from the society and succeeded remarkably in many areas such as machine learning and artificial intelligence [2]. As we all know, in reinforcement learning, an agent determines the optimal strategy under the feedback of rewards via constantly interacting with the environment. The function of the policy maps possible states to possible actions. Although reinforcement learning has made great achievements in single agent, it remains challenging in the application of multiagent [3]. The goal of the multiagent system is to enable several agents with simple intelligence, but it is easy to manage and control to realize complex intelligence through mutual cooperation. While reducing the complexity of system modeling, the robustness, reliability, and flexibility of the system should be improved [4, 5].In this paper, the objective of this paper is to investigate multiagent reinforcement learning (MARL), where each agent exchanges information with their neighbors in network systems [6]. All agents share the state space and action except local rewards. The purpose of the MARL is to determine the global optimal policy, and a feasible way is to construct a central controller, where each agent must exchange information with the central controller [7], which makes decisions for all of them. However, with the increase of state dimensions, the computation of the central controller becomes extensively heavy. The whole system would collapse if the central controller was attacked.Then, we try to replace the centralized algorithm mentioned above with distributed control [8, 9]. Consistency protocol based on design enables all agents to achieve the same state [10–13]. In [14], Zhang et al. proposed a continuous-time distributed version of the gradient algorithm. As far as we know, most of the gradient methods use integer order iteration. In fact, fractional order has been developed for 300 years and used to solve many kinds of problems such as control applications and systems’ theory [15–17]. In comparison with the traditional integer order algorithm, the fractional order algorithm has more design freedom and potential to obtain better convergence performance [18, 19].Hereinafter, the contributions of the paper are listed:(1)
We transform the multiagent strategy evaluation problem into a distributed optimization problem with a consensus constraint(2)
We construct the fractional order dynamics and prove the convergence of the algorithm(3)
We take a numerical example to verify the superiority of the proposed fractional order algorithmThe rest organization of this paper is listed as follows. Section2 introduces some problems of formulation on MARL and fractional order calculus. Section 3 transforms the multiagent strategy evaluation problem into the optimization problem with a consensus constraint, proposes an algorithm with fractional order dynamics, and proves that the algorithm asymptotically converge to an exact solution. Section 4 presents a simulation example, and we summarize the work in Section 5.


## 2. Problem Formulation

### 2.1. Notations

Letℝ,ℝn, and ℝn×m represent the real number set, n-dimensional real column vector set, and n × m real matrix set, respectively. AT represents the transpose of A. A=∑i=1n∑i=1naij1/2,XG=XTGX, and A,B=ATB.S,Ai=1n,P,Rii=1n,γ represents a multiagent Markov decision process (MDP), where S is the state space and A is the joint action space. Pa is the probability of transition from st to st+1 when the agent takes the joint action a and Pπs,s′=Ea∼π·|sPas,s′, Ris,a is the local reward when agent i takes joint action a at state s and γ∈0,1 is a discount parameter. πa|s represents the condition of probability when the agent takes joint action a at state s. The reward function of agent i is defined when follows a joint policy π at state s as follows:(1)Riπs=Ea∼π·|sRis,a,where the right-hand side of the equation means that there is a probability for all possible choices of action a, and we calculate the expected value for all rewards of agent i:(2)Rcπs=1n∑i=1nRiπs,where Rcπs represents the average of the local rewards.


### 2.2. Graph theory

The graph is expressed asGV,E, where G represents a graph, V is the set of vertices, and E is the set of edges in G. If any edge in the graph is undirected, the graph is named as undirected graph [20]. In graph, A=aij∈ℝn×n is the adjacency matrix with aij≠0 if i,j∈E, aij=0 otherwise. D=diagd1,d2,…,d3 is the degree matrix with di=∑j=1naij and Laplacian matrix is L=D−A. Moreover, if the graph is connected, L has the following two properties:(1)
Laplacian matrix is a semipositive definite matrix(2)
The minimum eigenvalue is 0 because the sum of every row of the Laplace matrix is 0The minimum nonzero eigenvalue is defined as the algebraic connectivity of the graph.Assumption 1.
The undirected graph mentioned in the following text is connected.Lemma 1 (see [21]).
The frequency distributed model is defined for a fractional order systemDαxt=ut, where α∈0,1 as follows:(3)∂zω,t∂z=−ωzω,t+ut,yt=∫0∞μαωzω,tdω,where μα=sinαπ/ωαπ.Definition 1 (see [22]).
Theαth order Caputo derivative is(4)Dαft=1Γn−α∫0tt−τn−1−αfnτdτ,where α∈n−1,n, n∈ℕ,Γt=∫0∞τt−1e−τdτ is Gamma function, and fnt is the nth order derivative of ft.


### 2.3. Policy Evaluation

To measure the benefits of agents in its current state, we establish the following value function, which represents the value of the cumulative return obtained by agents starting from the statest, adopting a certain strategy π:(5)Vπs=Eπ∑m=1∞γmRcπst+m+1|st=s.We construct Bellman equation based onVπ∈ℝS and Rcπ∈ℝS:(6)Vπ=Rcπ+γPπVπ.It is difficult to evaluateVπ directly if the dimension of the state space is very large. Therefore, we use Vθs=ϕTsθ to approximate Vπ, where θ∈ℝd is the vector and ϕs:S⟶ℝd, which is a particular function for state s. Indeed, solving equation (6) is equivalent to obtain the vector θ via Vθ≈Vπ. In other words, it means to minimize the mean square error about 1/2Vθ−VπD2, where D=diagμπs,s∈S, ∈ℝS×S is a diagonal matrix determined by the stationary distribution. We construct the equation as follows:(7)fθ=12ΠΦVθ−γPπVθ−RcπD2+ρ2θ2,where ρ is a regularization parameter and ΠΦ is a projection operator in the column subspace of Φ. It is not difficult to rewrite ΠΦ as ΠΦ=ΦΦTDΦ−1ΦTD substituting ΠΦ into (7):(8)fθ=ρ2θ2+12ΠΦVθ−γPπVθ−RcπD2=ρ2θ2+12Vθ−γPπVθ−RcπTΠΦTDΠΦ×Vθ−γPπVθ−Rcπ=ρ2θ2+12Vθ−γPπVθ−RcπTDΦΦTDΦ−1ΦTD×Vθ−γPπVθ−Rcπ=ρ2θ2+12ΦTDVθ−γPπVθ−RcπΦTDΦ−12=ρ2θ2+12ΦTDΦ−γPπΦθ−ΦTDRcπΦTDΦ−12=ρ2θ2+12Aθ−bC−12,where A=ΦTDΦ−γPπΦ=Es∼μπϕsϕs−γϕs′T, C=ΦTDΦ=Es∼μπϕsϕTs, and b=ΦTDRcπ=Es∼μπRcπsϕs.The minimum value ofθ in equation (8) is unique if A is a full rank matrix and C is a positive definite matrix. In practice, it is difficult to get the expectations in the compact form when the distribution is unknown. We replace expectation with the average as follows:(9)A^=1p∑t=1PAt,b^=1p∑t=1Pbt,C^=1p∑t=1PCt,where At=ϕstφTst,φstϕstϕst+1T, Ct=ϕstϕTst, and bt=Rcπstϕst.We assume that the sample sizep approaches infinity to make sure its confidence level. In these sequences, each state is attached at least once. Then, we reconstruct equation (8) as follows:(10)fθ=12A^θ−b^C^−12+ρ2θ2.Noteworthy, in a shared space, the agent observes the states and actions of the neighbors, but only observes the local rewards of its own. In other words, we getA^ and C^ except b^. So, we define b^i=1/p∑t=1pbt,i with bt,i=Riπst,atϕst. Then, we rewrite equation (10) as follows:(11)minθ∈Rd1n∑t=1n12A^θ−b^iC−12+ρ2θ2.


## 2.1. Notations

Letℝ,ℝn, and ℝn×m represent the real number set, n-dimensional real column vector set, and n × m real matrix set, respectively. AT represents the transpose of A. A=∑i=1n∑i=1naij1/2,XG=XTGX, and A,B=ATB.S,Ai=1n,P,Rii=1n,γ represents a multiagent Markov decision process (MDP), where S is the state space and A is the joint action space. Pa is the probability of transition from st to st+1 when the agent takes the joint action a and Pπs,s′=Ea∼π·|sPas,s′, Ris,a is the local reward when agent i takes joint action a at state s and γ∈0,1 is a discount parameter. πa|s represents the condition of probability when the agent takes joint action a at state s. The reward function of agent i is defined when follows a joint policy π at state s as follows:(1)Riπs=Ea∼π·|sRis,a,where the right-hand side of the equation means that there is a probability for all possible choices of action a, and we calculate the expected value for all rewards of agent i:(2)Rcπs=1n∑i=1nRiπs,where Rcπs represents the average of the local rewards.


## 2.2. Graph theory

The graph is expressed asGV,E, where G represents a graph, V is the set of vertices, and E is the set of edges in G. If any edge in the graph is undirected, the graph is named as undirected graph [20]. In graph, A=aij∈ℝn×n is the adjacency matrix with aij≠0 if i,j∈E, aij=0 otherwise. D=diagd1,d2,…,d3 is the degree matrix with di=∑j=1naij and Laplacian matrix is L=D−A. Moreover, if the graph is connected, L has the following two properties:(1)
Laplacian matrix is a semipositive definite matrix(2)
The minimum eigenvalue is 0 because the sum of every row of the Laplace matrix is 0The minimum nonzero eigenvalue is defined as the algebraic connectivity of the graph.Assumption 1.
The undirected graph mentioned in the following text is connected.Lemma 1 (see [21]).
The frequency distributed model is defined for a fractional order systemDαxt=ut, where α∈0,1 as follows:(3)∂zω,t∂z=−ωzω,t+ut,yt=∫0∞μαωzω,tdω,where μα=sinαπ/ωαπ.Definition 1 (see [22]).
Theαth order Caputo derivative is(4)Dαft=1Γn−α∫0tt−τn−1−αfnτdτ,where α∈n−1,n, n∈ℕ,Γt=∫0∞τt−1e−τdτ is Gamma function, and fnt is the nth order derivative of ft.


## 2.3. Policy Evaluation

To measure the benefits of agents in its current state, we establish the following value function, which represents the value of the cumulative return obtained by agents starting from the statest, adopting a certain strategy π:(5)Vπs=Eπ∑m=1∞γmRcπst+m+1|st=s.We construct Bellman equation based onVπ∈ℝS and Rcπ∈ℝS:(6)Vπ=Rcπ+γPπVπ.It is difficult to evaluateVπ directly if the dimension of the state space is very large. Therefore, we use Vθs=ϕTsθ to approximate Vπ, where θ∈ℝd is the vector and ϕs:S⟶ℝd, which is a particular function for state s. Indeed, solving equation (6) is equivalent to obtain the vector θ via Vθ≈Vπ. In other words, it means to minimize the mean square error about 1/2Vθ−VπD2, where D=diagμπs,s∈S, ∈ℝS×S is a diagonal matrix determined by the stationary distribution. We construct the equation as follows:(7)fθ=12ΠΦVθ−γPπVθ−RcπD2+ρ2θ2,where ρ is a regularization parameter and ΠΦ is a projection operator in the column subspace of Φ. It is not difficult to rewrite ΠΦ as ΠΦ=ΦΦTDΦ−1ΦTD substituting ΠΦ into (7):(8)fθ=ρ2θ2+12ΠΦVθ−γPπVθ−RcπD2=ρ2θ2+12Vθ−γPπVθ−RcπTΠΦTDΠΦ×Vθ−γPπVθ−Rcπ=ρ2θ2+12Vθ−γPπVθ−RcπTDΦΦTDΦ−1ΦTD×Vθ−γPπVθ−Rcπ=ρ2θ2+12ΦTDVθ−γPπVθ−RcπΦTDΦ−12=ρ2θ2+12ΦTDΦ−γPπΦθ−ΦTDRcπΦTDΦ−12=ρ2θ2+12Aθ−bC−12,where A=ΦTDΦ−γPπΦ=Es∼μπϕsϕs−γϕs′T, C=ΦTDΦ=Es∼μπϕsϕTs, and b=ΦTDRcπ=Es∼μπRcπsϕs.The minimum value ofθ in equation (8) is unique if A is a full rank matrix and C is a positive definite matrix. In practice, it is difficult to get the expectations in the compact form when the distribution is unknown. We replace expectation with the average as follows:(9)A^=1p∑t=1PAt,b^=1p∑t=1Pbt,C^=1p∑t=1PCt,where At=ϕstφTst,φstϕstϕst+1T, Ct=ϕstϕTst, and bt=Rcπstϕst.We assume that the sample sizep approaches infinity to make sure its confidence level. In these sequences, each state is attached at least once. Then, we reconstruct equation (8) as follows:(10)fθ=12A^θ−b^C^−12+ρ2θ2.Noteworthy, in a shared space, the agent observes the states and actions of the neighbors, but only observes the local rewards of its own. In other words, we getA^ and C^ except b^. So, we define b^i=1/p∑t=1pbt,i with bt,i=Riπst,atϕst. Then, we rewrite equation (10) as follows:(11)minθ∈Rd1n∑t=1n12A^θ−b^iC−12+ρ2θ2.


## 3. Fractional Order Dynamics for Policy Evaluation

Hereinbefore, the aim of policy evaluation becomes to minimize the object function. Now, we rewrite (11) as follows:(12)minθi1n∑i=1n12A^θi−b^iC^−12+ρ2θi2,s.t.θi=θj.We defineθ¯∈ℝnd as a factor concatenating all θi: θ¯=θ1T,θ2T,…θnTT∈ℝnd and the aggregative function f as fθ¯=∑i=1nfθi. As we all know, the consensus constraint (12) is expressed as(13)minθ¯12A^¯θ¯−b^¯iC^¯-12+ρ2θ¯2,s.t.L¯θ¯=0,where b^¯=b^1T,b^2T,…b^nTT∈ℝnd,L∈ℝn×n,L¯=L⊗Id∈ℝnd×nd, A^¯=A^⊗In∈ℝnd×nd, and C^¯=C^⊗In ∈ℝnd×nd. Based on (13), we formulate the following the augmented Lagrangian:(14)ℒθ¯,λ=fθ¯+λ,L¯θ¯+12θ¯TL¯θ¯,where λ∈ℝnd is the Lagrange multiplier.It is feasible to design a fractional order continuous-time optimization algorithm from primal-dual viewpoint, gradient descend for primal variableθ¯, and gradient ascent for dual variable λ via (14). Both of them are updated according to the fractional order law:(15)Dα1θ¯t=−∇θ¯tℒθ¯t,λt,Dα2λt=∇λtℒθ¯t,λt,where 0<α1<2,0<α2<1,∇θ¯tℒθ¯t,λt, and ∇λtℒθ¯t,λt are gradient of θ¯t,λt on variables θ¯t and λt, respectively. We express the detail of (15) in Algorithm 1.Algorithm 1:
Initialization:θi=0∈ℝd,λi=0∈ℝd.UpdateFort≤50Dα1θit=−A^TC^−1A^+ρIθit−A^TC^−1b^i+L¯iλt+L¯iθ¯t,Dα2λit=L¯iθ¯tEndReturnθThe aim of the distributed algorithm is to obtain the solution of the value function. The proposed algorithm has more potential to get better convergence performance and design freedom than the conventional integer order. Hereinafter, we provide the following convergence conclusion.Theorem 1.
Under Assumption1, let θ¯t and λt be generated according to Algorithm 1. If 0<α1,α2<1, then θ¯t asymptotically converges to the optimal solution.Proof.
We obtain the detailed dynamics ofθ¯t and λt:(16)Dα1θ¯t=−A^¯TC^¯−1b^¯+ρI+L¯θ¯(t)+A^¯TC^¯−1b¯−L¯λt,Dα2λt=L¯θ¯(t,where I is an identity matrix. We consider the equilibrium of (16):(17)0=−A^¯TC^¯−1b^¯+ρI+L¯θ¯∗+A^¯TC^¯−1b¯−L¯λ∗,0=L¯θ¯∗.
Then, we combine (16) and (17), and according to the facts Dα1θ¯∗=0, Dα2λ∗=0,(18)Dα1θ¯˜t=−A^¯TC^¯−1b^¯+ρI+L¯θ¯˜t−L¯λ˜t,Dα2λ˜t=L¯θ¯˜t.
Through Lemma1, we reconstruct (18) as follows:(19)∂z1ω,t∂t=−ωz1ω,t−A^¯TC^¯−1b^¯+ρI+L¯θ¯˜t−L¯λ˜t,θ¯˜t=∫0∞μα1ωz1ω,tdωand(20)π∂z2ω,t∂t=−ωz2ω,t+L¯θ¯˜t,λ˜t=∫0∞μα2z2ω,tdω.
We construct the Lyapunov function as follows:(21)V1=12∫0∞∑i=12μαiωziω,t2dω.
Then,(22)V1.=∫0∞∑i=12μαiωziω,t,∂ziω,t∂tdω=∫0∞μα1ωz1ω,t,−ωz1ω,t−A^¯TC^¯−1b^¯+ρI+L¯θ¯˜t−L¯λ˜tⅆω+∫0∞μα2ωz2ω,t−ωz2ω,t+L¯θ¯˜tⅆω=−∫0∞∑i=12μαiωziω,t2dω+θ¯˜t,−A^¯TC^¯−1b^¯+ρI+L¯θ¯˜t−L¯λ˜t+λ˜t,L¯θ¯˜t=−∫0∞∑i=12μαiωziω,t2dω−θ¯˜tTA^¯TC^¯−1b^¯+ρI+L¯θ¯˜t≤0.
We obtain the result according to the Lasalle invariance principle.
Hereinafter, we improve the convergence conclusion of Theorem 1 by extendingα1 from (0,1) to (1,2).Theorem 2.
Under Assumption1, let θ¯t and λt be generated according to Algorithm 1. If 1<α1<2,α1+α2=2, then θ¯t asymptotically converges to the optimal solution.Proof.
Under the conditionα1=1+α¯1, we rewrite the dynamics with the condition of Theorem 1 as follows:(23)θ¯˜˙at=−A^¯TC^¯−1b^¯+ρI+L¯θ¯˜t−L¯λ˜t,Dα¯1θ¯˜t=θ¯˜at,Dα2θ¯˜t=L¯θ¯˜t.
Due toα1=1+α¯1 and α1+α2=2,(24)λ˜˙t=Dα1¯Dα2λ˜t=Dα1¯L¯θ¯˜t=L¯aθ¯˜t.
Under the condition of (23) and (24), we obtain the frequency distributed model by Lemma 1 as follows:(25)θ¯˜˙at=−A^¯TC^¯−1b^¯+ρI+L¯θ¯˜t−L¯λ˜t,∂z1ω,t∂t=−ωz1ω,t+θ¯˜at,θ¯˜t=∫0∞μα¯1ωz1ω,tdω,λ˜˙t=L¯θ¯˜at.
We construct the Lyapunov function:(26)V2=12θ¯˜at2+12λ˜t2.
Then,(27)V2.=θ¯˜at,θ¯˜at+λ˜t,λ˜˙t=θ¯˜at,−A^¯TC^¯−1b^¯+ρI+L¯θ¯˜at−L¯λ˜t+λ˜t,L¯θ¯˜at=−θ¯˜atTA^¯TC^¯−1b^¯+ρI+L¯θ¯˜t≤0.
Through the LaSalle invariance principle, we obtain the result.


## 4. Experimental Simulation

In this section, we provide an example to illustrate the effectiveness of the proposed algorithm. There are 20 states in the multiagent reinforcement learning. We setd=5, regularization parameter ρ=0.1, and discount parameter γ=0.5. There are 4 agents in the connected network in Figure 1. State s is a randomly generated 5-dimensional column vector, the dimension of ϕs is a cosine function, and P is a randomly generated 5-dimensional matrix.Figure 1
Undirected communication network graph.Then, we randomly generate the matricesA^,C^,b^i as follows:(28)A^=0.97970.59490.11740.08550.73030.43890.26220.29670.26250.48860.11110.60280.31880.80100.57850.25810.71120.42420.02920.23730.40870.22170.50790.92890.4588,C^=0.25000.00000.00000.00000.00000.00000.25000.00000.00000.00000.00000.00000.25000.00000.00000.00000.00000.00000.25000.00000.00000.00000.00000.00000.2500,b^1=0.9631,0.5468,0.5211,0.2316,0.4889T,b^2=0.6241,0.6791,0.3955,0.3674,0.9880T,b^3=0.0377,0.8852,0.9133,0.7962,0.0987T,b^4=0.2619,0.3354,0.6797,0.1366,0.7212T.Before the simulation, it is necessary to obtain the solution of the multiagent reinforcement learning:(29)θ∗=−0.0756,0.0211,0.5362,0.0508,0.6956T.We show the comparison about the fractional order algorithm with the conventional integer order one. In Figures2 and 3, the curve illustrates almost the same convergence performance as the conventional integer order when α is 0.995. In Figures 4 and 5, the fractional order algorithm achieves a faster convergent rate than that of the integer order algorithm. Simulation results illustrate the convergence about the integer order and the fractional order. Furthermore, the proposed distributed algorithm with fractional order dynamics has more design freedom to achieve a better performance than that of the conventional first-order algorithm.Figure 2
The trajectory of estimation ofθ1.Figure 3
The trajectory of estimation ofθ2.Figure 4
The trajectory of estimation ofθ1.Figure 5
The trajectory of estimation ofθ2.


## 5. Conclusion

In this paper, the value function problem of the multiagent reinforcement learning was transformed as a distributed optimization problem with a consensus constraint. Then, we proposed a distributed algorithm with fractional order dynamics to solve this problem. Besides, we proved the asymptotic convergence of the algorithm by Lyapunov functions and illustrated the effectiveness of the proposed algorithm with an example. In the future, we will consider applying reinforcement learning to the recommendation system, so as to get better results [23].



---

*Source: 1020466-2021-09-06.xml*