Decentralized Deterministic Multi-Agent Reinforcement Learning
Authors: Antoine Grosnit
Desmond Cai
Laura Wynter
Venue:  (2021)
Keywords: multiagent reinforcement learning
MARL
decentralized actor-critic algorithm

Abstract: Recent work in multi-agent reinforcement learning (MARL) by [Zhang, ICML12018] provided the first decentralized actor-critic algorithm to offer convergence guarantees. In that work, policies are stochastic and are defined on finite action spaces. We extend those results to develop a provably-convergent decentralized actor-critic algorithm for learning deterministic policies on continuous action spaces. Deterministic policies are important in many real-world settings. To handle the lack of exploration inherent in deterministic policies we provide results for the off-policy setting as well as the on-policy setting. We provide the main ingredients needed for this problem: the expression of a local deterministic policy gradient, a decentralized deterministic actor-critic algorithm, and convergence guarantees when the value functions are approximated linearly. This work enables decentralized MARL in high-dimensional action spaces and paves the way for more widespread application of MARL.

Decentralized Deterministic Multi-Agent Reinforcement Learning
Anonymous Author(s) Affiliation Address email
Abstract
[Zhang. ICML 2018] provided the first decentralized actor-critic algorithm for multi-agent reinforcement learning (MARL) that offers convergence guarantees. that work, policies are stochastic and are defined finite action spaces, We extend those results to offer novably-convergene decentralized actor-critic algorithm for learning deterministic policies on continuous action spaces. Deterministic policies are important real-world settings. To handle lack exploration inherent de- terministic policies, consider both off-policy and on-policy settings. We provide the expression local deterministic policy gradient, decentralized deterministic actor-criti algorithms and convergence guarantees for awecarl--pproximmtte value functions. This work will help enable decentralized MARL in figg--iimesiooall action spaces and pave the way for more widespread use of MARL.
10
1 Introduction
12
13 Cooperative multi-agent reinforcement learning (MARL) has seen considerably less use than its single-agent analog, in part because often no central agent exists to coordinate the cooperative agents. 15 As result, decentralized architectures have been advocated for MARL. Recently, decentralized architectures have been shown admit convergence guarantees comparable to their centralized 17 counterparts under mild network-specific assumptions (see Zhang et al. [2018), Suttle et al. [019]). In this work, develop decentralized actor-critic algorithm with deterministic policies for multi- agent reinforcement learning. Specifically, we extend results for actor-critic with stochastic policies 19
(Bhatnagar et al. [2009]. Degris et al. [2012], Maci [2018), Suttle et al. [2019) to handle deterministic 21 policies. Indeed, theoretical and empirical work has shown that deterministic algorithms outperform their stochastic counterparts in high -igee-iinnsional continuous action settings (Silver et al. (January 2014b), Lillicrap et al. 2015) Fujimoto et al. (2018). Deterministic policies further avoid estimating the complex integral over the action space. Empirically this allows for lower variance of the critic estimates and faster convergence. On the other hand, deterministic policy gradient methods suffer from reduced exploration. For this reason, provide both off off-policy and on-policy versions of
29
25
26
27 results, the off- oof-policy version allowing for significant improvements in exploration. The contributions
28 of this paper are three-fold: (I) we derive the expression of the gradient in terms of the long-term
29 average reward, which is needed in the undiscounted multi- setting with deterministic policies;
30 (2) we show that the deterministic policy gradient is the limiting case, as policy variance tends to
31 zero, of the stochastic policy gradient; and (3) we provide decentralized deterministic multi-agent
32 actor critic algorithm and prove convergence under linear function approximation.
Submitted to 34th Conference on Neural Information Processing Systems (NeurIPS 2020). Do not distribute.

---

33
2
Background
34 Consider system of N agents denoted by M [N] in decentralized setting. Agents determine
35 their decisions independently based on observations of their own rewards. Agents may however com- municate via possibly limevvarying communication network, characterized by undirected graph
37 G. = (W, &d), where & is the set of communication links connecting the agents at time t E N. The networked multi-agent MDP thus characterized by tuple (S, {AA) IEN' P: [R')eN" JEN: (2))
38
39 where S is finite global state space shared by all agents in .N. AA' is the action space of agent i, and {Gr)12 is a vary-na communication network. addition, let A - IIeAA A denote the joint action space of all agents. Then, P: S x A x S + [0. 1] is the state transition probability of the MDP, and R 8 x A - IR is the local reward function of agent i. States and actions
40
41
assumed globally observable whereas rewards are only locally observable. At time f, each agent i chooses its local parameterized policy Th. :S x A' - [0, 1].
43
action of E A' given state 8t E S, according where (s, (x,a') is the probability of agent choosing action at state 8, and 0' E O C IR mh is (ON)
45
48
the policy parameter. We pack the parameters together as 0- = [(O').....
O where
47
ILe O' We denote the joint policy by ne : S SSx A + [0. 1] where (s, a) = IEN T (s, Note that decisions are decentralized in that rewards are observed locally, policies are evaluated 49 locally, and actions are executed locally. We assume that for any i E N, s E S, a' E A', the policy function Te. (s, a²) > 0 for any 0' E O' and that Td. (s, a²) is continuously differentiable with respect to the parameters O over O'. In addition, for any 0 E θ, let pe S x S + [0, 1] denote the transition matrix of the Markov chain {st)120 induced by policy To. that is, for any s, E S,
θ =
48
50
51
pd (s'(s) = ExEA Te(s,a) P(s'|s, a)). We make the standard assumption that the Markov chain (0)) irreducible and aperiodic under any To and denote its stationary distribution by dg.
53
54
55
Our objective is to find a policy hh that maximizes the long-term average reward over the network. 56 Let rit1 denote the reward received by agent i as a result of taking action a,. Then, we wish to solve:
T-11
max ((TO)= = lim T T
= Σ
0
N
1+1
iEN
sES,aEA
where R(s,a) (1/N). EieN R',s, a) is the globally averaged reward function. Let Fe (I/N). EieN then a(s,a)= E [r = 8,0, = a). and therefore, the global relative action- value function is: Qo(s,a) E E [T+1 (()]ssp s, ag a, _o], and the global relative state-value function is: Vo(s) EncA mo(s, a)Qo(s a). For simplicity, we refer to Vo and Qa as simply the state-value function and action-value function. We define the advantage function as As a) Qo(s, a) (s).
58
60
61
82
63 Zhang et al. (2018) provided the first provably convergent MARL algorithm in the context of the above model. The fundamental result underlying their algorithm is a local policy gradient theorem:
J(oo) = Eandg [g log (s, a²) Ab(s,a)].
where Ab(s,,) = Qo(s,a) - a) is a local advantage function and Vi a=*) = Evea Tze (s, d's,, "' This thcorem has important practical value as it shows that the policy gradient with respect to each local parameter 8¹ can be obtained locally using the corresponding score function Vø. mg. provided that agent i has an unbiased estimate of the advantage functions
85
66
67
88
89
A or Ag. With only local information, the advantage functions Ab or Ag cannot be well estimated
70 since the estimation requires the rewards {ri) sEN of all agents. Therefore, they proposed a consensus
71 based actor-critic that leverages the communication network to share information between agents
72 by placing& a weight (i,j) on the message transmitted from agent j to agent i at time 1. Their
73 action-value function Qo was approximated by parameterized function Q.. S x A + R, and each
74 agent i maintains its own parameter w², which it uses to form a local estimate Q., of the global Qo- 75 At each time step I, each agent i shares its local parameter wi with its neighbors on the network, and the shared parameters are used to arrive at a consensual estimate of Qe over time.

---

3 Local Gradients of Deterministic Policies
77
While the use of stochastic policy facilitates the derivations of convergence proofs, most woold 79 control tasks require a deterministic policy to be implementable. In addition, the quantities estimated
80 in the deterministic critic do not involve estimation of the complex integral over the action space found in the stochastic version. This offers lower variance of the critic estimates and faster convergence. To address the lack of exploration that comes with deterministic policies, we provide both off-policy
81
82
83 and on-policy versions of our results. Our first requirement is a local deterministic policy gradient theorem.
84
85
We assume that A' = TR We make standard regularity assumptions on our MDP. That is, we 86 assume that for any 8, 8 E S, P(s'|s, and R' (s. a) bounded and have bounded first and second derivatives. We consider local deterministic policies Ugg. : : + A'' with parameter vector
87
88 0³ O', and denote the joint policy by μ사 S + A, where (e((s) = (pgi (s),... Myw (s)) and ..... is twice continuously differentiable with respect to the parameter 8 over O¹. Let p denote the transition matrix of the Markov chain (s,112 induced by policy He, that is, for any s, E S, ( (s' = P(s'|s, (s)). We assume that the Markov chain {s:]22 is irreducible and aperiodic under any وب and denote its stationary distribution by dld.
89 0 ((.)) ) [ON) We assume that for any E S, the deterministic policy function pi (s)
91
82
93
94
Our objective is to find policy μi that maximizes the long-run average reward:
max J (H1) = Es No(s)]
Σ d (s)
.ES
Analogous to the stochastic policy case, denote the action-value function by Qo(s,a) Eiz0 [[ - [80)) = 8, aq a, mo]. and the state-value function by Vo(s) = Qa(s, (o)s)))(ss) (s)))). When there is ambiguity, we will denote (uu) and d by simply J(0) and d", respectively. We present three results for the long-run average reward: (1) an expression for the local deterministic policy gradient in the on-policy setting (ge)) (2) an expression for the gradient in the off- ooolcol setting, and (3) we show that the deterministic policy gradient can be seen as the limit of the stochastic one.
96
98
100
102
On-Policy Setting
Theorem (Local Deterministic Policy Gradient Theorem On Policy). For any 0 E i.
104
V aa: exists and is given by
(ooJ( = Bandno (o) Qo(s, (g)))))))))))))))))))))))))))))) 1a=pp,
The first step of the proof consists in showing that VoJ(po) Ey Vo Q0(s,a)la-noth)
This is an extension of the well-known stochastic case, for which we have VTJ(TT)) = Esnno V log (ogg(m((ass)22 (els)) a)). which holds for a long-term
107
108
averaged return with stochastic policy (e.g Theorem of Sutton et al. (2000a]). See the Appendix for
109
the details.
110
Off-Py Setting In the off-policy setting, we are given behavior policy " : P(A), and our goal is to maximize the long-run average reward under state distribution d=:
111
Jx (1o) Ex-ar [[(s, (o())) = Σ d" (s) (o(s))
(1)
SES
112 Note that we consider here an excursion objective (Sutton et al. 2009] Silver et al. (Jauaryy 2014a],
113 Sutton et al. (2016) since we take the average over the state distribution of the behaviour policy л of the state-action reward when selecting action given by the target policy na. We thus have:
115 Theorem (Local Deterministic Policy Gradient Theorem Off Policy). For any 8 E θ, E,
S + P(A) a fixed stochastic policy, o exists and is given by
Ja (14) = Eg Vos V R(s, u1 (5), a²) oi
3

---

117
Proof.
Since d" is independent of & we can take the gradient on both sides of T
Vole(s) V VoR(ss, (e(s) a=po(o) VaJr((19) Bandd
118 Given that (2) 0 i $ we have Vopo(s) Diag( (oii (8), VaN J (s)) and the
result follows.
L
120
This result implies that, off-policy, each agent needs access to "0 (st) for every t.
I Limit Theorem As noted by [iiverr et al. January 2014b], the fact that the deterministic gradient a limit case the stochastic gradient enables the standard machinery of policy gradient, such as compatible-function approximation (Suttonn et al. [2000b]) natural gradients (Kakade (200T), on-line feature adaptation (Prabuchandran et al. (016).) and actor-critic (Konda) [2002) to be used with deterministic policies. We show that it holds in setting. The proof can be found in the Appendix.
122
124
Theorem (Limit of the Stochastic Policy Gradient for MARL). Let ne be stochastic policy such that a (als) = vo (s), a), where a is parameter controlling the variance, and Va satisfy Condition in the Appendix. Then,
127
lim VaJKo (Te,)) V (111)) 010
129
where on the lh.s the gradient the standard stochastic policy gradient and on the rh.s. the gradient is the deterministic policy gradient.
130
Algorithms
131
132
We provide two decentralized deterministic actor-critic algorithms, one on-policy and the other off-policy and demonstrate their convergence in the next section; assumptions and proofs are provided in the Appendix.
133
134
135
On-Policy Deterministic Actor-Critic
Algorithm Networked deterministic on-policy actor-critic
Initialize: step = O: parameters Ji- wh W6. 0h. Vi E W; state 8u; stepsizes {Bw. 1120, f80, Draw o = Hgg (su) and compute ab V Hig (su)
Observe joint action dg (a) ... a and ão = (u.....,0p) a
repeat
for i e N do
Observe st+1 and reward ri+1 = ('),
Update Jim1 +- (1 Bw,,)) Jf Bus r't1
Draw action a++1 = pbg (8 and compute 2 = [
end for
Observe joint action at+1 = (a an and ύet1 = (it=1: 7711 for i E N do
Update: 87 + rit - J Q.: (81-1, - Quy
Critic step: Wf +- wi + Buet 5f Vw at) W-W!
Actor step: 6:41 0 + Bo. Vorly (s:) V.. Quy (8t, a a²) a'za
Send of to the neighbors (j NN: (1, E &r} over 9,
Consensus step: w/+1 + of at
end for
Update t
until end

---

136
Consider the following on- on-policy algorithm. The actor step is based on an expression for Vo (ug) terms of V. V. Qseee Equation (15) in the Appendix). We approximate the action-valie value function Qo using a family of functions Qu A R parameterized by w, column vector in K Each agent i maintains its own parameter w² and uses Q.e as its local estimate of Qa. The parameters w' are
137
138
139
140
updated in the critic step using consensus updates through a weight matrix C.
(ct))
NRN
where cf the weight on the message transmitted from i to j at time t, namely:
141
++ = (1 - Bwwc) Ji + Sw.s rit1
(2)
w wi + Buit . -5 V (8c, ar)
(3)
W=W!
w/+1 Σ cl w/
(4)
JEN
142 with
6: = - J + Que (54+1,0+11) - (ur(s): at).
For the actor step, each agent improves its policy via:
0+1=00 Bo, Voruóg (+1) V Vui (u ar at)
(5)
144
Since Algorithm|| I is an on-policy algorithm, each agent updates the critic using only (st, Ots 8:41). at time knowing that ax+1 Me, ($:41). ). The terms in blue are additional terms that need to be shared when using compatible features (this explained further the next section).
146
147
Off-Policy Deterministic Actor-Critic We further propose an off-policy actor-critic algorithm, defined Algorithm 2 to enable better exploration capability. Here, the goal is to maximize Jx (Ha) where is the behavior policy. To do so, the globally averaged reward function R(s, a) is approximated using a family of functions Rs S x A - TR that are parameterized by X, a column vector in R Each agent i maintains its own parameter X and uses Rx as its local estimate of R. Based on I the actor update is
148
150
152
0/+1 = 02 + Bo,t Ver V (xp (o)), o'==ag(sn)" (sa)
(6)
153
which requires each agent i to have access to 1 (8t) for j E E.
The critic update is
X; = M + 3x,e 8%. () A=
1/41 Σ &
JEN
155 with
5, = r ar) (x.
156
In this case, 5f was motivated by distributed optimization results, and is not related to the local TD-error (as there is no "temporal" relationship for Rt). Rather, it is simply the difference between the sample reward and the bootstrap estimate. The terms in blue are additional terms that need to be shared when using compatible features (this is explained further in the next section).
157
158
159
5
Convergence
180
161
To show convergence, we use two-timescale technique where in the actor, updating deterministic policy parameter 0' occurs more slowly than that of wt and J in the critic. We study the asymptotic behaviour of the critic by freezing the joint policy (40, then study the behaviour of 0g under convergence of the critic. To ensure stability, projection is often assumed since it is not clear how boundedness of
163
5

---

Algorithm 2 Networked deterministic off-policy actor-critic
Initialize: step = 0; parameters X6 No. l. Vi E NN state su: stepsizes (Bx.t)120 (B0,) Draw ab ~ x (5p) compute aj - ug: (Sv) and 0g = Vo Hèg (so) Observe joint action ag = (ad..... ab ), āg = (ag..... . ag and Ty (ah...., og) repeat
for i E . do Observe 8t+1 and reward r/41 (s), end for for i E / do
Update: 52 ritt R2
Critic step: Xi +- Ni Bx, oi (x 1==
Actor step: 01+1 = 0j + Bo,t ( Vol (y (st), a²) ('=
Send X; to the neighbors (j NW (i,5) E Et} over Gr end for
for i E .V do Consensus step: Mi+1 f Ejer of X
Draw action ac+1 ~ (($+1)), compute at+1 Hoj ($1+1) and compute 2241 Vollo ($++1)
end for
Observe joint action a++1 (oi41...... NN.) de+1 (df+1)..... a and ãेF1 (a) I......... ..+1) Update + 1+1 until end
(0:) can otherwise be ensured (see Bhatnagar et al. 2009 ). However, in practice, convergence is
185
typically observed even without the projection step (see Bhatnagar et al. (2009), Degris al. [2012).
167
Prabuchandran et al. [2016), Zhang et al. (2018), Suttle et al. (019]).
also introduce the following technical assumptions which will be needed in the statement of the convergence results.
169
A ssummtiio 1 (Linear approximation, average-reward), For each agent i, the average-reward function R is parameterized by the class of linear functions, i.e., Rys (s,, a) = wa was a) X² where we (s, a) [ a).... weg wa. (s, a)] RK the feature associated with the state-action pair (s, a). The feature vectors wo(S (s, a), well as &, a) uniformly bounded for any E S, A, k
170
171
[1, K]. Furthermore, we assume that the feature matrix W R|S| K has full column rank, where the k-th column of Wr, is [[A 전 (a)s))aa, a)da, s E S] for any l: E [].
173
174
Assumption 2 (Linear approximation, action-value). For each agent i, the action-value function is parameterized by the class of linear functions, i.c., Q (s,a)
Φ(s, a) w where Φ(s, 01 (s. a)...)..... Φx (s, a)] E IRK is the feature associated with the state-action pair (s,a). The feature vectors (08, a). as well as Vadu a) are uniformly bounded for any E S, E A, E (1,..., .)]......... Furthermore, we assume that for any 0 E O, the feature matrix $ E S| has full column rank, (s))) s] for any l E [1, Also, for any u E Ø²
177
178
179
180
where the k-th column of Dg Dau + 1.
181
182
Assumption (Bounding 0). The update of the policy parameter 0³ includes local projection by 1 TH - O that projects any 0f onto compact set O' that can be expressed as (0'g) <
184
0, j =
s²} L....s's R", for some real- realevalued, continuously differentiable functions {9} hsiss
defined on mm We also assume that θ I @' is large enough to include least one local minimum of (()).
186
We use {Fi) to denote the filtration with F, a C+-1, Pr-1, t).
Assumption (Random matrices). The sequence of non-negative random matrices (C+ = (c())))
188
satisfics:

---

190
1. C is row stochastic and FF) is a.s. column stochastic for each t, i.e., C,1 = 1 and
1 [(C 1 a.s. Furthermore, there exists constant 77 (0, 1) such that, for any 0, we have c 2
193
2. C₁ respects the communication graph Gr, i.e., of = if (4,j) $ &
3. The spectral norm of [ (I - 11 /N) C.] is smaller than one.
194
195
4. Given the d-algebra generated by the random variables before time i, Cr conditionally independent of 5t, and ri+z for any E ..
197
Assumption (Step size rules, on-policy). The stepsizes Bu,,, satisfy:
Σ Bui Eous 00
Bo.
> (Be., + +8,,)) <
Σ |3,,01 -B0,cl 00.
198 In addition, fa,,= = o(Bu,r) and Su, 1.
199 Assumption (Step size rules, off off-policy). The step-sizes Bx,c, Bo, satisfy:
BA. Σ
Ba.t 00,
ER. + 1/, oo
3g, = (Bx,)),
lim Bx
On-Policy Convergence To state convergence of the critic step, we define Dî Diag (s): E S]. Ra = [R(s, (o())), 8 E S) E R and the operator 7/0 I + S for any action-value vector Q E glls (and not RISI-iA since there is mapping associating an action to each state) as:
(o) = Rg ((p) 1 - P
Theorem 4. Under Assumptions and for any given deterministic policy po, with (fi and {we) generated from 22. we have
Σiex Ji = (ue) and lim; = we a.s. for any
i N,, where
J(us) = d8 =d ((s,
sES
200 is the long-tern ner-term average return under μa, and we is the unique solution to
49 D2 [T (Powe) Towol
(10)
Moreover, Wa the minimizer of the Mean Square Projected Bellman Error (MSPBE), i.e., the minimize
solution to
| IIT (low))l
201 where II is the operator that projects a vector the space spanned by the columns of P.. and 11-11
202 denotes the euclidean norm weighted by the matrix D
203 To state convergence of the actor step, we define quantities vio Ei and Ei as
v1.0 = V (s) and
wi = vi. = (6
E. Va, Qwo (St,
ai (st,
as)
(; Va, Va.o(st, ai as) 2a wa,
ς = Va, Quc (i (ai))
Va,o(s,, aj " "a (o)) w/-
e.
7

---

Additionally, we introduce the operator (-)) as
204
00 + 17 (7-)(0) - 0² I
F't [g(()]
lim
(11)
0.
205
for any 0 E θ and g: ④ i a continuous function. In case the limit above not unique we take
206 I [o) to be the set of all possible limit points (11).
Theorem 5. Under Assumptions 2 and the policy parameter 88 obtained from converges
207
208
a.s. to a point in the set of asymptotically stable equilibria of
0' = 1 [B se [wi. Ei,a]]
for any i E N.
(12)
209
In the case of multiple limit points, the above is treated as a differential inclusion rather than an ODE.
211
The convergence of the critic step can be proved by taking similar steps as that in Zhang et al. (2018).
For the convergence of the actor step, difficulties arise from the projection (which is handled using Kushner-Clart Lemma Kushner and Clark (1978) and the dete-dependent noise (that handled by "natural" timescale averaging Crowder] [2009]). Details are provided in the Appendix.
213
215
Remark. Note that that with linear function approximator Qo. V1.00 - E1.0
(oHL(Ss) Va VaQua (st,a) a=po(ae) may not be an unbiased estimate of VoJ(0):
216
Vona(s)) ( (Valuo (mp - V VaQuo (8, () (s,)))a-no(s)
Eg [c,00 V (0) sodd
217
standard approach to overcome this approximation issue via compatible features (see, for example, Silver et al. JJanuary 2014a] and Zhang and Zavlanos (2019) ), i.c. Φ(s, a) = a VoHa(s) giving, for E I
218
219
Qu(s,a)=a =a a Vano(s) = (a po(s)) (s) Vo()))
with (s))s) (a(()))())) and valu(s, a=
(8)
220
We thus expect that the convergent point of (5) corresponds to small neighborhood of a local optimum of [UO), ) i.e., Juu) = 0, provided that the error for the gradient of the action- value function V.Qu(s,a) (s)
221
(oQ a)la=mo(s) is small. However, note that using
compatible features requires computing, at each step t, 0( 0e) a; Vopo(Ss) Thus, in Algorithm each agent observes not only the joint action ac+1 (a a+t1) but also
224
225
(V W (8++1),....
V Tow pap (9++1)) (see the parts in blue in Algorithm
Off-Polic Convergence
227
Theorem 6. Under Assumptions 7 and 6 for any given behavior policy v and any 0 E θ with
228
{ generated from 7 we have lim xc Xa a.s. for any N, where Xg is the unique
229
solution to
B do A d=
(13)
where d: = (dd S) Ar, Ifa =(aas) a)) da, S| K and
230
BT, = [ESest d" (s) ((als)u:(s,a) a)) da, S sis K] RKx
231
From here on we let
G V (s 0. (st), ai)
Wa H/. (st), as)
c; a; (xc) do
a, ax=pi
ę = Va, (St, (8t), a:)
Va u( 11 (st), a:) a (x) X
233 and we keep
11. Veriig (8t).
and wt Vhe = (orrig((s))
8

---

234 Theorem 7. Under Assumptions 1 3 4 and the policy parameter B3 obtained from 6 converges
235 a.s. to a point in the asymptotically stable equllbbia of
0' = r [Eendr [14 Si,]]-
(14)
We define compatible features for the action-value and the average-reward function in an analogous 237 manner: w a) = (a po(s)) (opo(s) For X E Rm"
a) = =a (a-)) Vopu(s)) A V. Va Voouos))
and we have that, for X = argmin Eend"
V Voltsols, V VaB(s, (a())))())))
VoJa(wo)) - Exnay [V) V fas a) la= Eawar [Vopu(s) V Fa a) (
238
The use of compatible features requires each agent to observe not only the joint action taken
a++1 (at+1..... a(t1) and the "on-policy action" ur+1 (i141..... a.+1). but also 0c+1
(V He (st+1)...... V Mop ($++1)) (see the parts in blue in Algorithm
241
We illustrate algorithm convergence on multi-agent extension of a continuous bandit problem from
Sec. 5.1 Silver et al. January 2014b). Details are in the Appendix. Figure Shows the convergence
242
243
of Algorithms and averaged over runs. In all cases, the system converges and the agents are
able to coordinate their actions to minimize system cost.
actier dinersans
25 Psaction dinens 085
L8/03
12000
J0000
2,000
.000/
200002
+2000
Figure 1: Convergence of Algorithms I and 2 on the multi-agent continuous bandit problem.
244
6
Conclusion
246
We have provided the tools needed to implement decentralized, deterministic actor-critic algorithms for cooperative multi-agent reinforcement learning. We provide the expressions for the policy gradients, the algorithms themselves, and prove their convergence in on-policy and off-policy settings. We also provide numerical results for continuous multi-agent bandit problem that demonstrates the convergence of our algorithms. Our work differs from Zhang and Zavlanos [2019) as the latter was based on policy consensus whereas ours is based on critic consensus. Our approach represents agreement between agents on every participants' contributions to the global reward, and as such, provides consensus scoring function with which evaluate agents. Our approach may be used in compensation schemes to incentivize participation. An interesting extension of this work would be to prove convergence of our actor-critic algorithm for continuous state spaces, as it may hold with assumptions on the geometric ergodicity of the stationary state distribution induced by the deterministic policies (see Crowder [209]). The expected policy gradient (EPG) of Ciosek and W Whiteson [2018]. . hybrid between stochastic and deterministic policy gradient, would also be interesting to leverage. The Multi-Agent Deep Deterministic Policy Gradient algorithm (MADDPG)
248
250
251
252
253
254
255
256
257
259
Lowe et al. [2017] assumes partial observability for each agent and would be useful extension,
261
but it is likely difficult to extend our convergence guarantees to the partially observed setting.

---

References
262
263
Albert Benveniste, Pierre Priouret, and Michel Métivier. Adaptive Algorithms and Stochastic Approximations. Peringer-Verlage Berlin, Heidelberg, 1990. ISBN 0-387-52894-6.
Shalabh Bhatnagar, Richard S. Sutton, Mohammad Ghavamzadeh, and Mark Lee. Natural actor-critic algorithms, Automatica, 45(11)) 1:2471-2482, November 2009, ISSN 0005-1098. doi: 10.1016/j. wttmmaatiia.00907.000000 URL http://dx dwi. 10. 1 automatica.2009 2009 .0.0000..00000 008
286
Kamil Ciosek and Shimon Whiteson. Expected Policy Gradients for Reinforcement Learning. arXiv e-prints, art, S1ii::18000032266 Jan 2018.
289
270
Martin Crowder. Stochastic approximation: A dynamical systems viewpoint by vivek s. borkar. International Statistical Review, 7702)3306-366, 2009.
Thomas Degris, Martha White, and Richard S. Sutton. Off-policy actor-critic. CoRR, abs/ 1205.4839, 2012.
273
org/ abwpg//aaa//////a 4839
274
Scott Fujimoto, Herke van Hoof, and Dave Meger. Addressing function approximation emror actor- critic methods. CoRR, abs/1802.099777, 2018. URL http:// org/
Sham Kakade. A natural policy gradient. In Proceedings of the 14th International Conference Neural Information Processing Systems: Natural and Synthetic, NIPS pages 1531-1538, Cam- bridge, MA, USA, 2001. MIT Press. URLhttpp /ttt:://dl... acm. org/ciittiinn....oooiioooooo cfm?id
277
279
2980738
280
Vijaymohan Konda. Actor-critic Algorithms. PhD thesis, Cambridge, MA, USA, 2002. AA10804543.
281
Harold J. (Harold Joseph) Kushner and (joint author.) Clark, Dean S. Stochastic approximation methods for constrained and unconstrained systems. New York Ppringer-Verlape 1978. ISBN
283
0387903410.
284
Timothy P. Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Manfred Otto Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. CoRR, (bs/1109.00971, 2015.
285
286
287
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor- critic for mixed cooperative-compettiiee environments. Neural Information Processing Systems (NIPS), 2017.
288
289
290
Hamid Reza Maei. Convergent actor-critic algorithms under off-policy training and function approxi- mation. CoRR, 802./802,,7 2018. URL SRRLL/ppp//aarai.oor////////2/2
291
292
Marbach and J. N. Tsitsiklis. Simulation- pppiuaatioobbuscooooppiitiiooo optimization of markov reward processes. IEEE Transactions on Automatic Control, 46(2):191-209, Feb 2001. ISSN 0018-9286. doi: 10.1109/9. 905687.
293
294
295
K. Prabuchandran, Shalabh Bhatnagar, and Vivek S. Borkar. Actor-critic algorithms with online feature adaptation. ACM Trans. Model. Comput. Simul., 26(4))24:1 February 2016. ISSN 1049-3301. doi: 10. 10.1145/2868723. URL lttp:://///oi acm org/ 10. 1145/2868723
296
297
298
Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., New York, NY, USA, 1st edition, 1994. ISBN 0471619779.
299
300
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic Policy Gradient Algorithms. International Conference on Machine Learning, pages 387-395, January 2014a.
301
302
303
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic Policy Gradient Algorithms. International Conference on Machine Learning, pages 387-395, January 2014b.
304
305
Wesley Suttle, Zhuoran Yang, Kaiqing Zhang, Zhaoran Wang, Tamer Basar, and Ji Liu. A multi-agent off-policy actor-critic algorithm for distributed reinforcement learning. CoRR, abs/1903.00 06372, 2019. URL //arxiv. org/ habbs/9993..633 06372
307
10

---

309
Richard S Sutton, David A. McAllester, Satinder P. Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In S. A. Solla, K. Leen, and K. Müller, editors, Advances in Neural Information Processing Systems 12, pages 1057-1063. MIT Press, 2000a.
310
312
313
Richard Sutton, David A. McAllester, Satinder P. Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In S. A. Solla, T. K. Leen, and K. Müller, editors, Advances in Neural Information Processing Systems 12, pages 1057-1063. MIT Press, 2000b.
315
Richard S. Sutton, Hamid Reza Maei, Doina Precup, Shalabh Bhatnagar, David Silver, Csaba Szepesvári, and Eric Wiewiora. Fast gradient-descent methods for temporal-difference learning with linear function approximation. In Proceedings of the 26th Annual International Conference on Machine Learning, ICML '09, pages 993-1000, New York, NY, USA, 2009. ACM. ISBN 978-1-60558-516-1
318
320
322
Richard S. Sutton, Rupam Mahmood, and Martha White. emphatic approach to the problem of off-policy remporal-difference learning. J. Mach. Learn. Res., 17(1):2003-2311 January 2016. acm. htt.a//..mmm..o//aa./..///////// cerg/citation... cfm?id-2946645. 300000 30070226
324
ISSN 1532-4435. URL httphttp:///11
325
Kaiqing Zhang, Zhuoran Yang. Han Liu, Tong Zhang, and Tamer Basar. Fully decentralized multi- agent reinforcement learning with networked agents. 80:5872-5881 10-15 Jul 2018.
Yan Zhang and Michael M. Zavlanos. Distributed off-policy actor-critic reinforcement learning with policy consensus. CoRR, 190309993,, 2019.
328

---

329
Numerical experiment details
330 We demonstrate the convergence of our algorithm a continuous bandit problem that a multi- agent extension of the experiment in Section 5.1 of Silver et al. (2014). Each agent chooses an action a' E I... We assume all agents have the same reward function given by (a = (2,'' (') [0. and a" = [4, ... We consider 10 agents and action dimensions m 10, 20, 50. Note that there are multiple possible solutions for this problem, requiring the agents to coordinate their actions to sum to a" We assume target policy of the form jıg. = 6' for each agent i and a Gaussian behaviour policy ((.) ~ NN000 .o)) where 0g = 0.1. We use the Gaussian behaviour policy for both Algorithms and 2. Strictly speaking, Algorithm is on-policy, but in this simplified setting where the target policy is constant, the on- on-policy version would be degenerate such that the Q estimate does not affect the TD-error. Therefore, we add Gaussian behaviour policy to Algorithm 1. Each agent maintains estimate Q² (a) of the critic using linear function of the compatible features and a bias feature. The critic is recomputed from each successive batch of 2m steps and the actor is updated once per batch. The critic step size is 0.1 and the actor step size is 0.01. Performance is evaluated by measuring the cost of the target policy (without exploration). Figure 2 shows the convergence of Algorithms 1 and 2 averaged over 5 runs. In all cases, the system converges and the agents are able to coordinate their actions to minimize system cost. The jupyter notebook will be made available for others to use. In fact, in this simple experiment, we also observe convergence under discounted rewards.
332
- -a"). The matrix C is positive definite with eigenvalues chosen from
334
335
336
337
338
339
340
0
342
344
345
346
348
acter dinersios
acter
action dimenibra
2
1|%
3X
XX
Stpt
Figure 2: Convergence of Algorithms 1 and 2 on the multi-agent continuous bandit problem.
Proof of Theorem [
350
The proof follows the same scheme as Sutton et al. (2000a]. naturally extending their results for a deterministic policy (e and continuous action space A.
351
352
Note that our regularity assumptions ensure that, for any s E S, Va(s), VoVa(s), J(0), (o.( d (s) are sipschitz-continuod functions of (since pi twice continuously differentiable and θ is compact), and that Qa a) and V Qo a) are Lipschitzz-ooniinouus functions of a (Marbach and Tiissikiss (201]).
353
354
355
We first show that [ = Ey-ar (otu(()) Qa(s, a) (=))=
356
357
The Poisson equation under policy μi is given by Puterman [994]
Qo(s,a) = -(0) + Σ ((s)s,
S'ES
12

---

358
So,
VoVo(s) VoQo(s, po(s)
[o(((s, Σ ((s))s
s'ES
VoNo(s) V. Val(s, V.R(ss VoJ(0) + Vo Σ
d'ES
Vomo(s) V V.R((s 0) (= Vo)(()
+ VoHo(s) VaP(s'ls, Vo(s') + Σ P(s')s,
S'ES
'ES
Vopo(s)V R(s,a) P(sss ((s)s,))Vo((5)
s'ES
a=
VoJ(0)+ + Σ (((
S'ES
Volo(s)V Qo(s, + Σ
d'88
359
Hence,
VaJ(0) Volu(s)
+ Σ P((1)s1((6)))VV(())) -oVa(s))))))
s'ES
Σ [o) Σ Volo Qo(s, ()==pp(())
#ES
SES
Σ ((s))
Σ (s)Vooo)sss) EES
#ES
EESS
Using stationarity property of do, we get
ΣΣ (())P)l1sssn(s))))) Σ (c(VVooooss)
sES SEES
EEES
Therefore, we get
Vo) Σ d (s)oo)) v.Qo(s,a))a-oaa Ex Vouu(s) VaQa(s, a) mato))))))
SES
360 Given that V V (2)ss) i have VoHo(S) Diag (s), ..., VaN (s)). which implies
J(O) = E Vo-u (z) (0(s, (
(e)=
(15)
Proof of Theorem 3
We extend the notation for off-policy reward function to stochastic policies as follows. Let 3 be behavior policy under which {st)c20 is irreducible and aperiodic, with stationary distribution d For 385 a stochastic policy æ S + >(A), we define
363
Jm(m) [d)(s) / {(als)
#ES
386
Recall that for a deterministic policy p + A, we have
Jo(n)= Σ (s)sss)))))))))
EES
387
introduce the following conditions which are identical to Conditions B1 from Silver et al. January 2014a).
13

---

389
Conditions 1. Functions Ve parametrized by are said to be regular delta- approxxppoo on R C A they satisfy the following conditions:
370
371
1.
The distributions Vo converge to delta distribution: lim SA (a', a))((dda==== f(a') for a' E and suitably smooth f. Specifically we require that this convergence is uniform in a' and over any class F of T--Lipschitz and bounded functions, [a](a)]]< I. < oc,
372
374
s(a < b < 00, i.e:
1/, Va(ldda)) - s(a') O.
lim
sup 2 JEF a E'ER
375
2. For each a' E R, (a,.)) is supported on some compact Ca, S A with Lipschitz boundary bd(C.r), vanishes on the boundary and continuously differentiable on Car.
376
377
3. For each a' R, for each a E A. the gradient Va'Vo a) exists.
4. Translation invariance: for all a A,a' E R. and any 8 E R= such that ò E A. a' + 8 E A, Vo (a', a) = Vr + 5, + 8
379
The following lemma is immediate corollary of Lemma 1 from Silver et al. (Janurry 2014a].
Lemma 1, Let Vo be regular celta-approximation on R S A. Then, wherever the gradients exist Vev(d' a) = -aaa(d'
381
Theorem 3 is a less technical restatement of the following result.
382
Theorem 8. Let μo - A. Denote the range of po by Ro A. and R UpRo. For each 6, consider Wa.o stochastic policy such that [a)s) = Vo (Ho(s)),,)), where vo satisfy Conditions ! on R. Then, there exists > such that, for each O E O + Jan. (To.a).
384
T + Jno.o (MO), ooo + VoJau..(TT. and a + VeJna (Ho) are properly defined on [0.r] (with VaJrooo
385
386
JA (T0.0) Jun. (Po) = JJp (euر) and VaJ
VaJuo (No)), and we
have:
lim VoJ (TH o40
lim VaJTo. (HO) = VoJno(Ho). r19
386
To prove this result, we first state and prove the following Lemma.
Lemma 2. There exists such that, for all 0 E Q and E [0, stationary distribution d exists and is unique. Moreover, for each f E O, a +> de and a + Vod are properly defined on [0,r] and both continuous at O.
390
Proof of Lemma 2 For any policy 3. we let (p'
392
be the transition matrix associated the a. Markov Chain {#1120 induced by B. In particular, for each 0 E e,, > O, 8, E S, we have
388
Piue
P(s' |s, (o))),
To (als)) a, aada=// Na (H)((s) a)da.
Let E E, S, (0n) E R such that On and (on)nEN E ER+ on +
- pike
pllen
plue
Applying the first condition of Conditions D with f: P(s'(s, a) belonging to F:
395
Var, (s))
P(s' ((5'l1,,,e Ma, (s))
/ |Vvo. (a', ,o, (a)dd S(a') 0. < sup EEF
396
By regularity assumptions on 1 + (s) and P(s'|s, (s, we have
pHti
puo
P(s' ss pe (s)) ((s((s, n-000
0.
14

---

397
Hence,
p -iie 0.
Therefore, for each s, s' S, (0, о) + p with P Pate is continuous θ {0}. Note 399 that, for each n E N. P II, (Pa) 2. is polynomial function of entries P. Thus, for
398
each n E N. fn (0.o) - II (Pra.a
a.s' with (0,000) = II (PHo") 8,." is continuous on X {0}. Moreover, for each E θ 2 0, from the structure of pre.", if there is some n E N such that Jn- (0, > 0 then, for all n², [m(0, a) 0.
400
401
Now let suppose that there exists (0,) @a such that, for each there is a on S <n- such that fn (0,, on) = O. By compacity of θ, we can take (0,) converging to some 0 E O. For each n² E N. by continuity we have f.. (0, 0) lim fn (n) O. Since pHe is irreducible and
404
such that for all s, and for all n 2 n. (pro")
408
aperiodic, there is some
0, i.c.
8,6
407
f (0, 0) > 0. This leads to a contradiction.
408
Hence, there exists n > such that for all
and a I <n-'1, fx,0, 0. let
follows that, for all 0 E θ and a E [0, r). paee. transition matrix associated to an irreducible and aperiodic Markov Chain, thus de is well defined the unique stationary probability distribution associated to pro.., We fix E θ the remaining the proof.
409
410
411
Let 3 a policy for which the Markov Chain corresponding to p3 is irreducible and aperiodic. Let 412
E S, as asserted in Marbach and Tsitsiklis [2001], considering stationary distribution d as vector (d²) .ES R S d is the unique solution of the balance equations:
Σ
d 6,8'
dd se
SES
Σ d =1
SES
415 Hence, we have A an [S] x [S] matrix and a * 0 constant vector of [R|S| such that the balance
416 equations of the form
d =a
(16)
417 with A eeer depending on p st. in an affine way, for each s' E S. Moreover, A is invertible, thus
418 d is given by
d
det( T
Entries of AA)( and dct(AA) are polynomial functions of the entries of p8
419
Thus, a ++ d de adj( ) is defined on [0,r] and is continuous at 0.
420
Lemma 1 and integration by parts imply that, for s E S, [0.r]:
/ VaVVlld', a)) P(s'l (,'lss,a a)da = ( a)da
Jempen volno(s), a)da boundary terms
VV al
Cngtos
where the boundary terms zero since ue vanishes the boundary due Conditions
15

---

423 Thus, for s, [0.r]:
" Ve / no.o (als) [s aada
(als) s a)da
(17)
Voua(s) Va a)l a)lo= P(slls,a)da I vo (s) a)) as
Valu((s
Cmato)
424
where exchange of derivation and integral in 17 follows by application of Leibniz rule with:
Va E A. A + ne Te (cls)) is differentiable, and (o7e)
426
VeHo(s) Vav (a', =))==
Leta" E R, 10 E
(c) s, a)ll VoHu(s) V (d', a) a)l a))=
Vouo(()) V. (a' a'=
sup (1)10()) op (uo
sup (a)oo()) 1op (ava(a" a pa(s)) + a")l (18)
AE
S sup (oHo(() AE
lop sup
(a"s(a" (a"" a)l laec.- aec..
where ||-[lap denotes the operator norm, and 18) comes from translation invariance (we take Vau, (a (a",a) ,a) for IR" CR.)) a
429
sup
[ (s) sup V/V ,a)l lacc,, is acC..
de
measurable, bounded and supported C.,, it is integrable on A.
Dominated convergence ensures that, for each A [L, ml] partial derivative gx( 0g. SA Vo (als) ss, a)da is continuous: let On 0, then
433
(Om) 0n. / (als)) a)da
do no. (s) I vola",a aaa'.a--a no (s) + +a V. a)da
C.-
Oo (s()) n
vola", - mo(s) + a V P(s' (s||s, a a)da = (o)
ea-
with the dominating function a sup Io (a sspp V |s a) loec.-.
434
aeC.-
aEA
Thus VaP is defined for E [0,r] and is continuous at O, with VaP s.x"
(s))(() V. P(s'ls a) (s)))))) Indeed, let (an)neN E [0,r] + a, 1 O, then, applying the first 436
condition of Conditions with / :a P(s''s, a) belonging to F. we get
Vo VoPa 6.6"
/ Von
=|Voop(())llg
VoP(s
Cestes
n
438 Since d= dot ( o.o adj (ATM.)) a with det (A 0 for all [o, and since entries of adj (A and det (o are polynomial functions of the entries of psa.e, it follows that
16

---

+ Ve, is properly defined on [0,r] and is continuous at 0, which concludes the proof of
440
Lemma 2
We now proceed to prove Theorem 8
443
Let ( Th as in Theorem 3] and > such that a d o H Vod are well defined on [0.r] and are continuous at O. Then, the following two functions
444
EEd dd (s) / Te (alo)
+ Jao.0 (TO,))
sES
+ Jae. (18)
Σ d (8) ((s,
SES
445 are properly defined on [0,r] (with Jn (To.o) = Jos.o((o) = Juo (1o))) Let 8 E S, by taking similar arguments in the proof of Lemma 2 we have
V / ne ((s,))
= / (a 8)
-Vopu(s) / Jensen a))
47 Thus, a + VaJso.o (TT, is properly defined on [0, and
/ To.a(als)) a)da
VOJTU, (T0 = Σ vod (8)
SES
Σ d (8) / (o.o(a)s) a)da
#ES
V Tod (8) / vo(Ho(()) a) a)
8ES
Σ d (s))op)())
vo(uo(s), a)) a).
aa
#ES
Similarly, + VoJTO.o (1o) is properly defined on [0, and
VoJ (pp) Σ Ved (s) (s)
Σ To (s)V((s) ao
449 To prove continuity of both a + VOJTO. (T0,r) and a VaJro (1O) (with VoJTo (TO,0)
450 VoJna,o VoJuo (Ho)), let (an)n20
VoJao. (T V J (T000) VoJao.. (m) V (Ho) + VoJao... (HO) V ( (19)
For the first term of the r.h.s we have
V VgJso.on (TT,..))
VeJsson (He)
Mo (6)1 / Van a(s, R(s,
#ES
+ Σ Ta (s) (s)][oHH((s)llgg 1/
V.. V.R(ss (a-mot))))
SES
17

---

452 Applying the first assumption in Condition with f: f:a R(s,a) and f a V VaR(s, a) belonging FF we have, for each E
453
MI Von (Ho(S), - Ros))o(s)) 0 and
|/ Vo, a)) R. a) (e 0.
454 Moreover, for each S. o (s) n-000
dua ( and Ved (s) n Vodto (s) (by Lemma 2).
455 and V (o) oc, so
V VoJno (To Venta (Har]
12000
456
For the second term of the r.h.s of 19). we have
VoJua.., (HO)
VoJ (po)l
V oo -Vod" R(s (o(s))
#ES
Σ #ES
do (s) -d) (s)) (s) Vo oo Va la
Continuity at 0 of d and + V (s) for each S, boundedness of R(s,-). 458 V.R(s,)) and (a(s) implics that
V VoJau.on (1O) - VoJna (po)) n1-00a
0.
459
Hence,
VgJ (TO,0.)) VeJno, V O. n-000
So, + VOJTO (To,r) and VoJ.u, (NO) are continuous 460
lim VoJTo, (T lim VoJ no.o (HO) = V VaJ (10)-
04
461
Proof of Theorem
We will use the two-time-scale stochastic approximation analysis. We let the policy parameter 0, fixed as 0, when analysing the convergence of the critic step. Thus we can show the convergence of towards an wa depending on 0, which will then be used to prove the convergence for the slow time-scale.
465
465
486
Lemma 3. Under Assumptions
5 the sequence w| generated from
is bounded a.s., i.e.
sup, || < a.s., for any E N.
468
The proof follows the same steps as that of Lemma B.1 in the PMLR version of Zhang et al. 2018
Lemma 4. Under Assumption 5 the sequence (Ji) generated as in is bounded a.s, iee, sup, J <
469
470 00 a.s. for any E N.
The proof follows the same steps as that of Lemma B.2 in the PMLR version of Zhang et al. 201 0
472 The desired result holds since Step and Step 2 of the proof of Theorem 4.6 Zhang et 2018
473 can both be repeated in the setting of deterministic policies.
474 Proof of Theorem 5
475 Let F..2 (0,, ST, S t) filtration. In addition, we define
H s, w) Volla(s) V (a
(0, 8) H(O, 8, wo):
h(0) = Exnds (H. s)
18

---

478 Then, for each A E ④ we can introduce ve S + R the solution to the Poisson equation:
(I- PO) vol.) = (() - h(0) 477 that is given by (0) - E120 E P [[ sx)) h(0)]so so s) which is properly defined
Ex>0
478 (similar to the differential value function V).
With projection, actor update
5
becomes
l = r [0, + Bo.t H (0,, St. wr]]
(20)
- [0. + (o,) - Bo,t (h((0)) (0,,, - Bu,s (H( 86) (O0,, 81, wx))
r [0c + ((,))(00)) + Ba, ((I - pot))oo (8t)) + A/]
= I [0c + Ba,ch(0: + 8,, (vo, (st) 1/. (st+1)) + Bo, (vol (8(+1) - (o)vo((st)) + [0,
r [0. B (h(O,) + A7 + 13 + A7)]
480 where
A! HO,,, 82, wi) H (0c, 81),
A Vo, vo, (st) (8(+1),
A = Vo, vo, ($1+1) - p vo (s)).
For < 1 we have
A
Bo (vo, (8k) - Voo (8k+1))
Bo k (vog (8K) - vox (8k++1)) + k=r
Σ
Bo (vo (ok+1) - Von (8R+1))
(Bo
(),,x) vox (82241) + Bo, Vo, (8r) - Bo, uo (8r) +
kk
k=r
(1)
(2)
ck
+
ck + 1r,
where
9k = (Bo - Bo, VBN (8k+1);
(1)
(2) Bo, (vor.) (sk+1) vo, (8k+1))
T Be, vo, (8x) B0, vo, (st).
Lemma 5. Ei=b A converges a.s. for t + 00
483
484
Proof of Lemma
Since (s) is uniformly bounded for 0 O, E S, we have for some K > 0
Σ
Ba, Bo.ul
which converges given Assumption 5
486 Moreover, since (s(s)) is twice continuously differentiable, 0 - vo(s) Lipschitz for each 8, and so
we have
Ba [1 (Sx+1) -oa+i (SK+1)|
K² 2
30.b 110 -0+22l
k=
< K 3
82
k=0
19

---

488
Finally, lim |lloeell || = 80.0 11,, (8u) || < 00 a.s.
1+00
Thus, Ex 1..x Alll Ex 1 + - |<2) + Moo converges a.s.
489
Lemma 6. Ei R converges a.s. for t - cc.
490
481
Proof of Lemma 6
We set
1-1
1-1
Ze
Σ k=0
8 (vB (8k+1) 1 plever (sk))
k=0
Since Ze is Fe-adapted and TE [Po, (#e+ [ = p0: vo, (8+), Zr is a martingale. The remaining of the 482
proof is now similar the proof of Lemma 2 on page 224 of Benveniste al. [990).
D
Let (0t) = de / [vi- ( and g(0) = (g'(
( We have
g0())) = (s,) by Si,0.-
SIES
Given (10) 0 + we is continuously differentiable and 0 + Vown is bounded so 0 - we is Lipschitz-contimuuus. Thus - Ei,0 is Lipschitz-cooninnuuss for each 8, E Due to our regularity assumptions, 0 - Vi.,, is also continuous for each N, 8t E S. Moreover, O +> ds) is also L Lipschitz continuous for each E S. Hence, 0 g(0) is Lipschizz-cominuous in and the ODE is well-posed. This holds even when using compatible features.
485
498
By critic faster convergence, we have lim; || a. ||= 0 so lim 0.
500
Hence, by Kushner-Clan Clark lemma Kushner and Clark [1978] (pp 191-196) we have that the update in converges a.s. the set of asymptotically stable equilibria of the ODE (12)
20
502
Proof of Theorem 6
503
We use the two-time scale technique: since critic updates at faster rate than the actor, we let the policy parameter Og to be fixed as 0 when analysing the convergence of the critic update.
504
Lemma 7. Under Assumptions 4 and 6 for any i N, sequence {X} generated from is
506
bounded almost surely.
507
To prove this lemma we verify the conditions for Theorem A.2 of Zhang et al.
2018 to hold.
We use (Fe,1 } to denote the filtration with Fr,1 oss,, Cr-1, 0r-1 Fr, t). With X,
[AA) ..... [] critic step ? has the form:
509
Ae11 - (C, @ I) (A+ + Sx,E 3141)
(21)
with V (6tu(ss, (e) ..... 8% a))) RKN, denotes Kronecker product and is
510
the identity matrix. Using the same notation as in Assumption A.1 from Zhang et al.) [2018). we
511
512
have:
h (A(,), st) = -EauT (8/u(ss, a) [Fe.)] = / (P(sss) w(s),a) N))(s),)) do,
Mi+1 -6/0(5e Te)T Easa how(ss a) (FF.)),
V/ (s, da, s)
h ['(Ac) Al.o dz Bx.0- de: where A
Since feature vectors are uniformly bounded for any S and E A, h² is Lipschitz continuous in its first argument. Since, for i N¹, , the r" are also uniformly bounded, E [[| [1, < K
514
515 | I?2) for some K > O. Furthermore, finiteness of [S] ensures that, a.s., [T((A.) h (de,, sx) 11)
K (1 + [IA,P)). Finally, (y) exists and has the form
1oo (y) = -x,
From Assumption I we have that -B.,0 is a Hurwitcz matrix, thus the origin is globally asymptot- 518 ically stable attractor of the ODE : (y). Hence Theorem A.2 of Zhang et al. [2018 applies, which concludes the proof of Lemma]
517
20

---

520
We introduce the following operators as in Zhang et al. (0018:
: R
(2) N ( @ 1) N Σ X
iEN
J (1 11 0 01) RRNN IR KN such that JA = 1 80 (A)-
522
J1 -I=I-J J KR R KN and we note { -1A= (A).
523
524
We then proceed in two steps in Zhang et al. 2018], firstly by showing the convergence a.s. of the disagreement vector sequence {}i,f} zero, secondly showing that the consensus vector sequence
525
( converges to the equilibrium such that (Ax) is solution to (13)
527
Lemma 8. Under Assumptions
7 aadd for any M > O, we have
6
sup |,, 1 1
[oup,ll\elIsMM) 00.
Since dynamic of { described by (1 is similar to (5.2) in Zhang al. 2018 we have
11 A 13
P (1 -1 +22 [| - E(
F()) +
1(1
(22)
529 where P represents the spectral norm of B [ (I 11 C.]. with p E [0, 1) by Assumption
530 Since vi+1 = 5 wsss, az) we have
E
119 = E3
((("(se,, - w(s,, w(s w az) T19
veW
< 2 E
Σ
||r ai)w(ss a.) |1+1|w((ss,a 1 -I 112-111 "
EEN
By uniform boundedness of r(s,-) and woss.)) (Assumptions D and finiteness of S, there exists
532 K1 > 0 such that
E
| 1 12 < Ki IAAl))
533 Thus, for any M > 0 there exists K2 such that, on the {sup S |+ M).
1 (A Fr.1 S K2.
(23)
534 We let Ut = || 1 1 (sup-gellA-l <M)-
Taking expectation over
22 noting that
535 1 (sup [ E (sup leup.<tl1>-lle MA-llerr we get
8ht
B(v+11) <
(B(r:)+2VEB)))) + +2/E(2)) v K2 + K2)
R
which is the same expression (5.10) in Zhang al. 2018 So similar conclusions to the ones of Step 1 of Zhang et al. (2018) holds:
537
sup | 1 (A
00
(24)
and
lim t1T 0 a.s.
(25)
We now show convergence of the consensus vector 6 (Ar). Based on 21 we have
(A++1) = ((C, & () 8 (A.) + A Bx,(0++)) (Ae) + (AL,) + BA, 8 l) + BTAL)))
(Ae) + (h(,,( + Mc+1)
21

---

where h(),, = Be,~ [((+ and M,-1 -
-BaNNT [1
539
Since (de) ((t, 0z) w(st, az) (de), we have
h(),, 81) Earra (F( a (e an) (F)) + Bunxx(u(ss) (A)) w(s (F(11)
so h is Lipschitz-continuuus in its first argument. Moreover, since (A and (F,
542 1 a.s.:
Bus- xxt [((G 8 (31--1 F3. Earr [+
(1T (1
()C @ 1) + A1, F
(I" (B(((())))) & I)BarR 32++ + 8x (L,
N (1 B(C,(Fe,2) & TY [ut+1 + 1 (e.1
Earor (1o+1)) a.s.
So {M& is martingale difference sequence. Additionally we have
EE 1|9 2 2--2 E [1 + A,, [F. 2 | (2t
544
with G2 N-2. Cf 11 C @ whose spectral norm is bounded for C₁ is stochastic. From (33 and we have that, for any M > over the /sepl M), there exists K3, K4 < oc such that
545
244
I1 + Ia. Fr.1] (A S K3 | A 1 [r,,]] (aup, & K4-
548
Besides, since r and w are uniformly bounded, there exists Ks. < such that Ks (1 + 119). Thus, for any M > O, there exists some Ko < such that over the set {sup, A SS M
|I (F.
548
E || ||
12 F S Kg (1 (IA))))
Hence, for any M 0, assumptions (a. 1)- (a.5) B.1. from Zhang et al. 2018 are verified on 549
set (s < M). Finally, we consider the ODE asymptotically followed by (Ax):
(Ax) -x (At) + Ax,0 d"
which has a single globally asymptotically stable equilibrium X E R.K. since BN,0 is positive 552 definite: x B_] A dd". By Lemma 7 supell (Ae) || do a.s., conditions to apply Theorem
551
553 B.2. of Zhang et al. 2018) hold a.s., which means that (Ax) - X a.s. As A 1 X (Ax) + A1 1500
554 and A1t Uas.. we have for each i N, a.s.,
X
B n An, d= +000
Proof of Theorem 7
556
Let Fr.2 = (0,,7 (0,,T: T S 1) be the a-field generated by (0r,T S (), and
G1 = of gi Egyrar [v] F..2.
Ci = Egindr [et (g) - Ch,,, [F.2]
With local projection, actor update
6 becomes
8 = [0] + Bo [vs (i,,, + Bo, + So.
(26)
So with (0.) = Exynet [ut Si, [F.2] and (())(())))))) =
(0)). we have
n((0)) = Σ d' (st) si E.o..
SESS
558 Given (T0. - we continuously differentiable and 0 + Vowg bounded so ~> we Lipschitz- continuous. Thus 0 + Éi is Lipschitz-comtinoous for each s; S. Our regularity assumptions
22

---

ensure that 0 + Vi is continuous for each i E N, E S. Moreover, 8 (s) is also Lipschitz
580
continuous for each S. Hence, 0 + g is Lipschit--ontinnous in 0 and the ODE (12) is
582
well-posed. This holds even when using compatible features.
563
By critic faster convergence, we have lim; [ 11=
Let Mi Ero Ga. Mi is martingale sequence with respect Ft.2- Since
(we)t; (Vadm(,,a)saa and (Va)o(s)): bounded (Lemma 3 Assumption 2 it follows
565
that the sequence { bounded. Thus, by Assumption
Σ, E M| - -Mill [F
566
E. Bi, 568
a.s. The martingale convergence theorem ensures that {M;} converges a.s.
Thus, for any e > 0,
lim P
sup m2
Σ
30
S
26 0.
589
Hence, by Kushner-Clar lemma Kushner and Clark 1978 (pp 191-196) we have that the update in 266 converges a.s. the of asymptotically stable equilibria of the ODE (12)
570
23


Reviews:
[{"review_id": "hxfuHrv3hG", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a solution to learning deterministic policy in the multi-agent RL setting, where local rewards are private to local agents.  Both on-policy learning and off-policy learning are considered in the paper. \nTo do so, the author first extends the policy gradient theorem in MARL for stochastic policy to deterministic policy.\nSpecifically, in on-policy learning, only global Q-function and local action are needed to compute local policy gradient; in off-policy setting, only averaged reward function and local action are needed.\nThe author then propose a decentralized algorithm for learning the global Q-function/averaged reward function. Two-timescale technique is adopted to show the convergence of the proposed algorithms.\n\nStrengths: \n(1) the extension of policy gradient to deterministic policy in MARL (locally observable reward) is interesting and important.\n(2) the decentralized algorithm itself, although similar to prior work in Zhang et al (2018), provide needed guarantee to the algorithm for convergence.\n(3) the paper is well written and easy to follow.\n\nCons:\nThe proposed decentralized algorithm closely mimics the one in the prior work, in addition to its analysis framework.  I hope the authors can provide more details on how the analysis of the algorithm differentiates itself from previous work in different aspects. I am happy to increase my rating if the author can address this issue in their response.", "extra_scores": {}, "extra_text": {}}, {"review_id": "gzk0qib8dVN", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nPros:\n1.\tThe motivation that considers both off-policy and on-policy is interesting and attractable. This work might provide a promising way to address the problem of inefficiency of exploration in MARL. \n2.\tThe convergence of MARL is challenging, and this paper gives a valuable attempt.\n\nCons:\n1.\tThe experiment is insufficient and doubtful, although this paper is convincing in theory, the experiments are not convincing at all. The convergence curves are quite nice, but the authors should compare the results with some other state-of-art algorithms to increase its credibility. \n2.\tThe differences with [Zhang, ICML 2018] are ambiguous. Some definitions and formulas and even algorithms are almost the same as [Zhang, ICML 2018]. \n3.\tThere are lots of format problems. For example, “Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Basar. Fully decentralized multiagent reinforcement learning with networked agents. 80:5872–5881, 10–15 Jul 2018.” In it, I cannot find where this paper is published. Some symbols are used without explanation, e.g., t in Algorithms 1 and 2.\n4.\tThe organization of this paper needs to be polished. In the background section, the authors firstly introduce the optimization problem of maximizing the average reward with the objective $J(\\pi_\\theta)$ on page 2. However, they use $J(\\theta)$ when defining the Q_\\theta function instead of $J(\\pi_\\theta)$ just 3 lines below. This simplification is not noted until Section 3. So the authors should re-organize the paper to make the content more readable.\n5.\tThis paper raises some assumptions when discussing, but neither does it offer a list of these assumptions, nor does it analyze the rationality and influence of them.\n\nQuestions:\n1.\tWhat is the difference between Figure 1 and Figure 2? \n2.\tWhat is the detail of the experiment? \n3.\tHow well do the results compared with [Zhang, ICML 2018]?\n4.\tIn Algorithm 1, why can you draw an action firstly?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "YsSEepb4_jB", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper establishes the asymptotic convergence of on- and  off- policy DPG in the multi-agent setting under some assumptions. Overall the paper is well written and easy to follow. Given the practical usefulness of DPG, I think the result in this paper is somehow meaningful to the community.\n\nHowever, the paper has the following issues:\n(1) Since this paper is a theoretical paper, the assumptions are very important to evaluate the signficance of the main theorems. Thus, the assumptions should be moved to the main body of the paper.\n\n(2) The projection is a practical issue that has been criticized by many researchers in the RL community. Although it is necessarily to make this assumption when handling two time-scale algorithm with time-varying MDP, it can be avoid by adopting other updating structures such as nested-loop, mini-batch two time-scale, etc. Or can the author provide an upper for such a projection radius so that the algorithm can at least be implemented in practice?\n\n(3) Although this paper is a theoretical paper, only considering multi-agent bandit in the experiement is not sufficient to verify the theoretical results in this paper. I suggest the author to consider some RL settings to make the experiment results stronger.\n\n(4) The current muti-agent setting in this paper is not that practical, as too many variables are requied to be globally observable.\n\n(5) The update at time step t required the knowledge in step (t+1), which could introduce some pratice issues as this paper focus on online update. Can the author propose some potential idea to fix this issue?\n\n=== After rebuttal ===\n\nSince the technical contribution of this paper is not significant enough, I will keep my score as weakly reject.", "extra_scores": {}, "extra_text": {}}, {"review_id": "WDe-YuqWFm", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper offers a comprehensive theoretical treatment of deterministic policy gradients in a multi-agent setting, working out several key results:\n* existence and explicit formulas for the multi-agent deterministic policy gradient in off and on-policy settings;\n* convergence of stochastic policy gradients to deterministic ones as policy variance converges to zero; \n* convergence of multi-agent deterministic actor-critic algorithms.\n\nThis paper is very well-written and easy to follow, although technically there is not much to expose here, as most of the paper consists of statements of results. I did not check all the math thoroughly, but there does not seem to be any cause for suspicion as far as I can tell. Related work is sufficiently well presented. \n\nI think that the topic of deterministic policy gradient in a multi-agent is sufficiently interesting and having the foundational results worked out in a single reference is a valuable contribution. The paper is incremental in a way that the deterministic results seem to be extensions of known stochastic results along the lines of well-understood techniques. If any unexpected challenges had to be addressed in order to derive these results (e.g. developing new techniques), this has to be made clearer in the paper. \n\nOverall I think this is a solid paper.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "CvrYhdPjzdQ", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Clarity: The paper is well written. The following require some clarifications:\n1) $\\tilde{a}$ variables are defined by never seem to be used in Algorithm 1, why?\n\n2) In the  off-policy setting (Theorem 1) letting $\\mathcal{N}=1$ does not recover the previous result by Silver et al. (January 2014a). This is perhaps due to the fact that eq(1) of this paper has $\\bar{R}$ in its objective and eq(14) of Silver et al. (January 2014a) has $Q^{\\text{target-policy}}$ instead. It would be great if the authors clarify why the two objectives are different. If my understanding is correct, in the off-policy setting, we are still interested in the maximising the reward with respect to target policy, and the restriction is that the samples are from the behaviour policy.  \n\n\nQuality:\n1) Strength: The theoretical results are stated clearly and detailed proofs have been provided. But for the off-policy case, other results seem to be correct.\n2) Weakness: The experiments are on a toy domain. The experiments demonstrate that the proposed algorithms indeed converge as expected. However, the experiments do not add any further insights such as a) what happens when we change the communication matrix $C$? b) What happens when the reward structure varies a lot across the agents?  c) what happens when different agents start from different parts of the state space. In short, the experiments have to be carefully thought out to cover the entire range so as to emphasise the multi-agent flavour. As it stands, the current version of the paper spends too little space (only about 4 lines) has been allocated for the experiments. \n\n\nNovelty:\nThe deterministic policy gradient result is new. The off-policy case seems to have some issue (see above). While the result in itself is new, it is not clear whether it follows trivially from prior results. It would be great if the authors can comment on the this.\n\n\nSignificance:\nThe significance of the current version is limited due to, \n1) the lack of experiments, \n2) the possibility that the new results could be obtained as trivial extension of prior work (Zhang ICML,2018 + Silver et al. (January 2014a)). (I am not saying that this is true, authors can clarify)\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper offers a direction for mult-agent RL that builds on results for actor-critic methods [Zhang, ICML 2018], extending that work to address deterministic policies.  The authors establish convergence under a number of assumptions.   Both on-policy setting and off-policy settings are treated.  The reviewers point out several concerns and the consensus seems to be that, while the direction looks promising, the paper deserves further work.

Decision: Reject