Decentralized Deterministic Multi-Agent Reinforcement Learning
Year: 2020

Abstract:
[Zhang, ICML 2018] provided the first decentralized actor-critic algorithm for 1 multi-agent reinforcement learning (MARL) that offers convergence guarantees. In 2 that work, policies are stochastic and are defined on finite action spaces. We extend 3 those results to offer a provably-convergent decentralized actor-critic algorithm for 4 learning deterministic policies on continuous action spaces. Deterministic policies 5 are important in real-world settings. To handle the lack of exploration inherent in de6 terministic policies, we consider both off-policy and on-policy settings. We provide 7 the expression of a local deterministic policy gradient, decentralized deterministic 8 actor-critic algorithms and convergence guarantees for linearly-approximated value 9 functions. This work will help enable decentralized MARL in high-dimensional 10 action spaces and pave the way for more widespread use of MARL. 11

[Zhang, ICML 2018] provided the first decentralized actor-critic algorithm for1 multi-agent reinforcement learning (MARL) that offers convergence guarantees. In2 that work, policies are stochastic and are defined on finite action spaces. We extend3 those results to offer a provably-convergent decentralized actor-critic algorithm for4 learning deterministic policies on continuous action spaces. Deterministic policies5 are important in real-world settings. To handle the lack of exploration inherent in de-6 terministic policies, we consider both off-policy and on-policy settings. We provide7 the expression of a local deterministic policy gradient, decentralized deterministic8 actor-critic algorithms and convergence guarantees for linearly-approximated value9 functions. This work will help enable decentralized MARL in high-dimensional10 action spaces and pave the way for more widespread use of MARL.11
1 Introduction12
Cooperative multi-agent reinforcement learning (MARL) has seen considerably less use than its13 single-agent analog, in part because often no central agent exists to coordinate the cooperative agents.14 As a result, decentralized architectures have been advocated for MARL. Recently, decentralized15 architectures have been shown to admit convergence guarantees comparable to their centralized16 counterparts under mild network-specific assumptions (see Zhang et al. [2018], Suttle et al. [2019]).17 In this work, we develop a decentralized actor-critic algorithm with deterministic policies for multi-18 agent reinforcement learning. Specifically, we extend results for actor-critic with stochastic policies19 (Bhatnagar et al. [2009], Degris et al. [2012], Maei [2018], Suttle et al. [2019]) to handle deterministic20 policies. Indeed, theoretical and empirical work has shown that deterministic algorithms outperform21 their stochastic counterparts in high-dimensional continuous action settings (Silver et al. [January22 2014b], Lillicrap et al. [2015], Fujimoto et al. [2018]). Deterministic policies further avoid estimating23 the complex integral over the action space. Empirically this allows for lower variance of the critic24 estimates and faster convergence. On the other hand, deterministic policy gradient methods suffer25 from reduced exploration. For this reason, we provide both off-policy and on-policy versions of our26 results, the off-policy version allowing for significant improvements in exploration. The contributions27 of this paper are three-fold: (1) we derive the expression of the gradient in terms of the long-term28 average reward, which is needed in the undiscounted multi-agent setting with deterministic policies;29 (2) we show that the deterministic policy gradient is the limiting case, as policy variance tends to30 zero, of the stochastic policy gradient; and (3) we provide a decentralized deterministic multi-agent31 actor critic algorithm and prove its convergence under linear function approximation.32
Submitted to 34th Conference on Neural Information Processing Systems (NeurIPS 2020). Do not distribute.
2 Background33
Consider a system of N agents denoted by N = [N ] in a decentralized setting. Agents determine34 their decisions independently based on observations of their own rewards. Agents may however com-35 municate via a possibly time-varying communication network, characterized by an undirected graph36 Gt = (N , Et), where Et is the set of communication links connecting the agents at time t ∈ N. The37 networked multi-agent MDP is thus characterized by a tuple (S, { Ai } i∈N , P, { Ri } i∈N , {Gt}t≥0)38 where S is a finite global state space shared by all agents in N , Ai is the action space of agent i, and39 {Gt}t≥0 is a time-varying communication network. In addition, let A = ∏ i∈N Ai denote the joint40 action space of all agents. Then, P : S × A × S → [0, 1] is the state transition probability of the41 MDP, and Ri : S ×A → R is the local reward function of agent i. States and actions are assumed42 globally observable whereas rewards are only locally observable. At time t, each agent i chooses its43 action ait ∈ Ai given state st ∈ S, according to a local parameterized policy πiθi : S ×A
i → [0, 1],44 where πiθi(s, a
i) is the probability of agent i choosing action ai at state s, and θi ∈ Θi ⊆ Rmi is45 the policy parameter. We pack the parameters together as θ = [(θ1)>, · · · , (θN )>]> ∈ Θ where46 Θ = ∏ i∈N Θ i. We denote the joint policy by πθ : S×A → [0, 1] where πθ(s, a) = ∏ i∈N π i θi(s, a
i).47 Note that decisions are decentralized in that rewards are observed locally, policies are evaluated48 locally, and actions are executed locally. We assume that for any i ∈ N , s ∈ S, ai ∈ Ai, the49 policy function πiθi(s, a i) > 0 for any θi ∈ Θi and that πiθi(s, a i) is continuously differentiable with50 respect to the parameters θi over Θi. In addition, for any θ ∈ Θ, let P θ : S × S → [0, 1] denote51 the transition matrix of the Markov chain {st}t≥0 induced by policy πθ, that is, for any s, s′ ∈ S,52 P θ(s′|s) = ∑ a∈A πθ(s, a) · P (s′|s, a). We make the standard assumption that the Markov chain53 {st}t≥0 is irreducible and aperiodic under any πθ and denote its stationary distribution by dθ.54
Our objective is to find a policy πθ that maximizes the long-term average reward over the network.55 Let rit+1 denote the reward received by agent i as a result of taking action a i t. Then, we wish to solve:56
max θ J(πθ) = lim T→∞
1 T E [ T−1∑ t=0 1 N ∑ i∈N rit+1 ] = ∑ s∈S,a∈A dθ(s)πθ(s, a)R̄(s, a),
where R̄(s, a) = (1/N) · ∑ i∈N R
i(s, a) is the globally averaged reward function. Let r̄t =57 (1/N) · ∑ i∈N r i t, then R̄(s, a) = E [r̄t+1|st = s, at = a], and therefore, the global relative action-58
value function is: Qθ(s, a) = ∑ t≥0 E [r̄t+1 − J(θ)|s0 = s, a0 = a, πθ] , and the global relative59
state-value function is: Vθ(s) = ∑ a∈A πθ(s, a)Qθ(s, a). For simplicity, we refer to Vθ and Qθ60 as simply the state-value function and action-value function. We define the advantage function as61 Aθ(s, a) = Qθ(s, a)− Vθ(s).62 Zhang et al. [2018] provided the first provably convergent MARL algorithm in the context of the63 above model. The fundamental result underlying their algorithm is a local policy gradient theorem:64
∇θiJ(µθ) = Es∼dθ,a∼πθ [ ∇θi log πiθi(s, a i) ·Aiθ(s, a) ] ,
where Aiθ(s, a) = Qθ(s, a) − Ṽ iθ (s, a−i) is a local advantage function and Ṽ iθ (s, a−i) =65 ∑ ai∈Ai π i θi(s, a i)Qθ(s, a i, a−i). This theorem has important practical value as it shows that the66 policy gradient with respect to each local parameter θi can be obtained locally using the corresponding67 score function ∇θi log πiθi provided that agent i has an unbiased estimate of the advantage functions68 Aiθ or Aθ. With only local information, the advantage functions A i θ or Aθ cannot be well estimated69
since the estimation requires the rewards { rit } i∈N of all agents. Therefore, they proposed a consensus70 based actor-critic that leverages the communication network to share information between agents71 by placing a weight ct(i, j) on the message transmitted from agent j to agent i at time t. Their72 action-value function Qθ was approximated by a parameterized function Q̂ω : S ×A → R, and each73 agent i maintains its own parameter ωi, which it uses to form a local estimate Q̂ωi of the global Qθ.74 At each time step t, each agent i shares its local parameter ωit with its neighbors on the network, and75 the shared parameters are used to arrive at a consensual estimate of Qθ over time.76
3 Local Gradients of Deterministic Policies77
While the use of a stochastic policy facilitates the derivations of convergence proofs, most real-world78 control tasks require a deterministic policy to be implementable. In addition, the quantities estimated79 in the deterministic critic do not involve estimation of the complex integral over the action space found80 in the stochastic version. This offers lower variance of the critic estimates and faster convergence. To81 address the lack of exploration that comes with deterministic policies, we provide both off-policy82 and on-policy versions of our results. Our first requirement is a local deterministic policy gradient83 theorem.84
We assume that Ai = Rni . We make standard regularity assumptions on our MDP. That is, we85 assume that for any s, s′ ∈ S, P (s′|s, a) and Ri(s, a) are bounded and have bounded first and86 second derivatives. We consider local deterministic policies µiθi : S → A
i with parameter vector87 θi ∈ Θi, and denote the joint policy by µθ : S → A, where µθ(s) = (µ1θ1(s), . . . , µNθN (s)) and88 θ = [(θ1)>, . . . , (θN )>]>. We assume that for any s ∈ S, the deterministic policy function µiθi(s)89 is twice continuously differentiable with respect to the parameter θi over Θi. Let P θ denote the90 transition matrix of the Markov chain {st}t≥0 induced by policy µθ, that is, for any s, s′ ∈ S,91 P θ(s′|s) = P (s′|s, µθ(s)). We assume that the Markov chain {st}t≥0 is irreducible and aperiodic92 under any µθ and denote its stationary distribution by dµθ .93
Our objective is to find a policy µθ that maximizes the long-run average reward:94
max θ J(µθ) = Es∼dµθ [R̄(s, µθ(s))] = ∑ s∈S dµθ (s)R̄(s, µθ(s)).
Analogous to the stochastic policy case, we denote the action-value function by Qθ(s, a) =95 ∑ t≥0 E[r̄t+1 − J(µθ)|s0 = s, a0 = a, µθ], and the state-value function by Vθ(s) = Qθ(s, µθ(s)).96
When there is no ambiguity, we will denote J(µθ) and dµθ by simply J(θ) and dθ, respectively. We97 present three results for the long-run average reward: (1) an expression for the local deterministic98 policy gradient in the on-policy setting ∇θiJ(µθ), (2) an expression for the gradient in the off-policy99 setting, and (3) we show that the deterministic policy gradient can be seen as the limit of the stochastic100 one.101
On-Policy Setting102 Theorem 1 (Local Deterministic Policy Gradient Theorem - On Policy). For any θ ∈ Θ, i ∈ N ,103 ∇θiJ(µθ) exists and is given by104
∇θiJ(µθ) = Es∼dµθ [ ∇θiµiθi(s)∇ai Qθ(s, µ −i θ−i(s), a i) ∣∣ ai=µi
θi (s)
] .
The first step of the proof consists in showing that ∇θJ(µθ) =105 Es∼dθ [ ∇θµθ(s)∇a Qθ(s, a)|a=µθ(s) ] . This is an extension of the well-known stochastic106 case, for which we have∇θJ(πθ) = Es∼dθ [∇θ log(πθ(a|s))Qθ(s, a)], which holds for a long-term107 averaged return with stochastic policy (e.g Theorem 1 of Sutton et al. [2000a]). See the Appendix for108 the details.109
Off-Policy Setting In the off-policy setting, we are given a behavior policy π : S → P(A), and110 our goal is to maximize the long-run average reward under state distribution dπ:111
Jπ(µθ) = Es∼dπ [ R̄(s, µθ(s)) ] = ∑ s∈S dπ(s)R̄(s, µθ(s)). (1)
Note that we consider here an excursion objective (Sutton et al. [2009], Silver et al. [January 2014a],112 Sutton et al. [2016]) since we take the average over the state distribution of the behaviour policy π of113 the state-action reward when selecting action given by the target policy µθ. We thus have:114 Theorem 2 (Local Deterministic Policy Gradient Theorem - Off Policy). For any θ ∈ Θ, i ∈ N ,115 π : S → P(A) a fixed stochastic policy,∇θiJπ(µθ) exists and is given by116
∇θiJπ(µθ) = Es∼dπ [ ∇θiµiθi(s)∇ai R̄(s, µ −i θ−i(s), a i) ∣∣ ai=µi
θi (s)
] .
Proof. Since dπ is independent of θ we can take the gradient on both sides of (1)117 ∇θJπ(µθ) = Es∼dπ [ ∇θµθ(s) ∇aR̄(s, µθ(s)) ∣∣ a=µθ(s) ] .
Given that∇θiµjθ(s) = 0 if i 6= j, we have∇θµθ(s) = Diag(∇θ1µ1θ1(s), . . . ,∇θNµ N θN (s)) and the118 result follows.119
This result implies that, off-policy, each agent needs access to µ−i θ−it (st) for every t .120
Limit Theorem As noted by Silver et al. [January 2014b], the fact that the deterministic gradient121 is a limit case of the stochastic gradient enables the standard machinery of policy gradient, such as122 compatible-function approximation (Sutton et al. [2000b]), natural gradients (Kakade [2001]), on-line123 feature adaptation (Prabuchandran et al. [2016],) and actor-critic (Konda [2002]) to be used with124 deterministic policies. We show that it holds in our setting. The proof can be found in the Appendix.125
Theorem 3 (Limit of the Stochastic Policy Gradient for MARL). Let πθ,σ be a stochastic policy126 such that πθ,σ(a|s) = νσ(µθ(s), a), where σ is a parameter controlling the variance, and νσ satisfy127 Condition 1 in the Appendix. Then,128
lim σ↓0 ∇θJπθ,σ (πθ,σ) = ∇θJµθ (µθ)
where on the l.h.s the gradient is the standard stochastic policy gradient and on the r.h.s. the gradient129 is the deterministic policy gradient.130
4 Algorithms131
We provide two decentralized deterministic actor-critic algorithms, one on-policy and the other132 off-policy and demonstrate their convergence in the next section; assumptions and proofs are provided133 in the Appendix.134
On-Policy Deterministic Actor-Critic135
Algorithm 1 Networked deterministic on-policy actor-critic Initialize: step t = 0; parameters Ĵ i0, ω i 0, ω̃ i 0, θ i 0,∀i ∈ N ; state s0; stepsizes {βω,t}t≥0, {βθ,t}t≥0 Draw ai0 = µ i θi0
(s0) and compute ãi0 = ∇θiµiθi0(s0) Observe joint action a0 = (a10, . . . , a N 0 ) and ã0 = ( ã10, . . . , ã N 0 ) repeat
for i ∈ N do Observe st+1 and reward rit+1 = r i(st, at)
Update Ĵ it+1 ← (1− βω,t) · Ĵ it + βω,t · rit+1 Draw action at+1 = µiθit(st+1) and compute ã i t+1 = ∇θiµiθit(st+1)
end for Observe joint action at+1 = (a1t+1, . . . , a N t+1) and ãt+1 = ( ã1t+1, . . . , ã N t+1 ) for i ∈ N do
Update: δit ← rit+1 − Ĵ it + Q̂ωit(st+1, at+1)− Q̂ωit(st, at) Critic step: ω̃it ← ωit + βω,t · δit · ∇ωQ̂ωi(st, at) ∣∣∣ ω=ωit Actor step: θit+1 = θit + βθ,t · ∇θiµiθit(st) ∇aiQ̂ωit(st, a −i t , a i) ∣∣∣ ai=ait Send ω̃it to the neighbors {j ∈ N : (i, j) ∈ Et} over Gt Consensus step: ωit+1 ← ∑ j∈N c ij t · ω̃ j t
end for Update t← t+ 1
until end
Consider the following on-policy algorithm. The actor step is based on an expression for∇θiJ(µθ)136 in terms of∇aiQθ(see Equation (15) in the Appendix). We approximate the action-value function Qθ137 using a family of functions Q̂ω : S×A → R parameterized by ω, a column vector in RK . Each agent138 i maintains its own parameter ωi and uses Q̂ωi as its local estimate of Qθ. The parameters ωi are139 updated in the critic step using consensus updates through a weight matrix Ct = ( cijt ) i,j ∈ RN×N140 where cijt is the weight on the message transmitted from i to j at time t, namely:141
Ĵ it+1 = (1− βω,t) · Ĵ it + βω,t · rit+1 (2)
ω̃it = ω i t + βω,t · δit · ∇ωQ̂ωi(st, at) ∣∣∣ ω=ωit
(3)
ωit+1 = ∑ j∈N cijt · ω̃ j t (4)
with142 δit = r i t+1 − Ĵ it + Q̂ωit(st+1, at+1)− Q̂ωit(st, at).
For the actor step, each agent i improves its policy via:143
θit+1 = θ i t + βθ,t · ∇θiµiθit(st) · ∇aiQ̂ωit(st, a −i t , a i) ∣∣∣ ai=ait . (5)
Since Algorithm 1 is an on-policy algorithm, each agent updates the critic using only (st, at, st+1), at144 time t knowing that at+1 = µθt(st+1). The terms in blue are additional terms that need to be shared145 when using compatible features (this is explained further in the next section).146
Off-Policy Deterministic Actor-Critic We further propose an off-policy actor-critic algorithm,147 defined in Algorithm 2 to enable better exploration capability. Here, the goal is to maximize148 Jπ(µθ) where π is the behavior policy. To do so, the globally averaged reward function R̄(s, a) is149 approximated using a family of functions ˆ̄Rλ : S ×A → R that are parameterized by λ, a column150 vector in RK . Each agent i maintains its own parameter λi and uses ˆ̄Rλi as its local estimate of R̄.151 Based on (1), the actor update is152
θit+1 = θ i t + βθ,t · ∇θiµiθit(st) · ∇ai ˆ̄Rλit(st, µ −i θ−it (st), a i) ∣∣∣ ai=µ
θit (st)
, (6)
which requires each agent i to have access to µj θjt (st) for j ∈ N .153
The critic update is154
λ̃it = λ i t + βλ,t · δit · ∇λ ˆ̄Rλi(st, at) ∣∣∣ λ=λit
(7)
λit+1 = ∑ j∈N cijt λ̃ j t , (8)
with155 δit = r i(st, at)− ˆ̄Rλit(st, at). (9)
In this case, δit was motivated by distributed optimization results, and is not related to the local156 TD-error (as there is no "temporal" relationship for R). Rather, it is simply the difference between157 the sample reward and the bootstrap estimate. The terms in blue are additional terms that need to be158 shared when using compatible features (this is explained further in the next section).159
5 Convergence160
To show convergence, we use a two-timescale technique where in the actor, updating deterministic161 policy parameter θi occurs more slowly than that of ωi and Ĵ i in the critic. We study the asymptotic162 behaviour of the critic by freezing the joint policy µθ, then study the behaviour of θt under convergence163 of the critic. To ensure stability, projection is often assumed since it is not clear how boundedness of164
Algorithm 2 Networked deterministic off-policy actor-critic
Initialize: step t = 0; parameters λi0, λ̃ i 0, θ i 0,∀i ∈ N ; state s0; stepsizes {βλ,t}t≥0, {βθ,t}t≥0 Draw ai0 ∼ πi(s0) , compute ȧi0 = µiθi0(s0) and ã i 0 = ∇θiµiθi0(s0) Observe joint action a0 = (a10, . . . , a N 0 ), ȧ0 = (ȧ 1 0, . . . , ȧ N 0 ) and ã0 = ( ã10, . . . , ã N 0
) repeat
for i ∈ N do Observe st+1 and reward rit+1 = r
i(st, at) end for for i ∈ N do
Update: δit ← rit+1 − ˆ̄Rλit(st, at) Critic step: λ̃it ← λit + βλ,t · δit · ∇λ ˆ̄Rλi(st, at) ∣∣∣ λ=λit Actor step: θit+1 = θit + βθ,t · ∇θiµiθit(st) · ∇ai ˆ̄Rλit(st, µ −i θ−it (st), a i) ∣∣∣ ai=µ
θit (st)
Send λ̃it to the neighbors {j ∈ N : (i, j) ∈ Et} over Gt end for for i ∈ N do
Consensus step: λit+1 ← ∑ j∈N c ij t · λ̃ j t Draw action at+1 ∼ π(st+1), compute ȧit+1 = µiθit+1(st+1) and compute ã i t+1 =
∇θiµiθit+1(st+1) end for Observe joint action at+1 = (a1t+1, . . . , a N t+1), ȧt+1 = (ȧ 1 t+1, . . . , ȧ N t+1) and ãt+1 =(
ã1t+1, . . . , ã N t+1 ) Update t← t+ 1
until end
{ θit }
can otherwise be ensured (see Bhatnagar et al. [2009]). However, in practice, convergence is165 typically observed even without the projection step (see Bhatnagar et al. [2009], Degris et al. [2012],166 Prabuchandran et al. [2016], Zhang et al. [2018], Suttle et al. [2019]). We also introduce the following167 technical assumptions which will be needed in the statement of the convergence results.168 Assumption 1 (Linear approximation, average-reward). For each agent i, the average-reward function169 R̄ is parameterized by the class of linear functions, i.e., ˆ̄Rλi,θ(s, a) = wθ(s, a) ·λi where wθ(s, a) =170 [ wθ,1(s, a), . . . , wθ,K(s, a) ] ∈ RK is the feature associated with the state-action pair (s, a). The171 feature vectors wθ(s, a), as well as ∇awθ,k(s, a) are uniformly bounded for any s ∈ S, a ∈ A, k ∈172 J1,KK. Furthermore, we assume that the feature matrix Wπ ∈ R|S|×K has full column rank, where173 the k-th column of Wπ,θ is [ ∫ A π(a|s)wθ,k(s, a)da, s ∈ S ] for any k ∈ J1,KK.174 Assumption 2 (Linear approximation, action-value). For each agent i, the action-value function175 is parameterized by the class of linear functions, i.e., Q̂ωi(s, a) = φ(s, a) · ωi where φ(s, a) =176 [ φ1(s, a), . . . , φK(s, a) ] ∈ RK is the feature associated with the state-action pair (s, a). The feature177 vectors φ(s, a), as well as∇aφk(s, a) are uniformly bounded for any s ∈ S , a ∈ A, k ∈ {1, . . . ,K}.178 Furthermore, we assume that for any θ ∈ Θ, the feature matrix Φθ ∈ R|S|×K has full column rank,179 where the k-th column of Φθ is [ φk(s, µθ(s)), s ∈ S ] for any k ∈ J1,KK. Also, for any u ∈ RK ,180 Φθu 6= 1.181 Assumption 3 (Bounding θ). The update of the policy parameter θi includes a local projection by182 Γi : Rmi → Θi that projects any θit onto a compact set Θi that can be expressed as {θi|qij(θi) ≤183 0, j = 1, . . . , si} ⊂ Rmi , for some real-valued, continuously differentiable functions {qij}1≤j≤si184 defined on Rmi . We also assume that Θ = ∏N i=1 Θ
i is large enough to include at least one local185 minimum of J(θ).186
We use {Ft} to denote the filtration with Ft = σ(sτ , Cτ−1, aτ−1, rτ−1, τ ≤ t).187 Assumption 4 (Random matrices). The sequence of non-negative random matrices {Ct = (cijt )ij}188 satisfies:189
1. Ct is row stochastic and E(Ct|Ft) is a.s. column stochastic for each t, i.e., Ct1 = 1 and190 1>E(Ct|Ft) = 1> a.s. Furthermore, there exists a constant η ∈ (0, 1) such that, for any191 cijt > 0, we have c ij t ≥ η.192
2. Ct respects the communication graph Gt, i.e., cijt = 0 if (i, j) /∈ Et.193 3. The spectral norm of E [ C>t · (I − 11 >/N) · Ct ] is smaller than one.194
4. Given the σ-algebra generated by the random variables before time t, Ct, is conditionally195 independent of st, at and rit+1 for any i ∈ N .196
Assumption 5 (Step size rules, on-policy). The stepsizes βω,t, βθ,t satisfy:197 ∑ t βω,t = ∑ t
βθ,t =∞∑ t
(β2ω,t + β 2 θ,t) <∞∑
t
|βθ,t+1 − βθ,t| <∞.
In addition, βθ,t = o(βω,t) and limt→∞βω,t+1/βω,t = 1.198
Assumption 6 (Step size rules, off-policy). The step-sizes βλ,t, βθ,t satisfy:199 ∑ t βλ,t = ∑ t βθ,t =∞, ∑ t β2λ,t + β 2 θ,t <∞
βθ,t = o(βλ,t), lim t→∞ βλ,t+1/βλ,t = 1.
On-Policy Convergence To state convergence of the critic step, we define Dsθ = Diag [ dθ(s), s ∈
S ] , R̄θ = [ R̄(s, µθ(s)), s ∈ S ]> ∈ R|S| and the operator TQθ : R|S| → R|S| for any action-value vector Q ∈ R|S| (and not R|S|·|A| since there is a mapping associating an action to each state) as:
TQθ (Q ′) = R̄θ − J(µθ) · 1 + P θQ′.
Theorem 4. Under Assumptions 3, 4, and 5, for any given deterministic policy µθ, with {Ĵt} and {ωt} generated from (2), we have limt→∞ 1N ∑ i∈N Ĵ i t = J(µθ) and limt→∞ω i t = ωθ a.s. for any i ∈ N , where J(µθ) =
∑ s∈S dθ(s)R̄(s, µθ(s))
is the long-term average return under µθ, and ωθ is the unique solution to200
Φθ >Dsθ [ TQθ (Φθωθ)− Φθωθ ] = 0. (10)
Moreover, ωθ is the minimizer of the Mean Square Projected Bellman Error (MSPBE), i.e., the solution to
minimize ω ‖Φθω −ΠTQθ (Φθω)‖ 2 Dsθ ,
where Π is the operator that projects a vector to the space spanned by the columns of Φθ, and ‖·‖2Dsθ201 denotes the euclidean norm weighted by the matrix Dsθ.202
To state convergence of the actor step, we define quantities ψit,θ, ξ i t and ξ i t,θ as203
ψit,θ = ∇θiµiθi(st) and ψ i t = ψ i t,θt = ∇θiµ i θit (st),
ξit,θ = ∇aiQ̂ωθ (st, a −i t , ai) ∣∣∣ ai=ai=µi
θit
(st) = ∇aiφ(st, a−it , ai) ∣∣ ai=ai=µi
θit
(st) ωθ,
ξit = ∇aiQ̂ωit(st, a −i t , ai) ∣∣∣ ai=µi
θi (st)
= ∇aiφ(st, a−it , ai) ∣∣ ai=µi
θi (st)
ωit.
Additionally, we introduce the operator Γ̂(·) as204
Γ̂i [g(θ)] = lim 0<η→0
Γi [ θi + η · g(θ) ] − θi
η (11)
for any θ ∈ Θ and g : Θ→ Rmi a continuous function. In case the limit above is not unique we take205 Γ̂i [g(θ)] to be the set of all possible limit points of (11).206 Theorem 5. Under Assumptions 2, 3, 4, and 5, the policy parameter θit obtained from (5) converges207 a.s. to a point in the set of asymptotically stable equilibria of208
θ̇i = Γ̂i [ Est∼dθ,µθ [ ψit,θ · ξit,θ ]] , for any i ∈ N . (12)
In the case of multiple limit points, the above is treated as a differential inclusion rather than an209 ODE.210
The convergence of the critic step can be proved by taking similar steps as that in Zhang et al. [2018].211 For the convergence of the actor step, difficulties arise from the projection (which is handled using212 Kushner-Clark Lemma Kushner and Clark [1978]) and the state-dependent noise (that is handled by213 “natural” timescale averaging Crowder [2009]). Details are provided in the Appendix.214 Remark. Note that that with a linear function approximator Qθ, ψt,θ · ξt,θ =215 ∇θµθ(st) ∇aQ̂ωθ (st, a) ∣∣∣ a=µθ(st) may not be an unbiased estimate of∇θJ(θ):216
Es∼dθ [ ψt,θ·ξt,θ ] = ∇θJ(θ)+Es∼dθ [ ∇θµθ(s) · ( ∇aQ̂ωθ (s, a) ∣∣∣ a=µθ(s) − ∇aQωθ (s, a)|a=µθ(s) )] .
A standard approach to overcome this approximation issue is via compatible features (see, for217 example, Silver et al. [January 2014a] and Zhang and Zavlanos [2019]), i.e. φ(s, a) = a · ∇θµθ(s)>,218 giving, for ω ∈ Rm,219
Q̂ω(s, a) = a · ∇θµθ(s)>ω = (a− µθ(s)) · ∇θµθ(s)>ω + V̂ω(s), with V̂ω(s) = Q̂ω(s, µθ(s)) and ∇aQ̂ω(s, a) ∣∣∣ a=µθ(s) = ∇θµθ(s)>ω.
We thus expect that the convergent point of (5) corresponds to a small neighborhood of a local220 optimum of J(µθ), i.e., ∇θiJ(µθ) = 0, provided that the error for the gradient of the action-221 value function ∇aQ̂ω(s, a) ∣∣∣ a=µθ(s) − ∇aQθ(s, a)|a=µθ(s) is small. However, note that using222 compatible features requires computing, at each step t, φ(st, at) = at · ∇θµθ(st)>. Thus, in223 Algorithm 1, each agent observes not only the joint action at+1 = (a1t+1, . . . , a N t+1) but also224
(∇θ1µ1θ1t (st+1), . . . ,∇θNµ N θNt (st+1)) (see the parts in blue in Algorithm 1).225
Off-Policy Convergence226 Theorem 6. Under Assumptions 1, 4, and 6, for any given behavior policy π and any θ ∈ Θ, with227 {λit} generated from (7), we have limt→∞λit = λθ a.s. for any i ∈ N , where λθ is the unique228 solution to229
Bπ,θ · λθ = Aπ,θ · dsπ (13) where dsπ = [ dπ(s), s ∈ S ]> , Aπ,θ = [ ∫ A π(a|s)R̄(s, a)w(s, a) >da, s ∈ S ] ∈ RK×|S| and230
Bπ,θ = [∑ s∈S d π(s) ∫ A π(a|s)wi(s, a) · w(s, a) >da, 1 ≤ i ≤ K ] ∈ RK×K .231
From here on we let232
ξit,θ = ∇ai ˆ̄Rλθ (st, µ −i θ−it (st), ai) ∣∣∣ ai=µi
θit
(st) = ∇aiw(st, µ−iθ−it (st), ai) ∣∣∣ ai=µi
θit
(st) λθ
ξit = ∇ai ˆ̄Rλit(st, µ −i θ−it (st), ai) ∣∣∣ ai=µi
θit
(st) = ∇aiw(st, µ−iθ−i(st), ai) ∣∣ ai=µi θi (st) λit
and we keep233
ψit,θ = ∇θiµiθi(st), and ψ i t = ψ i t,θt = ∇θiµ i θit (st).
Theorem 7. Under Assumptions 1, 3, 4, and 6, the policy parameter θit obtained from (6) converges234 a.s. to a point in the asymptotically stable equilibria of235
θ̇i = Γi [ Es∼dπ [ ψit,θ · ξit,θ ]] . (14)
We define compatible features for the action-value and the average-reward function in an analogous236 manner: wθ(s, a) = (a− µθ(s)) · ∇θµθ(s)>. For λ ∈ Rm,237
ˆ̄Rλ,θ(s, a) = (a− µθ(s)) · ∇θµθ(s)> · λ
∇a ˆ̄Rλ,θ(s, a) = ∇θµθ(s)> · λ
and we have that, for λ∗ = argmin λ
Es∼dπ [ ‖∇a ˆ̄Rλ,θ(s, µθ(s))−∇aR̄(s, µθ(s))‖2 ] :
∇θJπ(µθ) = Es∼dπ [ ∇θµθ(s) · ∇aR̄(s, a) ∣∣ a=µθ(s) ] = Es∼dπ [ ∇θµθ(s) · ∇a ˆ̄Rλ∗,θ(s, a) ∣∣∣ a=µθ(s) ] .
The use of compatible features requires each agent to observe not only the joint action taken238 at+1 = (a 1 t+1, . . . , a N t+1) and the “on-policy action” ȧt+1 = (ȧ 1 t+1, . . . , ȧ N t+1), but also ãt+1 =239
(∇θ1µ1θ1t (st+1), . . . ,∇θNµ N θNt (st+1)) (see the parts in blue in Algorithm 2).240
We illustrate algorithm convergence on multi-agent extension of a continuous bandit problem from241 Sec. 5.1 of Silver et al. [January 2014b]. Details are in the Appendix. Figure 2 shows the convergence242 of Algorithms 1 and 2 averaged over 5 runs. In all cases, the system converges and the agents are243 able to coordinate their actions to minimize system cost.
244
6 Conclusion245
We have provided the tools needed to implement decentralized, deterministic actor-critic algorithms246 for cooperative multi-agent reinforcement learning. We provide the expressions for the policy247 gradients, the algorithms themselves, and prove their convergence in on-policy and off-policy settings.248 We also provide numerical results for a continuous multi-agent bandit problem that demonstrates249 the convergence of our algorithms. Our work differs from Zhang and Zavlanos [2019] as the latter250 was based on policy consensus whereas ours is based on critic consensus. Our approach represents251 agreement between agents on every participants’ contributions to the global reward, and as such,252 provides a consensus scoring function with which to evaluate agents. Our approach may be used253 in compensation schemes to incentivize participation. An interesting extension of this work would254 be to prove convergence of our actor-critic algorithm for continuous state spaces, as it may hold255 with assumptions on the geometric ergodicity of the stationary state distribution induced by the256 deterministic policies (see Crowder [2009]). The expected policy gradient (EPG) of Ciosek and257 Whiteson [2018], a hybrid between stochastic and deterministic policy gradient, would also be258 interesting to leverage. The Multi-Agent Deep Deterministic Policy Gradient algorithm (MADDPG)259 of Lowe et al. [2017] assumes partial observability for each agent and would be a useful extension,260 but it is likely difficult to extend our convergence guarantees to the partially observed setting.261
References262 Albert Benveniste, Pierre Priouret, and Michel Métivier. Adaptive Algorithms and Stochastic263 Approximations. Springer-Verlag, Berlin, Heidelberg, 1990. ISBN 0-387-52894-6.264
Shalabh Bhatnagar, Richard S. Sutton, Mohammad Ghavamzadeh, and Mark Lee. Natural actor-critic265 algorithms. Automatica, 45(11):2471–2482, November 2009. ISSN 0005-1098. doi: 10.1016/j.266 automatica.2009.07.008. URL http://dx.doi.org/10.1016/j.automatica.2009.07.008.267
Kamil Ciosek and Shimon Whiteson. Expected Policy Gradients for Reinforcement Learning. arXiv268 e-prints, art. arXiv:1801.03326, Jan 2018.269
Martin Crowder. Stochastic approximation: A dynamical systems viewpoint by vivek s. borkar.270 International Statistical Review, 77(2):306–306, 2009.271
Thomas Degris, Martha White, and Richard S. Sutton. Off-policy actor-critic. CoRR, abs/1205.4839,272 2012. URL http://arxiv.org/abs/1205.4839.273
Scott Fujimoto, Herke van Hoof, and Dave Meger. Addressing function approximation error in actor-274 critic methods. CoRR, abs/1802.09477, 2018. URL http://arxiv.org/abs/1802.09477.275
Sham Kakade. A natural policy gradient. In Proceedings of the 14th International Conference on276 Neural Information Processing Systems: Natural and Synthetic, NIPS’01, pages 1531–1538, Cam-277 bridge, MA, USA, 2001. MIT Press. URL http://dl.acm.org/citation.cfm?id=2980539.278 2980738.279
Vijaymohan Konda. Actor-critic Algorithms. PhD thesis, Cambridge, MA, USA, 2002. AAI0804543.280
Harold J. (Harold Joseph) Kushner and (joint author.) Clark, Dean S. Stochastic approximation281 methods for constrained and unconstrained systems. New York : Springer-Verlag, 1978. ISBN282 0387903410.283
Timothy P. Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Manfred Otto Heess, Tom Erez,284 Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement285 learning. CoRR, abs/1509.02971, 2015.286
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor-287 critic for mixed cooperative-competitive environments. Neural Information Processing Systems288 (NIPS), 2017.289
Hamid Reza Maei. Convergent actor-critic algorithms under off-policy training and function approxi-290 mation. CoRR, abs/1802.07842, 2018. URL http://arxiv.org/abs/1802.07842.291
P. Marbach and J. N. Tsitsiklis. Simulation-based optimization of markov reward processes. IEEE292 Transactions on Automatic Control, 46(2):191–209, Feb 2001. ISSN 0018-9286. doi: 10.1109/9.293 905687.294
K. J. Prabuchandran, Shalabh Bhatnagar, and Vivek S. Borkar. Actor-critic algorithms with online295 feature adaptation. ACM Trans. Model. Comput. Simul., 26(4):24:1–24:26, February 2016. ISSN296 1049-3301. doi: 10.1145/2868723. URL http://doi.acm.org/10.1145/2868723.297
Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John298 Wiley & Sons, Inc., New York, NY, USA, 1st edition, 1994. ISBN 0471619779.299
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller.300 Deterministic Policy Gradient Algorithms. International Conference on Machine Learning, pages301 387–395, January 2014a.302
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller.303 Deterministic Policy Gradient Algorithms. International Conference on Machine Learning, pages304 387–395, January 2014b.305
Wesley Suttle, Zhuoran Yang, Kaiqing Zhang, Zhaoran Wang, Tamer Basar, and Ji Liu. A multi-agent306 off-policy actor-critic algorithm for distributed reinforcement learning. CoRR, abs/1903.06372,307 2019. URL http://arxiv.org/abs/1903.06372.308
Richard S Sutton, David A. McAllester, Satinder P. Singh, and Yishay Mansour. Policy gradient309 methods for reinforcement learning with function approximation. In S. A. Solla, T. K. Leen, and310 K. Müller, editors, Advances in Neural Information Processing Systems 12, pages 1057–1063. MIT311 Press, 2000a.312
Richard S Sutton, David A. McAllester, Satinder P. Singh, and Yishay Mansour. Policy gradient313 methods for reinforcement learning with function approximation. In S. A. Solla, T. K. Leen, and314 K. Müller, editors, Advances in Neural Information Processing Systems 12, pages 1057–1063. MIT315 Press, 2000b.316
Richard S. Sutton, Hamid Reza Maei, Doina Precup, Shalabh Bhatnagar, David Silver, Csaba317 Szepesvári, and Eric Wiewiora. Fast gradient-descent methods for temporal-difference learning318 with linear function approximation. In Proceedings of the 26th Annual International Conference319 on Machine Learning, ICML ’09, pages 993–1000, New York, NY, USA, 2009. ACM. ISBN320 978-1-60558-516-1.321
Richard S. Sutton, A. Rupam Mahmood, and Martha White. An emphatic approach to the problem322 of off-policy temporal-difference learning. J. Mach. Learn. Res., 17(1):2603–2631, January 2016.323 ISSN 1532-4435. URL http://dl.acm.org/citation.cfm?id=2946645.3007026.324
Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Basar. Fully decentralized multi-325 agent reinforcement learning with networked agents. 80:5872–5881, 10–15 Jul 2018.326
Yan Zhang and Michael M. Zavlanos. Distributed off-policy actor-critic reinforcement learning with327 policy consensus. CoRR, abs/1903.09255, 2019.328
Numerical experiment details329
We demonstrate the convergence of our algorithm in a continuous bandit problem that is a multi-330 agent extension of the experiment in Section 5.1 of Silver et al. (2014). Each agent chooses331 an action ai ∈ Rm. We assume all agents have the same reward function given by Ri(a) =332 − (∑
i a i − a∗
)T C (∑
i a i − a∗
) . The matrix C is positive definite with eigenvalues chosen from333 {0.1, 1}, and a∗ = [4, . . . , 4]T. We consider 10 agents and action dimensions m = 10, 20, 50. Note334 that there are multiple possible solutions for this problem, requiring the agents to coordinate their335 actions to sum to a∗. We assume a target policy of the form µθi = θi for each agent i and a Gaussian336 behaviour policy β(·) ∼ N (θi, σ2β) where σβ = 0.1. We use the Gaussian behaviour policy for both337 Algorithms 1 and 2. Strictly speaking, Algorithm 1 is on-policy, but in this simplified setting where338 the target policy is constant, the on-policy version would be degenerate such that the Q estimate does339 not affect the TD-error. Therefore, we add a Gaussian behaviour policy to Algorithm 1. Each agent340 maintains an estimate Qω i
(a) of the critic using a linear function of the compatible features a− θ341 and a bias feature. The critic is recomputed from each successive batch of 2m steps and the actor342 is updated once per batch. The critic step size is 0.1 and the actor step size is 0.01. Performance343 is evaluated by measuring the cost of the target policy (without exploration). Figure 2 shows the344 convergence of Algorithms 1 and 2 averaged over 5 runs. In all cases, the system converges and the345 agents are able to coordinate their actions to minimize system cost. The jupyter notebook will be346 made available for others to use. In fact, in this simple experiment, we also observe convergence347 under discounted rewards.348
Proof of Theorem 1349
The proof follows the same scheme as Sutton et al. [2000a], naturally extending their results for a350 deterministic policy µθ and a continuous action space A.351 Note that our regularity assumptions ensure that, for any s ∈ S, Vθ(s), ∇θVθ(s), J(θ), ∇θJ(θ),352 dθ(s) are Lipschitz-continuous functions of θ (since µθ is twice continuously differentiable and Θ is353 compact), and that Qθ(s, a) and ∇aQθ(s, a) are Lipschitz-continuous functions of a (Marbach and354 Tsitsiklis [2001]).355
We first show that∇θJ(θ) = Es∼dθ [ ∇θµθ(s)∇a Qθ(s, a)|a=µθ(s)].356
The Poisson equation under policy µθ is given by Puterman [1994]357
Qθ(s, a) = R̄(s, a)− J(θ) + ∑ s′∈S P (s′|s, a)Vθ(s′).
So,358
∇θVθ(s) = ∇θQθ(s, µθ(s)) = ∇θ [ R̄(s, µθ(s))− J(θ) + ∑ s′∈S P (s′|s, µθ(s))Vθ(s′) ]
= ∇θµθ(s) ∇aR̄(s, a) ∣∣ a=µθ(s) −∇θJ(θ) +∇θ ∑ s′∈S P (s′|s, µθ(s))Vθ(s′)
= ∇θµθ(s) ∇aR̄(s, a) ∣∣ a=µθ(s) −∇θJ(θ)
+ ∑ s′∈S ∇θµθ(s) ∇aP (s′|s, a)|a=µθ(s) Vθ(s ′) + ∑ s′∈S P (s′|s, µθ(s))∇θVθ(s′)
= ∇θµθ(s)∇a [ R̄(s, a) + ∑ s′∈S P (s|s′, a)Vθ(s′) ]∣∣∣∣∣ a=µθ(s)
−∇θJ(θ) + ∑ s′∈S P (s′|s, µθ(s))∇θVθ(s′)
= ∇θµθ(s)∇a Qθ(s, a)|a=µθ(s) + ∑ s′∈S P (s′|s, µθ(s))∇θVθ(s′)−∇θJ(θ)
Hence,359
∇θJ(θ) = ∇θµθ(s)∇a Qθ(s, a)|a=µθ(s) + ∑ s′∈S
P (s′|s, µθ(s))∇θVθ(s′)−∇θVθ(s)∑ s∈S dθ(s)∇θJ(θ) = ∑ s∈S dθ(s)∇θµθ(s)∇a Qθ(s, a)|a=µθ(s)
+ ∑ s∈S dθ(s) ∑ s′∈S P (s′|s, µθ(s))∇θVθ(s′)− ∑ s∈S dθ(s)∇θVθ(s).
Using stationarity property of dθ, we get∑ s∈S ∑ s′∈S dθ(s)P (s′|s, µθ(s))∇θVθ(s′) = ∑ s′∈S dθ(s′)∇θVθ(s′).
Therefore, we get ∇θJ(θ) = ∑ s∈S dθ(s)∇θµθ(s) ∇aQθ(s, a)|a=µθ(s) = Es∼dθ [ ∇θµθ(s) ∇aQθ(s, a)|a=µθ(s)].
Given that ∇θiµjθ(s) = 0 if i 6= j, we have ∇θµθ(s) = Diag(∇θ1µ1θ1(s), . . . ,∇θNµ N θN (s)), which360 implies361
∇θiJ(θ) = Es∼dθ [ ∇θiµiθi(s)∇ai Qθ(s, µ −i θ−i(s), a i) ∣∣ ai=µi
θi (s)
]. (15)
Proof of Theorem 3362
We extend the notation for off-policy reward function to stochastic policies as follows. Let β be a363 behavior policy under which {st}t≥0 is irreducible and aperiodic, with stationary distribution dβ . For364 a stochastic policy π : S → P(A), we define365
Jβ(π) = ∑ s∈S dβ(s) ∫ A π(a|s)R̄(s, a)da.
Recall that for a deterministic policy µ : S → A, we have366 Jβ(µ) = ∑ s∈S dβ(s)R̄(s, µ(s)).
We introduce the following conditions which are identical to Conditions B1 from Silver et al.367 [January 2014a].368
Conditions 1. Functions νσ parametrized by σ are said to be regular delta-approximation onR ⊂ A369 if they satisfy the following conditions:370
1. The distributions νσ converge to a delta distribution: limσ↓0 ∫ A νσ(a
′, a)f(a)da = f(a′)371 for a′ ∈ R and suitably smooth f . Specifically we require that this convergence is uniform372 in a′ and over any class F of L-Lipschitz and bounded functions, ‖∇af(a)‖< L < ∞,373 supaf(a) < b <∞, i.e.:374
lim σ↓0 sup f∈F,a′∈R ∣∣∣∣∫ A νσ(a ′, a)f(a)da− f(a′) ∣∣∣∣ = 0.
2. For each a′ ∈ R, νσ(a′, ·) is supported on some compact Ca′ ⊆ A with Lipschitz boundary375 bd(Ca′), vanishes on the boundary and is continuously differentiable on Ca′ .376
3. For each a′ ∈ R, for each a ∈ A, the gradient∇a′νσ(a′, a) exists.377
4. Translation invariance: for all a ∈ A, a′ ∈ R, and any δ ∈ Rn such that a + δ ∈ A,378 a′ + δ ∈ A, νσ(a′, a) = νσ(a′ + δ, a+ δ).379
The following lemma is an immediate corollary of Lemma 1 from Silver et al. [January 2014a].380 Lemma 1. Let νσ be a regular delta-approximation onR ⊆ A. Then, wherever the gradients exist
∇a′ν(a′, a) = −∇aν(a′, a).
Theorem 3 is a less technical restatement of the following result.381 Theorem 8. Let µθ : S → A. Denote the range of µθ by Rθ ⊆ A, and R = ∪θRθ. For382 each θ, consider πθ,σ a stochastic policy such that πθ,σ(a|s) = νσ(µθ(s), a), where νσ satisfy383 Conditions 1 on R. Then, there exists r > 0 such that, for each θ ∈ Θ, σ 7→ Jπθ,σ (πθ,σ),384 σ 7→ Jπθ,σ (µθ), σ 7→ ∇θJπθ,σ (πθ,σ), and σ 7→ ∇θJπθ,σ (µθ) are properly defined on [ 0, r ]
(with385 Jπθ,0(πθ,0) = Jπθ,0(µθ) = Jµθ (µθ) and ∇θJπθ,0(πθ,0) = ∇θJπθ,0(µθ) = ∇θJµθ (µθ)), and we386 have:387
lim σ↓0 ∇θJπθ,σ (πθ,σ) = lim σ↓0 ∇θJπθ,σ (µθ) = ∇θJµθ (µθ).
To prove this result, we first state and prove the following Lemma.388 Lemma 2. There exists r > 0 such that, for all θ ∈ Θ and σ ∈ [ 0, r ] , stationary distribution dπθ,σ389
exists and is unique. Moreover, for each θ ∈ Θ, σ 7→ dπθ,σ and σ 7→ ∇θdπθ,σ are properly defined390 on [ 0, r ] and both are continuous at 0.391
Proof of Lemma 2. For any policy β, we let ( P βs,s′ ) s,s′∈S be the transition matrix associated to the392 Markov Chain {st}t≥0 induced by β. In particular, for each θ ∈ Θ, σ > 0, s, s′ ∈ S, we have393 Pµθs,s′ = P (s ′|s, µθ(s)),
P πθ,σ s,s′ = ∫ A πθ,σ(a|s)P (s′|s, a)da = ∫ A νσ(µθ(s), a)P (s ′|s, a)da.
Let θ ∈ Θ, s, s′ ∈ S, (θn) ∈ ΘN such that θn → θ and (σn)n∈N ∈ R+ N, σn ↓ 0:394 ∣∣∣Pπθn,σns,s′ − Pµθs,s′ ∣∣∣ ≤ ∣∣∣Pπθn,σns,s′ − Pµθns,s′ ∣∣∣+ ∣∣∣Pµθns,s′ − Pµθs,s′ ∣∣∣ .
Applying the first condition of Conditions 1 with f : a 7→ P (s′|s, a) belonging to F :395 ∣∣∣Pπθn,σns,s′ − Pµθns,s′ ∣∣∣ = ∣∣∣∣∫ A νσn(µθn(s), a)P (s ′|s, a)da− P (s′|s, µθn(s)) ∣∣∣∣
≤ sup f∈F,a′∈R ∣∣∣∣∫ A νσn(a ′, a)f(a)da− f(a′) ∣∣∣∣ −→n→∞ 0.
By regularity assumptions on θ 7→ µθ(s) and P (s′|s, ·), we have396 ∣∣∣Pµθns,s′ − Pµθs,s′ ∣∣∣ = |P (s′|s, µθn(s))− P (s′|s, µθ(s))| −→n→∞ 0.
Hence,397 ∣∣∣Pπθn,σns,s′ − Pµθs,s′ ∣∣∣ −→n→∞ 0. Therefore, for each s, s′ ∈ S, (θ, σ) 7→ Pπθ,σs,s′ , with P πθ,0 s,s′ = P µθ s,s′ , is continuous on Θ× {0}. Note398
that, for each n ∈ N, P 7→ ∏ s,s′ (P
n)s,s′ is a polynomial function of the entries of P . Thus, for399 each n ∈ N, fn : (θ, σ) 7→ ∏ s,s′ (P πθ,σn)s,s′ , with fn(θ, 0) = ∏ s,s′ (P
µθn)s,s′ is continuous on400 Θ × {0}. Moreover, for each θ ∈ Θ, σ ≥ 0, from the structure of Pπθ,σ , if there is some n∗ ∈ N401 such that fn∗(θ, σ) > 0 then, for all n ≥ n∗, fn(θ, σ) > 0.402
Now let us suppose that there exists (θn) ∈ ΘN ∗ such that, for each n > 0 there is a σn ≤ n−1 such403 that fn(θn, σn) = 0. By compacity of Θ, we can take (θn) converging to some θ ∈ Θ. For each404 n∗ ∈ N, by continuity we have fn∗(θ, 0) = lim
n→∞ fn∗(θn, σn) = 0. Since Pµθ is irreducible and405 aperiodic, there is some n ∈ N such that for all s, s′ ∈ S and for all n∗ ≥ n, ( Pµθn ∗ ) s,s′ > 0, i.e.406 fn∗(θ, 0) > 0. This leads to a contradiction.407
Hence, there exists n∗ > 0 such that for all θ ∈ Θ and σ ≤ n∗−1, fn(θ, σ) > 0. We let r = n∗−1. It408 follows that, for all θ ∈ Θ and σ ∈ [ 0, r ] , Pπθ,σ is a transition matrix associated to an irreducible and409 aperiodic Markov Chain, thus dπθ,σ is well defined as the unique stationary probability distribution410 associated to Pπθ,σ . We fix θ ∈ Θ in the remaining of the proof.411
Let β a policy for which the Markov Chain corresponding to P β is irreducible and aperiodic. Let412 s∗ ∈ S, as asserted in Marbach and Tsitsiklis [2001], considering stationary distribution dβ as a413 vector ( dβs ) s∈S ∈ R
|S|, dβ is the unique solution of the balance equations:414 ∑ s∈S dβsP β s,s′ = d β s′ s
′ ∈ S\{s∗},∑ s∈S dβs = 1.
Hence, we have Aβ an |S| × |S| matrix and a 6= 0 a constant vector of R|S| such that the balance415 equations is of the form416
Aβdβ = a (16)
with Aβs,s′ depending on P β s′,s in an affine way, for each s, s ′ ∈ S. Moreover, Aβ is invertible, thus417 dβ is given by418
dβ = 1
det(Aβ) adj(Aβ)>a.
Entries of adj(Aβ) and det(Aβ) are polynomial functions of the entries of P β .419
Thus, σ 7→ dπθ,σ = 1 det(Aπθ,σ )
adj(Aπθ,σ )>a is defined on [ 0, r ] and is continuous at 0.420
Lemma 1 and integration by parts imply that, for s, s′ ∈ S, σ ∈ [ 0, r ] :421 ∫
A ∇a′νσ(a′, a)|a′=µθ(s) P (s ′|s, a)da = − ∫ A ∇aνσ(µθ(s), a)P (s′|s, a)da
= ∫ Cµθ(s) νσ(µθ(s), a)∇aP (s′|s, a)da+ boundary terms
= ∫ Cµθ(s) νσ(µθ(s), a)∇aP (s′|s, a)da
where the boundary terms are zero since νσ vanishes on the boundary due to Conditions 1.422
Thus, for s, s′ ∈ S, σ ∈ [ 0, r ] :423
∇θP πθ,σ s,s′ = ∇θ ∫ A πθ,σ(a|s)P (s′|s, a)da
= ∫ A ∇θπθ,σ(a|s)P (s′|s, a)da (17)
= ∫ A ∇θµθ(s) ∇a′νσ(a′, a)|a′=µθ(s) P (s ′|s, a)da
= ∇θµθ(s) ∫ Cµθ(s) νσ(µθ(s), a)∇aP (s′|s, a)da
where exchange of derivation and integral in (17) follows by application of Leibniz rule with:424
• ∀a ∈ A, θ 7→ πθ,σ(a|s)P (s′|s, a) is differentiable, and ∇θπθ,σ(a|s)P (s′|s, a) =425 ∇θµθ(s) ∇a′νσ(a′, a)|a′=µθ(s).426 427
• Let a∗ ∈ R, ∀θ ∈ Θ,428 ‖∇θπθ,σ(a|s)P (s′|s, a)‖ = ∥∥∥∇θµθ(s) ∇a′νσ(a′, a)|a′=µθ(s)∥∥∥
≤ ‖∇θµθ(s)‖op ∥∥∥∇a′νσ(a′, a)|a′=µθ(s)∥∥∥
≤ sup θ∈Θ ‖∇θµθ(s)‖op ‖∇aνσ(µθ(s), a)‖
= sup θ∈Θ ‖∇θµθ(s)‖op ‖∇aνσ(a ∗, a− µθ(s) + a∗)‖ (18)
≤ sup θ∈Θ ‖∇θµθ(s)‖op sup a∈Ca∗ ‖∇aνσ(a∗, a)‖ 1a∈Ca∗
where ‖·‖op denotes the operator norm, and (18) comes from translation invariance (we take429 ∇aνσ(a∗, a) = 0 for a ∈ Rn\Ca∗ ). a 7→ sup
θ∈Θ ‖∇θµθ(s)‖op sup a∈Ca∗ ‖∇aνσ(a∗, a)‖ 1a∈Ca∗ is430 measurable, bounded and supported on Ca∗ , so it is integrable on A.431 • Dominated convergence ensures that, for each k ∈ J1,mK, partial derivative gk(θ) =432 ∂θk ∫ A∇θπθ,σ(a|s)P (s ′|s, a)da is continuous: let θn ↓ θ, then433
gk(θn) = ∂θk ∫ A ∇θπθn,σ(a|s)P (s′|s, a)da
= ∂θkµθn(s) ∫ Ca∗ νσ(a ∗, a− µθn(s) + a∗)∇aP (s′|s, a)da
−→ n→∞ ∂θkµθ(s) ∫ Ca∗ νσ(a ∗, a− µθ(s) + a∗)∇aP (s′|s, a)da = gk(θ)
with the dominating function a 7→ sup a∈Ca∗ |νσ(a∗, a)|sup a∈A ‖∇aP (s′|s, a)‖ 1a∈Ca∗ .434
Thus σ 7→ ∇θP πθ,σ s,s′ is defined for σ ∈
[ 0, r ]
and is continuous at 0, with ∇θP πθ,0 s,s′ =435 ∇θµθ(s) ∇aP (s′|s, a)|a=µθ(s). Indeed, let (σn)n∈N ∈ [ 0, r ]+N
, σn ↓ 0, then, applying the first436 condition of Conditions 1 with f : a 7→ ∇aP (s′|s, a) belonging to F , we get437 ∥∥∥∇θPπθ,σns,s′ −∇θPµθs,s′∥∥∥
= ‖∇θµθ(s)‖op ∥∥∥∥∥ ∫ Cµθ(s) νσn(µθ(s), a)∇aP (s′|s, a)da− ∇aP (s′|s, a)|a=µθ(s) ∥∥∥∥∥ −→n→∞ 0. Since dπθ,σ = 1
det(Aπθ,σ ) adj (Aπθ,σ )> a with |det (Aπθ,σ ) | > 0 for all σ ∈
[ 0, r ]
and since entries438 of adj (Aπθ,σ ) and det (Aπθ,σ ) are polynomial functions of the entries of Pπθ,σ , it follows that439
σ 7→ ∇θdπθ,σ is properly defined on [ 0, r ]
and is continuous at 0, which concludes the proof of440 Lemma 2.441
We now proceed to prove Theorem 8.442 Let θ ∈ Θ, πθ as in Theorem 3, and r > 0 such that σ 7→ dπθ,σ , σ 7→ ∇θdπθ,σ are well defined on443 [ 0, r ] and are continuous at 0. Then, the following two functions444
σ 7→ Jπθ,σ (πθ,σ) = ∑ s∈S dπθ,σ (s) ∫ A πθ,σ(a|s)R̄(s, a)da,
σ 7→ Jπθ,σ (µθ) = ∑ s∈S dπθ,σ (s)R̄(s, µθ(s)),
are properly defined on [ 0, r ]
(with Jπθ,0(πθ,0) = Jπθ,0(µθ) = Jµθ (µθ)). Let s ∈ S, by taking445 similar arguments as in the proof of Lemma 2, we have446
∇θ ∫ A πθ,σ(a|s)R̄(s, a)da = ∫ A ∇θπθ,σ(a, s)R̄(s, a)da,
= ∇θµθ(s) ∫ Cµθ(s) νσ(µθ(s), a)∇aR̄(s, a)da.
Thus, σ 7→ ∇θJπθ,σ (πθ,σ) is properly defined on [ 0, r ] and447
∇θJπθ,σ (πθ,σ) = ∑ s∈S ∇θdπθ,σ (s) ∫ A πθ,σ(a|s)R̄(s, a)da
+ ∑ s∈S dπθ,σ (s)∇θ ∫ A πθ,σ(a|s)R̄(s, a)da
= ∑ s∈S ∇θdπθ,σ (s) ∫ A νσ(µθ(s), a)R̄(s, a)da
+ ∑ s∈S dπθ,σ (s)∇θµθ(s) ∫ Cµθ(s) νσ(µθ(s), a)∇aR̄(s, a)da.
Similarly, σ 7→ ∇θJπθ,σ (µθ) is properly defined on [ 0, r ] and448
∇θJπθ,σ (µθ) = ∑ s∈S ∇θdπθ,σ (s)R̄(s, µθ(s)) + ∑ s∈S dπθ,σ (s)∇θµθ(s) ∇aR̄(s, a) ∣∣ a=µθ(s)
To prove continuity at 0 of both σ 7→ ∇θJπθ,σ (πθ,σ) and σ 7→ ∇θJπθ,σ (µθ) (with ∇θJπθ,0(πθ,0) =449 ∇θJπθ,0(µθ) = ∇θJµθ (µθ)), let (σn)n≥0 ↓ 0:450
∥∥∇θJπθ,σn (πθ,σn)−∇θJπθ,0(πθ,0)∥∥ ≤ ∥∥∇θJπθ,σn (πθ,σn)−∇θJπθ,σn (µθ)∥∥+ ∥∥∇θJπθ,σn (µθ)−∇θJµθ (µθ)∥∥ . (19)
For the first term of the r.h.s we have451
∥∥∇θJπθ,σn (πθ,σn)−∇θJπθ,σn (µθ)∥∥ ≤ ∑ s∈S ‖∇θdπθ,σn (s)‖ ∣∣∣∣∫ A νσn(µθ(s), a)R̄(s, a)da− R̄(s, µθ(s))
∣∣∣∣ + ∑ s∈S dπθ,σn (s)‖∇θµθ(s)‖op ∥∥∥∥∫ A νσn(µθ(s), a)∇aR̄(s, a)da− ∇aR̄(s, a) ∣∣ a=µθ(s) ∥∥∥∥ .
Applying the first assumption in Condition 1 with f : a 7→ R̄(s, a) and f : a 7→ ∇aR̄(s, a) belonging452 to F we have, for each s ∈ S:453 ∣∣∣∣∫
A νσn(µθ(s), a)R̄(s, a)da− R̄(s, µθ(s)) ∣∣∣∣ −→n→∞ 0 and∥∥∥∥∫ A νσn(µθ(s), a)∇aR̄(s, a)da− ∇aR̄(s, a) ∣∣ a=µθ(s)
∥∥∥∥ −→n→∞ 0. Moreover, for each s ∈ S, dπθ,σn (s) −→
n→∞ dµθ (s) and∇θdπθ,σn (s) −→ n→∞ ∇θdµθ (s) (by Lemma 2),454 and ‖∇θµθ(s)‖op<∞, so455 ∥∥∇θJπθ,σn (πθ,σn)−∇θJπθ,σn (µθ)∥∥ −→n→∞ 0. For the second term of the r.h.s of (19), we have456 ∥∥∇θJπθ,σn (µθ)−∇θJµθ (µθ)∥∥ ≤∑
s∈S ‖∇θdπθ,σn (s)−∇θdµθ (s)‖ ∣∣R̄(s, µθ(s))∣∣ + ∑ s∈S |dπθ,σn (s)− dµθ (s)| ‖∇θµθ(s)‖op
∥∥∥∇aR̄(s, a)∣∣a=µθ(s)∥∥∥ . Continuity at 0 of σ 7→ dπθ,σ (s) and σ 7→ ∇θdπθ,σ (s) for each s ∈ S, boundedness of R̄(s, ·),457 ∇aR̄(s, ·) and ∇θ(s)µθ(s) implies that458 ∥∥∇θJπθ,σn (µθ)−∇θJµθ (µθ)∥∥ −→n→∞ 0. Hence,459 ∥∥∇θJπθ,σn (πθ,σn)−∇θJπθ,0(πθ,0)∥∥ −→n→∞ 0. So, σ 7→ ∇θJπθ,σ (πθ,σ) and ∇θJπθ,σ (µθ) are continuous at 0:460
lim σ↓0 ∇θJπθ,σ (πθ,σ) = lim σ↓0 ∇θJπθ,σ (µθ) = ∇θJµθ (µθ).
Proof of Theorem 4461
We will use the two-time-scale stochastic approximation analysis . We let the policy parameter θt462 fixed as θt ≡ θ when analysing the convergence of the critic step. Thus we can show the convergence463 of ωt towards an ωθ depending on θ, which will then be used to prove the convergence for the slow464 time-scale.465 Lemma 3. Under Assumptions 3 – 5, the sequence ωit generated from (2) is bounded a.s., i.e.,466 supt‖ωit‖<∞ a.s., for any i ∈ N .467
The proof follows the same steps as that of Lemma B.1 in the PMLR version of Zhang et al. [2018].468
Lemma 4. Under Assumption 5, the sequence {Ĵ it} generated as in 2 is bounded a.s, i.e., supt|Ĵ it | <469 ∞ a.s., for any i ∈ N .470
The proof follows the same steps as that of Lemma B.2 in the PMLR version of Zhang et al. [2018].471
The desired result holds since Step 1 and Step 2 of the proof of Theorem 4.6 in Zhang et al. [2018]472 can both be repeated in the setting of deterministic policies.473
Proof of Theorem 5474
Let Ft,2 = σ(θτ , sτ , τ ≤ t) a filtration. In addition, we define475
H(θ, s, ω) = ∇θµθ(s) · ∇aQω(s, a)|a=µθ(s) , H(θ, s) = H(θ, s, ωθ),
h(θ) = Es∼dθ [H(θ, s)] .
Then, for each θ ∈ Θ, we can introduce νθ : S → Rn the solution to the Poisson equation:476 ( I − P θ ) νθ(·) = H(θ, ·)− h(θ)
that is given by νθ(s) = ∑ k≥0 Esk+1∼P θ(·|sk) [H(θ, sk)− h(θ)|s0 = s] which is properly defined477 (similar to the differential value function V ).478
With projection, actor update (5) becomes479 θt+1 = Γ [θt + βθ,tH(θt, st, ωt)] (20)
= Γ [θt + βθ,th(θt)− βθ,t (h(θt)−H(θt, st))− βθ,t (H(θt, st)−H(θt, st, ωt))] = Γ [ θt + βθ,th(θt) + βθ,t ( (I − P θt)νθt(st) ) + βθ,tA 1 t ] = Γ [ θt + βθ,th(θt) + βθ,t (νθt(st)− νθt(st+1)) + βθ,t ( νθt(st+1)− P θtνθt(st) ) + βθ,tA 1 t
] = Γ [ θt + βθ,t ( h(θt) +A 1 t +A 2 t +A 3 t
)] where480
A1t = H(θt, st, ωt)−H(θt, st), A2t = νθt(st)− νθt(st+1), A3t = νθt(st+1)− P θtνθt(st).
For r < t we have481 t−1∑ k=r βθ,kA 2 k = t−1∑ k=r βθ,k (νθk(sk)− νθk(sk+1))
= t−1∑ k=r βθ,k ( νθk(sk)− νθk+1(sk+1) ) + t−1∑ k=r βθ,k ( νθk+1(sk+1)− νθk(sk+1) ) =
t−1∑ k=r (βθ,k+1 − βθ,k) νθk+1(sk+1) + βθrνθr (sr)− βθtνθt(st) + t−1∑ k=r (2) k
= t−1∑ k=r (1) k + t−1∑ k=r (2) k + ηr,t
where482 (1) k = (βθ,k+1 − βθ,k) νθk+1(sk+1),
(2) k = βθ,k ( νθk+1(sk+1)− νθk(sk+1) ) ,
ηr,t = βθrνθr (sr)− βθtνθt(st). Lemma 5. ∑t−1 k=0 βθ,kA 2 k converges a.s. for t→∞483
Proof of Lemma 5. Since νθ(s) is uniformly bounded for θ ∈ Θ, s ∈ S, we have for some K > 0484 t−1∑ k=0 ∥∥∥ (1)k ∥∥∥ ≤ K t−1∑ k=0 |βθ,k+1 − βθ,k|
which converges given Assumption 5.485
Moreover, since µθ(s) is twice continuously differentiable, θ 7→ νθ(s) is Lipschitz for each s, and so486 we have487
t−1∑ k=0 ∥∥∥ (2)k ∥∥∥ ≤ t−1∑ k=0 βθ,k ∥∥νθk(sk+1)− νθk+1(sk+1)∥∥
≤ K2 t−1∑ k=0 βθ,k ‖θk − θk+1‖
≤ K3 t−1∑ k=0 β2θ,k.
Finally, lim t→∞ ‖η0,t‖ = βθ,0 ‖νθ0(s0)‖ <∞ a.s.488
Thus, ∑t−1 k=0 ∥∥βθ,kA2k∥∥ ≤∑t−1k=0 ∥∥∥ (1)k ∥∥∥+∑t−1k=0 ∥∥∥ (2)k ∥∥∥+ ‖η0,t‖ converges a.s.489 Lemma 6. ∑t−1 k=0 βθ,kA 3 k converges a.s. for t→∞.490
Proof of Lemma 6. We set491
Zt = t−1∑ k=0 βθ,kA 3 k = t−1∑ k=0 βθ,k ( νθk(sk+1)− P θkνθk(sk) ) .
Since Zt is Ft-adapted and E [νθt(st+1)|Ft] = P θtνθt(st), Zt is a martingale. The remaining of the492 proof is now similar to the proof of Lemma 2 on page 224 of Benveniste et al. [1990].493
Let gi(θt) = Est∼dθt [ ψit · ξit,θt |Ft,2 ] and g(θ) = [ g1(θ), . . . , gN (θ) ] . We have
gi(θt) = ∑ st∈S dθt(st) · ψit · ξit,θt .
Given (10), θ 7→ ωθ is continuously differentiable and θ 7→ ∇θωθ is bounded so θ 7→ ωθ is494 Lipschitz-continuous. Thus θ 7→ ξit,θ is Lipschitz-continuous for each st ∈ S . Due to our regularity495 assumptions, θ 7→ ψit,θt is also continuous for each i ∈ N , st ∈ S. Moreover, θ 7→ d
θ(s) is also496 Lipschitz continuous for each s ∈ S. Hence, θ 7→ g(θ) is Lipschitz-continuous in θ and the ODE497 (12) is well-posed. This holds even when using compatible features.498
By critic faster convergence, we have limt→∞‖ξit − ξit,θt‖= 0 so limt→∞A 1 t = 0.499
Hence, by Kushner-Clark lemma Kushner and Clark [1978] (pp 191-196) we have that the update in500 (20) converges a.s. to the set of asymptotically stable equilibria of the ODE (12).501
Proof of Theorem 6502
We use the two-time scale technique: since critic updates at a faster rate than the actor, we let the503 policy parameter θt to be fixed as θ when analysing the convergence of the critic update.504 Lemma 7. Under Assumptions 4, 1 and 6, for any i ∈ N , sequence {λit} generated from (7) is505 bounded almost surely.506
To prove this lemma we verify the conditions for Theorem A.2 of Zhang et al. [2018] to hold.507 We use {Ft,1} to denote the filtration with Ft,1 = σ(sτ , Cτ−1, aτ−1, rτ , λτ , τ ≤ t). With λt =508 [ (λ1t ) >, . . . , (λNt ) >]>, critic step (7) has the form:509
λt+1 = (Ct ⊗ I) (λt + βλ,t · yt+1) (21) with yt+1 = ( δ1tw(st, at) >, . . . , δNt w(st, at) >)> ∈ RKN , ⊗ denotes Kronecker product and I is510 the identity matrix. Using the same notation as in Assumption A.1 from Zhang et al. [2018], we511 have:512
hi(λit, st) = Ea∼π [ δitw(st, a) >|Ft,1 ] = ∫ A π(a|st)(Ri(st, a)− w(st, a) · λit)w(st, a)>da, M it+1 = δ i tw(st, at) > − Ea∼π [ δitw(st, a) >|Ft,1 ] ,
h̄i(λt) = A i π,θ · dsπ −Bπ,θ · λt, where Aiπ,θ = [∫ A π(a|s)Ri(s, a)w(s, a)>da, s ∈ S ] .
Since feature vectors are uniformly bounded for any s ∈ S and a ∈ A, hi is Lipschitz continuous in513 its first argument. Since, for i ∈ N , the ri are also uniformly bounded, E [ ‖Mt+1‖2|Ft,1 ] ≤ K · (1 +514 ‖λt‖2) for some K > 0. Furthermore, finiteness of |S| ensures that, a.s., ‖h̄(λt) − h(λt, st)‖2≤515 K ′ · (1 + ‖λt‖2). Finally, h∞(y) exists and has the form516 h∞(y) = −Bπ,θ · y. From Assumption 1, we have that −Bπ,θ is a Hurwitcz matrix, thus the origin is a globally asymptot-517 ically stable attractor of the ODE ẏ = h∞(y). Hence Theorem A.2 of Zhang et al. [2018] applies,518 which concludes the proof of Lemma 7.519
We introduce the following operators as in Zhang et al. [2018]:520
• 〈·〉 : RKN → RK521 〈λ〉 = 1
N (1> ⊗ I)λ = 1 N ∑ i∈N λi.
• J = (
1 N 11
> ⊗ I ) : RKN → RKN such that J λ = 1⊗ 〈λ〉.522
• J⊥ = I − J : RKN → RKN and we note λ⊥ = J⊥λ = λ− 1⊗ 〈λ〉.523
We then proceed in two steps as in Zhang et al. [2018], firstly by showing the convergence a.s. of the524 disagreement vector sequence {λ⊥,t} to zero, secondly showing that the consensus vector sequence525 {〈λt〉} converges to the equilibrium such that 〈λt〉 is solution to (13).526 Lemma 8. Under Assumptions 4, 1 and 6, for any M > 0, we have527
sup t E [ ‖β−1λ,tλ⊥,t‖ 2 1{supt‖λt‖≤M} ] <∞.
Since dynamic of {λt} described by (21) is similar to (5.2) in Zhang et al. [2018] we have528
E [ ‖β−1λ,t+1λ⊥,t+1‖ 2|Ft,1 ]
= β2λ,t β2λ,t+1
ρ ( ‖β−1λ,tλ⊥,t‖ 2+2 · ‖β−1λ,tλ⊥,t‖·E(‖yt+1‖ 2|Ft,1) 1 2 + E(‖yt+1‖2|Ft,1) ) (22)
where ρ represents the spectral norm of E [ C>t · (I − 11 >/N) · Ct ] , with ρ ∈ [0, 1) by Assumption529
4. Since yit+1 = δ i t · w(st, at)> we have530 E [ ‖yt+1‖2|Ft,1 ] = E [∑ i∈N ‖(ri(st, at)− w(st, at)λit) · w(st, at)>‖2|Ft,1 ] ≤ 2 · E
[∑ i∈N ‖ri(st, at)w(st, at)>‖2+‖w(st, at)>‖4·‖λit‖2|Ft,1 ] .
By uniform boundedness of r(s, ·) and w(s, ·) (Assumptions 1) and finiteness of S, there exists531 K1 > 0 such that532 E [ ‖yt+1‖2|Ft,1 ] ≤ K1(1 + ‖λt‖2).
Thus, for any M > 0 there exists K2 > 0 such that, on the set {supτ≤t‖λτ‖< M},533 E [ ‖yt+1‖21{supτ≤t‖λτ‖<M}|Ft,1 ] ≤ K2. (23)
We let vt = ‖β−1λ,tλ⊥,t‖21{supτ≤t‖λτ‖<M}. Taking expectation over (22), noting that534 1{supτ≤t+1‖λτ‖<M} ≤ 1{supτ≤t‖λτ‖<M} we get535
E(vt+1) ≤ β2λ,t β2λ,t+1
ρ ( E(vt) + 2 √ E(vt) · √ K2 +K2 ) which is the same expression as (5.10) in Zhang et al. [2018]. So similar conclusions to the ones of536 Step 1 of Zhang et al. [2018] holds:537
sup t E [ ‖β−1λ,tλ⊥,t‖ 2 1{supt‖λt‖≤M} ] <∞ (24)
and lim t λ⊥,t = 0 a.s. (25)
We now show convergence of the consensus vector 1⊗ 〈λt〉. Based on (21) we have538
〈λt+1〉 = 〈(Ct ⊗ I)(1⊗ 〈λt〉+ λ⊥,t + βλ,tyt+1)〉 = 〈λt〉+ 〈λ⊥,t〉+ βλ,t〈(Ct ⊗ I)(yt+1 + β−1λ,tλ⊥,t)〉 = 〈λt〉+ βλ,t(h(λt, st) +Mt+1)
where h(λt, st) = Eat∼π [ 〈yt+1〉|Ft ] andMt+1 = 〈(Ct⊗I)(yt+1+β−1λ,tλ⊥,t)〉−Eat∼π [ 〈yt+1〉|Ft ] .539 Since 〈δt〉 = r̄(st, at)− w(st, at)〈λt〉, we have540
h(λt, st) = Eat∼π(r̄(st, at)w(st, at)>|Ft) + Eat∼π(w(st, at)〈λt〉 · w(st, at)>|Ft,1)
so h is Lipschitz-continuous in its first argument. Moreover, since 〈λ⊥,t〉 = 0 and 1>E(Ct|Ft,1) =541 1> a.s.:542
Eat∼π [ 〈(Ct ⊗ I)(yt+1 + β−1λ,tλ⊥,t)〉|Ft,1 ] = Eat∼π [ 1 N (1> ⊗ I)(Ct ⊗ I)(yt+1 + β−1λ,tλ⊥,t)|Ft,1 ]
= 1
N (1> ⊗ I)(E(Ct|Ft,1)⊗ I)Eat∼π
[ yt+1 + β −1 λ,tλ⊥,t|Ft,1 ] = 1
N (1>E(Ct|Ft,1)⊗ I)Eat∼π
[ yt+1 + β −1 λ,tλ⊥,t|Ft,1 ] = Eat∼π [ 〈yt+1〉|Ft,1 ] a.s.
So {Mt} is a martingale difference sequence. Additionally we have543 E [ ‖Mt+1‖2|Ft,1 ] ≤ 2 · E [ ‖yt+1 + β−1λ,tλ⊥,t‖ 2 Gt |Ft,1 ] + 2 · ‖E [ 〈yt+1〉|Ft,1 ] ‖2
with Gt = N−2 ·C>t 11 >Ct ⊗ I whose spectral norm is bounded for Ct is stochastic. From (23) and544 (24) we have that, for any M > 0, over the set {supt‖λt‖≤M}, there exists K3,K4 <∞ such that545
E [ ‖yt+1+β−1λ,tλ⊥,t‖ 2 Gt |Ft,1 ] 1{supt‖λt‖≤M} ≤ K3·E [ ‖yt+1‖2+‖β−1λ,tλ⊥,t‖ 2|Ft,1 ] 1{supt‖λt‖≤M} ≤ K4.
Besides, since rit+1 and w are uniformly bounded, there exists K5 < ∞ such that546 ‖E [ 〈yt+1〉|Ft,1 ] ‖2≤ K5 · (1 + ‖〈λt〉‖2). Thus, for any M > 0, there exists some K6 < ∞547 such that over the set {supt‖λt‖≤M}548
E [ ‖Mt+1‖2|Ft,1 ] ≤ K6 · (1 + ‖〈λt〉‖2).
Hence, for any M > 0, assumptions (a.1) - (a.5) of B.1. from Zhang et al. [2018] are verified on the549 set {supt‖λt‖≤M}. Finally, we consider the ODE asymptotically followed by 〈λt〉:550
˙〈λt〉 = −Bπ,θ · 〈λt〉+Aπ,θ · dπ
which has a single globally asymptotically stable equilibrium λ∗ ∈ RK , since Bπ,θ is positive551 definite: λ∗ = B−1π,θ ·Aπ,θ · dπ . By Lemma 7, supt‖〈λt〉‖<∞ a.s., all conditions to apply Theorem552 B.2. of Zhang et al. [2018] hold a.s., which means that 〈λt〉 −→
t→∞ λ∗ a.s. As λt = 1⊗ 〈λt〉+ λ⊥,t553
and λ⊥,t −→ t→∞ 0 a.s., we have for each i ∈ N , a.s.,554
λit −→ t→∞ B−1π,θ ·Aπ,θ · d π.
Proof of Theorem 7555
Let Ft,2 = σ(θτ , τ ≤ t) be the σ-field generated by {θτ , τ ≤ t}, and let556
ζit,1 = ψ i t · ξit − Est∼dπ [ ψit · ξit|Ft,2 ] , ζit,2 = Est∼dπ [ ψit · (ξit − ξit,θt)|Ft,2 ] .
With local projection, actor update (6) becomes557 θit+1 = Γ i [ θit + βθ,tEst∼dπ [ ψit · ξit,θt |Ft,2 ] + βθ,tζ i t,1 + βθ,tζ i t,2 ] . (26)
So with hi(θt) = Est∼dπ [ ψit · ξit,θt |Ft,2 ] and h(θ) = [ h1(θ), . . . , hN (θ) ] , we have
hi(θt) = ∑ st∈S dπ(st) · ψit · ξit,θt .
Given (10), θ 7→ ωθ is continuously differentiable and θ 7→ ∇θωθ is bounded so θ 7→ ωθ is Lipschitz-558 continuous. Thus θ 7→ ξit,θ is Lipschitz-continuous for each st ∈ S. Our regularity assumptions559
ensure that θ 7→ ψit,θt is continuous for each i ∈ N , st ∈ S. Moreover, θ 7→ d θ(s) is also Lipschitz560 continuous for each s ∈ S. Hence, θ 7→ g(θ) is Lipschitz-continuous in θ and the ODE (12) is561 well-posed. This holds even when using compatible features.562
By critic faster convergence, we have limt→∞‖ξit − ξit,θt‖= 0.563 Let M it = ∑t−1 τ=0 βθ,τζ i τ,1. M i t is a martingale sequence with respect to Ft,2. Since564 {ωt}t, {∇aφk(s, a)}s,k, and {∇θµθ(s)}s are bounded (Lemma 3, Assumption 2), it follows565 that the sequence { ζit,1 } is bounded. Thus, by Assumption 5, ∑ t E [∥∥M it+1 −M it∥∥2 |Ft,2] =566 ∑
t ∥∥βθ,tζit,1∥∥2 < ∞ a.s. The martingale convergence theorem ensures that {M it} converges a.s.567 Thus, for any > 0,568
lim t P ( sup n≥t ∥∥∥∥∥ n∑ τ=t βθ,τζ i τ,1 ∥∥∥∥∥ ≥ ) = 0.
Hence, by Kushner-Clark lemma Kushner and Clark [1978] (pp 191-196) we have that the update in569 (26) converges a.s. to the set of asymptotically stable equilibria of the ODE (12).570

Review summaries:
This paper extends the results for actor-critic with stochastic policies of [Zhang, ICML 2018] to deterministic policies and offers the proof of convergence under some specific assumptions. The authors consider both the on-policy setting and the off-policy setting and offers some convincing derivation. It provides a valuable idea and a promising direction in MARL, but the current version has several problems that need to be fixed. Specifically, some parts of equations, algorithms, and expressions are ambiguous and unintelligible. Besides, problems with the format in the formula and citations also exist, which degrade the paper’s quality and clarity.