A Law of Iterated Logarithm for Multi-Agent Reinforcement Learning
Authors: Gugan Thoppe
Bhumesh Kumar
Venue: NeurIPS 2021 Poster (2021)
Keywords: multi-agent
distributed
stochastic approximation
almost sure
convergence rates
row stochastic
gossip
law of iterated logarithm
concentration
martingale

Abstract: In Multi-Agent Reinforcement Learning (MARL), multiple agents interact with a common environment, as also with each other, for solving a shared problem in sequential decision-making. It has wide-ranging applications in gaming, robotics, finance, communication, etc. In this work, we derive a novel law of iterated logarithm for a family of  distributed nonlinear stochastic approximation schemes that is useful in MARL. In particular, our result describes the convergence rate on almost every sample path where the algorithm converges. This result is the first of its kind in the distributed setup and provides deeper insights than the existing ones, which only discuss convergence rates in the expected or the CLT sense. Importantly, our result holds under significantly weaker assumptions: neither the gossip matrix needs to be doubly stochastic nor the stepsizes square summable. As an application, we show  that, for the stepsize $n^{-\gamma}$ with $\gamma \in (0, 1),$ the distributed TD(0) algorithm with linear function approximation has a convergence rate of $O(\sqrt{n^{-\gamma} \ln n })$ a.s.; for the $1/n$ type stepsize, the same is $O(\sqrt{n^{-1} \ln \ln n})$ a.s. These decay rates do not depend on the graph depicting the interactions among the different agents. 

A Law of Iterated Logarithm for Multi-Agent Reinforcement Learning
Gugan Thoppe
Bhumesh Kumar
Computer Science and Automation
Electrical and Computer Engineering University Wisconsin at Madison
Indian Institute of Science
Bengaluru, Karnataka 560012, India perppe@iss.ac.... in
Madison, WI 53706, USA bkumar@wisc.
Abstract
In Multi-Agent Reinforcement Learning (MARL), multiple agents interact with common environment, also with each other, for solving shared problem in sequential decision-making. It has wide-ranging applications in gaming, robotics, finance, etc. In this work, derive novel law of iterated logarithm for family of distributed nonlinear stochastic approximation schemes that is useful in MARL. In particular, our result describes the convergence rate almost every sample path where the algorithm converges. This result is the first of its kind in the distributed setup and provides deeper insights than the existing ones, which only discuss con- vergence rates in the expected or the CLT sense. Importantly, our result holds under significantly weaker assumptions: neither the gossip matrix needs be doubly stochastic nor the stepsizes square summable. As an application, we show that, for the stepsize n with 7 E (0, 1), the distributed TD(O) algorithm with linear function approximation has a convergence rate of O(vn~> In a.s.; for the l/n type stepsize, the same is O(vn-1 In In a.s. These decay rates do not depend on the graph depicting the interactions among the different agents.
Introduction
Can a machine train itself the same way an infant learns to sit up, crawl, and walk? That is, can device interact with the environment and figure out the action sequence required to complete a given task? The study of algorithms that enable such decision-making is what the field of Reinforcement Learning (RL) is all about [40]. In contrast, the mathematics needed to analyze such schemes is what forms the focus in Stochastic Approximation (SA) theory [2, 4]. More generally, SA refers to iterative scheme that helps find zeroes optimal points of function, for which only noisy evaluations are possible. In this work, we analyze family Distributed Stochastic Approximation (DSA) algorithms [24] that is useful in Multi-Agent Reinforcement Learning (MARL) [22, 51].
In the MARL framework, we have multiple agents learners that continually engage with shared environment: the agents pick local actions, and the environment responds by transitioning to new state and giving each agent a different local reward. Additionally, the agents also gossip about local computations with each other. The goal of the agents is to cooperatively find action policies that maximize the collective rewards obtained over time. Algorithms useful in this endeavor have found empirical success in domains diverse gaming [28], robotics [29], autonomous driving [35], communication networks [21], power grids [34]. and economics [19]. However, theoretical analyses of such schemes are still very minimal, and this is what this paper aims to address.
For the purpose of analysis, MARL methods are often viewed as special cases of DSA algorithms. The archetypical form of DSA scheme with m distributed nodes can be described as follows. Let G
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

be a directed graph representing the connections between these nodes, and W = (W;,) E [0, 'm a matrix whose i--th entry denotes the strength of the edge j + i. it assumed that W is compatible with 9, i.e., Way > 0 only if + i E g. Then, at agent i, the above scheme (written as row vectors) has the update rule
In (i)
Σ Wijzn(i + (n))) + Mn+1(1),, JEA
n O,
where In E mR the joint estimate of the solution at time n, its j-th row, i.e., In (j) denotes' the estimate obtained at agent j. NV, represents the set of in-neighbors of node i in G. an is the stepsize, h; _m + R4 is the driving function at agent i, and Mi+ E I is the noise in its evaluation at time n. This update rule has two parts: a weighted average of the estimates obtained by gossip and a refinement based on local computations. Clearly, the joint update rule of all the agents is
In+1 = In + an [(())) + Mn+1]:
where Mn+1 is the m x d matrix whose i-th row is Mn+1 (i), and h is the function that maps x E 1mxd the m x d matrix whose i-th row is (z).
Two important points about the above framework are as follows: i.) we allow h; to be a function of all of F. and not just of z,n (1), is commonly assumed, and ii.) the computations at different nodes in the above setup run synchronously on a common clock.
Related Work: We now give summary of relevant theoretical results from the DSA and MARL literature. For ease of discussion, we categorize them into i.) asymptotic and ii.) finite-time results.
The asymptotic ones mainly concern almost sure (a.s.) convergence [42, 3. 26. 24, 15, 52, 50, 39, 18]. The first four papers here provide convergence guarantees for a broad family of nonlinear DSA algorithms. The other articles also do the same, but in context of specific MARL schemes such as distributed Q-learning, distributed actor-critic methods, distributed TD methods, and their off- policy variations. Two other kinds of asymptotic results also exist in the literature. The first is the CLT shown in [27] for the average of estimates obtained at different nodes in a generic DSA scheme. The other is the convergence in mean result obtained in [48] for a distributed policy gradient method.
literature, in contrast, majorly talks about expectation bounds. Assuming there exists a unique v. that solves Σ (x) = 0, these results describe the rate at which B||E, - x. decays with n. Notable contributions for DSA here are [49, 44]. Compared to ours, these look at a slightly different setup: the measurement noise at each node has a Markov component in place of a martingale difference term. In this new setup, [49] shows that, for any sufficiently small but constant stepsize c, the expected error decreases linearly to ball of radius O(v (n(1/c)) On the other hand, [44] deals with the case where h is additionally non-convex and shows that B|| - xxx = On VInn), which is comparable to the best known bound in the centralized setting.
Finite-time
Expectation bounds in the MARL framework primarily concern policy evaluation methods [10, 11, 37, 5]. The first three papers here deal with the distributed TD(0) method. These show that result similar to the one in [49] holds for this method under constant stepsizes. In contrast, when a, is of the 1/n type, it is proven that El|,z, in [5] for two distributed variants of the TDC method. There are also some other works that derive finite-time bounds [45, 9, 46, 54, 13, 36. 33, 53), but we do not discuss them in this paper since the algorithms proposed there do not fit the update rule given in (2).
x. 221l = ((1/ /n). Similar bounds have also been derived
The different finite-time results, as also the asymptotic CLT, do provide insights into the rate at which an iterative method converges. However, there are some significant issues with these studies. First, except [27], all others require the gossip matrix to be doubly stochastic, at least in the mean. While this assumption simplifies the analysis, also severely restricts the communication protocol choices. In fact, as pointed out in [27]. this condition even limits the use of a natural broadcast node, one that transmits its local estimate to all the neighbors without expecting all of them to respond. Second, these works only talk about convergence rates in the expected or the CLT sense. By their very nature, these results do not reveal much about the decay rates along different sample paths. Finally, all current results, including the ones on convergence, only apply to constant or squmabesummable stepsizes. Nothing is known about the alowly-decaying non-square-summal
By default, all our vectors are row vectors. We use for conjugate transpose.
2

---

ones, which are generally preferable since they give similar benefits as constant stepsizes and, often, also guarantee convergence. Note that such issues also plague much of the distributed stochastic optimization literature [47, 38, 20, 16, 32, 31].
Key Contributions: The highlights of this work
follows.
1. Law of Iterated Logarithm (LII.): We derive a novel law of iterated logarithm for the DSA scheme given in (2). That is, for suitably defined Jur show that lim supla, Intn+1] Intn+1l-1/2|1r,,, x.1l || - C a.s. every sample path in the event
E(x.)) == { + x..)
(3)
Here, C 2 0 is some constant and fn = k= og. Also, the norm that we work is the operator norm. In particular, for any x E Cmmxd
-ko
nn
|||||| :=
sup VEC",,ECC
(uuzo'I :
|||||| = ||a|| = 1}.
(4)
This result is the first of its kind in the distributed setup. Further, as discussed in Remark 2.3 later, it provides deeper insights about the asymptotic behavior of (zn)n20 than other existing results, which only discuss convergence rates in the expected or the CLT sense.
Analysis and Gossip Matrix: The above result is obtained via a new approach we develop here for analyzing DSA schemes. Let Tm be such that x W = and let
Q = 1'T,
(5)
where 1 T. denotes the vector of all ones. Then outline of our approach is that we express In 2g as sum of T (z,, I=) and QI, and, thereafter, analyze each summand by treating its update rule as a separate SA scheme. This contrasts the usual approach (c.g.. [27, 10, 11]) where the error is split into (11//)((z, - xx) and (I (1-1't 111/m) In fact, this is the main reason why, unlike other existing results, ours does not require that the gossip matrix be doubly stochastic.
3. Concentration Inequality and Stepsizes: We also improve upon an existing concentration result ([12, Corollary 6.4.25)) for a sum of martingale differences; see Lemma 4.6. Specifically, by modifying the original proof from [12], we show that the result stated there actually holds under a broader set of conditions. The key benefit of this is that, unlike other related results, our LIL result does not require that the stepsize sequence be square-summable.
4. MARL Application: We use our theory to prove law of iterated logarithm for the distributed TD(0) algorithm with linear function approximation. This is the first such result in MARL.
The rest of the paper is structured follows. In Section 2, we formally state our main result along with all the assumptions needed. We also pinpoint the new insights that our result provides. In Section 3, we give demonstration of how result can be applied in the MARL setup. In particular, there we talk about the distributed TD(0) algorithm with linear function approximation and prove that it indeed satisfies all the assumptions of our main result. Section 4 has two parts. In the first part, we state some key intermediate lemmas and then use the same to derive our main result. The latter part, in contrast, focuses proofs of these intermediate results; note that we only sketch their proofs here and leave the details to the appendix. Finally, in Section 5, we conclude with summary of our findings and discuss some interesting future directions.
Contents:
2 Assumptions and Main Result
Throughout this work, we assume that the following four technical assumptions, i.e., A4, hold for the DSA scheme in (2).
A₁. Property of the Gossip Matrix: W is an irreducible aperiodic row stochastic matrix.
This condition implies there exists unique vector π E 18 such that
J W π
(6)
Throughout, C denotes a generic constant. Its value could be different each time it is used: in fact, it could be different even in the same line.
3

---

Accordingly, based on [24, Theorem 11, one would expect (2) to eventually converge to an invariant set of the m-fold product of the d-dimensional ODE
((()
Σ n,,, (1yb()))==(((11
By m-fold product, we refer to the dynamics in Ruxd where each row individually satisfies (7). A natural invariant set of this dynamics is S = (1'y y:: :::yy: [R C RRxxd With this in mind, let
F, 1 y. E,
where y. E Rd is asymptotically stable equilibrium of (7). Notice that don't assume y. to be the only attractor of this ODE.
We remark that our main result concerns the behavior of the DSA scheme on the event E Exr.) where v. as defined above and (xx,) ) is as defined (3).
Ag. Nature of near I,: There exists neighbourhood U of a, such that, for x E U,
h(x) -.)
+ Q(B f2(x)),
where A E paxd is such that yAv' > 0 for all y # 0, B E Rmxd is some constant matrix, f2 u - mmxd is some arbitrary continuous function, while fi + pmxd is another continuous function that additionally satisfies
(1'm((())) O(1 -x.)))))))) as I Txi
(10)
for some a 1.
Note that A2 is generalization of Assumption (A1) in [30]. As in [30], this also is local in nature: it only prescribes specific behavior for h close to x.. Furthermore, this condition ensures that the driving function (t) (7) equals - (x x=)A + x fff(()) (x);; the first term the linear part while the second term represents the nonlinear portions. Separately, observe that Qh(x)- = Q(B + f2(z)). This plays no role in (7); hence, conditions on B and f2 are minimal. We now construct a family of examples to show that A2 broadly holds. The simplest member in this family is h(x) = B xA, where B and are as defined above". Clearly, if b(i) and sii) are i-th rows respectively, then the i-component function here is (x(2)) b(i) x.) The fact that the scaling matrix A is the same for each is crucial for A to hold. Also, observe that this function does not depend π. The other members of the family are obtained by adding various n-dependent nonlinear perturbations to this simple setup, i.c., by making different choices" for fi and f2.
and x,
As. Stepsize Behavior:
There exists some decreasing positive function defined on [0, oo) such that the stepsize an, a(n). Further, is either of Type 1 or Type 7.
(a) Type 1: a(n) = coo/n for some ox > 1/(2Amin), where
Amin == min (A) A spectrum (A)}
(11)
with (()) denoting the real part of X; (b) Type 7 The function a is differentiable and its derivative varies regularly with exponent 7 where 0 < < 1.
The regularly varying condition above implies that do(xx) da = = L(x) for some slowly varying
function I,, e.g., L(x)= = C' for some C >> O, or L(x) = xInx)" for some 7) E RR. Thus, examples of on here include Cn -Y and n~ (0 n)",, which are non-suuar--sumaable for y E (0,1/2).
A4. Noise Attributes: With F,, = a (0o, MI...., Mn). and E(x.), as in (3), the following hold.
(a) [EMM+ [F)) = 0 a.s.
A verification of all the conditions mentioned in Ag for l(()) = B A has been done in Section 3; there also discuss usefulness of this function in the context of policy evaluation MARL.
For example, we can let fi( = (1(((2 xI)) and fz(x) = =2A + 92(x), where 91 RR + mxd is such that, 0, || (z)ll ([Il=1)) for some > 1, and g2 arbitrary continuous function.

---

(b) There exists C 2 0 such that [[QM++1l| & C (1+ [QQ(2, - zx)ll) a.s. on (z,).
(c) There is non-random symmetric positive semi-definite matrix M Rdddd such that
lim E(M MMMM+1111111 Fr) = M a.s. on E(x)). To 22000
(12)
(d) There exists b > 2 such that supn20 B B[ 1 < 00 a.s. on E(x.).
These noise conditions extensions of the standard assumptions in the SA literature [30, 25, 4). Our main result can now stated as follows. This generalizes Theorem from [30].
Theorem 2.1 (Main Result: Law of Iterated Logarithm), Suppose A1...., As hold and 2/b if is of Type y. Then, there exists some deterministic constant C z such that
lim sup[a,, In 1n 112 | x. C a.s. on Exx).
This result is called a law iterated logarithm since its proof crucially relies on Lemma 4.6, which indeed is law of iterated logarithm for a sum of scaled martingale differences. We end this section with some important comments about our main result.
Remark 2.2. Our result shows that, a.s. on Exx)), I|nn - x. is O(vn In In the Type case, and O(vn n)) in the Type r case. Note that, since we require Y > 2/b, our result applies for smaller values of only if (4.(d) holds for sufficiently large b.
Remark 2.3. Our result provides deeper insights than the convergence rates that exist in the DSA/MARL literature. For this discussion, we suppose PPE[(z.) = As mentioned in Section 1, the existing results are of two kinds: finite-time expectation bounds and the CLT. Indeed a finite- bound has several benefits and is not directly comparable to asymptolic result. Nevertheless, an expectation bound only describes the average behavior, while ours characterizes the decay rate on almost every sample path. In fact, if we compare just the decay rate obtained in our result in the Type 1 case with that obtained in [10, 111, which show El|x, xxlll O O(VInn/ Vn), then ours is tighter (it has ln ln n in place nn). Furthermore, while a CLT can at the best show that
lim sup Oep. 1/ - x= = oo a.s., our result is more precise in stating that the expression becomes bounded if it is divided by an additional /Infu f term.
3 Application to Reinforcement Learning
We apply result here to variant of the distributed TD(0) algorithm [10. 11] with linear function approximation. This method is useful for policy evaluation in MARL. The discussion here is divided into the following three parts: i.) setup, ii.) objective and algorithm, and iii.) analysis.
Setup: We consider a distributed system of m agents modeled by a Markov Decision Process. This can be characterized by the tuple (S, {. P, (R:). 7, 9). Here, S = {1,.... L} is the global state space, Ui and R, are the set of actions and the reward function agent i, respectively, P describes the transition probabilities, is the discount factor, and G = (V, E) is directed graph that represents the connectivity structure among the m agents.
Let N₁ and W be as in (I), We assume that this W satisfies the conditions in A.. Then, for this matrix, there is unique vector ग (T;) satisfying (6).
Let μ4; be the stationary policy of agent and let == =Wz).. Also, let u(aas) = (x(g be the probability for choosing the joint action = (a.) E 24, This policy then induces Markov chain on S, which we assume is aperiodic and irreducible. Therefore, it also has a unique stationary distribution and denote the same by & R44
At each step, the above system evolves as follows. First, each agent sees the current state s and applies an action a; U4 sampled from (4(+ss). Based on the joint action a, the system then moves to new state 5. Equivalently, the joint action a and the state 3 can be seen as samples of ((-(s) and P(- a), respectively. Finally, each agent i receives an instantancous reward R; a, 3).
Objective and Algorithm:
The goal of the multi multi-agent system cooperatively estimate the value function J E RR corresponding to μ. This is defined as the solution to the Bellman equation
(M = E Σ ne Rs ()) 73) 8 SES,
5

---

where the expectation is over pl-ls) and ă P(-|s, a). This expression differs from the ones in [10, 11], in that, the coefficients π; here is replaced by 1/m there. When L is large, estimating J directly is intractable. An alternative then is to make use of linear function approximation. That is, for some d, choose a feature matrix + E RRdd with full column rank. And then, with ((s) denoting the s-th row of Φ try and find 0 E Ee such that Js)s o(s) for all E.
The distributed TD(0) algorithm is helpful in this latter context. Let (sn: ans 3,), n 2 0, be IID samples of (s, a, 8), where s ~ <p(-), a ~ u(-ls), and P(-ls, a). Then, at agent this distributed algorithm has the update rule:
0 (n+1
Σ Woyn(() + (zx((1)) (n()))n))
(13)
JEN
where (1) = Rsn,, On, (s)) E Rd and A,, =
yo' (3)()))((s)))) E Rdxd.
Analysis: We first express the update rule given in (13) for different i in the standard DSA form. Let A = [[A,] and B [[Bn]. where B, Rm is the matrix whose i-th row b, (1). Both A and B do not depend on n since (5,,, an 8,), n 2 0, is IID. Next, for 2 0, let on E Rm be the matrix whose i-th row is (1). Then, (13) for different i can be jointly written as shown in (2) for
Mxx)= = B xA
and
Ma41 (B, B) In (Ap A)-
(14)
Next, we look at the limiting ODE given in (7). In our case, this has the form j(1) = B - y(1) A. Now, A is known to be positive definite [40], i.e., 0A0' > O for all 0 * 0. Hence, it is invertible and the real parts of all its eigenvalues are positive, i... -A is Hurwitz stable. This then shows that 0, BBA is the unique globally asymptotically stable equilibrium for the above ODE.
We now verify the assumptions stated in Section 2. A1 trivially holds due to assumptions on W. For A2, let fx) = 0 and fz(z) = - =xA for x E Im Further, let I, = 1'e, Then, h(x) = -1 - )A + (I - [B + fz(x))) as desired. In order to satisfy As. we simply choose a stepsize sequence that fulfills one of the criteria mentioned there.
It now only remains to establish As. Let Fn be defined there. Then, part (a) follows from the definitions of A and B and the fact that (8n, On 8n) is independent of the past. On the other hand, part (b) can be shown by building upon the arguments used in the proof of [7, Lemma 5.1]. Next observe that, since (sn: an 3n) is independent of the past, the only quantity that is random in 11M T Ma+1
En. Also, trivially, E[M n n MM is a symmetric positive semi- definite matrix. Therefore, on the event E(r.), it is easy to see that part (c) holds as well. Finally, notice that M| S C(1+ + ||,, II) for some C 2 O; this follows as in part (b) above. Hence, on (x.,), sup B[[[= M || [.] < co a.s. for any b 2 O. This verifies part (d).
Thus, Theorem 2.1 holds for the distributed TD(0) algorithm with linear function approximation.
4 Theoretical Analysis: Proof of the Main Result
We now turn to the technical details of our analysis. With Q as in (5) and x, as in (8), observe that 1'xr.- = x. and, hence, H, X_ = 1'T(2, - xx) + Qr,,. We refer to the first term in this decomposition as the agreement component of the error and the second as the disagreement component. This decomposition differs from the standard approaches [10, 11, 27], wherein In, split into (1'1) (zn x.) and (II (1'1 (1/m)))m... In fact, the success of our approach strongly hinges on this novel error decomposition.
The rest of the section is organized as follows. We first state our bounds for the two terms in our decomposition. Using these bounds, we then provide a formal proof for Theorem 2.1. Thereafter, we sketch the proofs of these intermediate bounds, leaving the details to the appendix.
'The IID assumption is standard in literature [7, 23, 41,43] and is needed to ensure that the update rule only has martingale noise. Otherwise, the update rule will additionally have Markovian noise, the analysis of which beyond the scope this paper. The good news though is that, as shown in previous works [14, 10, 11j. the asymptotic behaviours with and without the Markovian noise are often similar.
The matrix A is usually defined to be the transpose of the expression we

---

Lemma 4.1. (Agreement Error) Almost surely on {xx,),
lim sup || (Jin x.).l
S C,
(15)
Van In n+11
where C 2 0 is some deterministic constant.
Lemma 4.2. (Disagreement Error) Let > 0. Then,
||Quıll O (an (lm())))++)) a.s. Exxx).
(16)
Remark 4.3. Up logarithmic factors, the rale which the disagreement decreases the square of the rate at which the agreement error decreases. Thus, the overall convergence rate is essentially dictated by the agreement component of the error.
With these two ingredients at hand, our main result is arrived at via the following short calculation.
Proof of Theorem 2.1. Observe that
|| x-ll S [T, z+)ll I|Q
Also, In Int1+1 is O n) and OInn in the Type and Type 1 cases, respectively. The desired result now easy to see from Lemmas 4.1 and 4.2.
4.1 Bound agreement error [1' s.)il
We first focus on the details of our analysis for the first ingredient, i.e., the agreement error. Let
Mn+1 = Σ ag 1'M41e
(6.12-111144 n 120. 0,
(17)
k=
and
An == 1'T(In Ix)
Un. n
(18)
Clearly, to prove Lemma 4.1, suffices to obtain bounds on the rate which || || and ||A.||| decay. These bounds are stated below, Note that these results are generalizations of Lemmas and 3 from [30]. Specifically, the results there focused on one-timescale stochastic approximation, ours on the other hand handles the distributed case. Furthermore, the quantities of interest here, e.g, Vhas Ans are matrix-vall valued, unlike the ones in [30] which were vector-valued.
Lemma 4.4. Let b be in As. Suppose that either is of Type 1 that is of Type oy with > 2/b. Then, there exists some deterministic constant C 2 such that
lim sup (a,, (atttt+)12 -1/2 |W++il C a.s. on E(x.) n-100
(19)
Lemma 4.5. Suppose Az, Ag and As hold. Then, for any X E (0, Amiu):
[as1155l| |1b8 1)
A 0
e
-EE E Σ aae oa Exuseh
Lase
(20)
a.s. E(x.), where a as in (10), Furthermore,
1. I is of Type 1, then
| O (max(n" Aao ;n 9:.5-155(mm (mnmmm))
a.s. E(x.).
2. If a is of Type y with 2/6 7 1, then
|| = O (a (cn In 1/2 + (or, In )0/2) a.s. on E(x.).
We refer the reader to the Appendix for the proofs of Lemmas 4.4 and 4.5. However, there is point which would like emphasize here. That is, th is sum of scaled (matrix-valued) martingale differences. And, to derive its decay rate, we use the following law of iterated logarithm.
Let LL(x) In In()..

---

Lemma 4.6. For 2 O, let Un+1 - PECK+1. where fent is real-valued martingale differ- ence sequence adapted filtration (Fa): and { sequence of real- scalars, again adapted to (Fn).
Let (Tn), also adapted (Fr); be such that, for n 0, 1ml I Tn and Tn Ek= T Further, assume sup=20 1 S o² for constant o
satisfies nim Tn
Also, let be such that Σn, a.s. Then,
0c and supn2o E [|e+1 [2+2 Fn] < 00
(insup(2T,LLL,,p 1/2 |n+1l a a.s.
(21)
Remark 4.7. The condition En n T
< 00 differs from the one in [12, Corol-
lary 6.4.25]: in that, it includes the additional term [LL(TT)] The impact of this is that longer require to be in (0, 1) as was the case in [12. Corollary 6.4.25]. Instead, 3 can now take any positive value. This is precisely what allows Theorem 2.1 be applicable even when the stepsizes are non non-square summable.
Remark 4.8. The above result goes through even if we have lim sup, Ble S instead of sup I S o²; cf. [30, Result 1].
We now present the proof of 4.1 which is a direct consequence of Lemmas 4.4 and 4.5.
Proof of Lemma 4.1. From (18), observe that
1'' xx)ll || ||
First consider the where is of Type y. From Lemmas 4.4 and 4.5, we have
| x.)ll (a,, Infn+1) 1/2 S C lim O (an + (a,, In (2) (o-1)/ C, 2=000
lim sup 10
where the last display holds because limn On 0, lim On Intat1 0, and 1.
Next consider the case where a is of Type Again, from Lemmas 4.4 and 4.5, we get
['T(EA - -I.]l SC + sim O max(n - Ado; n 8;n 1.5 (In n) ) +a/2
lim sup
= C,
n-+00 (a,, In 122
(n- 1/2
where the last display holds because Xoo and a > 1.
The desired result now follows.
4.2 Bound on disagreement error [|Qra]]
We now turn to the detailed analysis of the disagreement component of the error. Let
Xat1 = LayWa-jp QM (1m-1 (()1)- n 2 1,
(22)
1=0
and
T= QI Xx: n20 0.
(23)
Note that Xx represents the cumulative noise in Qun It is also easy to see that
Xa+1 = e and + an M..QMn+h
2 0.
(24)
We now state our bounds for x!x and ||T,|| and do not have analogues in the one- mie-immee analysis.
||. Note that Xa and r, are peculiar to the DSA setup
Lemma 4.9. Let 8 0. Then.
[1x++1|| O (Ian)))
E(x,)
(25)

---

Lemma 4.10. Almost surely on (x.), a[T+ = O (an)
(26)
We refer readers the Appendix for proofs of Lemma 4.9 and 4.10. The overall disagreement emoor can now be bounded as shown below.
Proof of Lemma 4. Observe that
1|Qz,11 S |[T Ilxell.
Using lemmas 4.9 and 4.10, we then have
||2,I1| O (an) O (an (Iam)ltt)) =0 (an (an()))))))
as desired.
5 Discussion
We derive a novel law of iterated logarithm for family of nonlinear DSA algorithms that useful in MARL. This law can also be seen asymptotic a.s. convergence rate result. It is the first of its kind in the distributed setup and holds under significantly weaker assumptions. Our proof uses a novel error decomposition and a novel law of iterated logarithm for sum of martingale differences.
While our DSA framework is fairly general, key limitation is that the scaling matrix (i.e., A) in each component function h; needs to be the same. It would be interesting to see if our approach can be extended to cover the general case [48] where the scaling matrices also depend on i. Another intriguing future direction is the setting with dynamic communication protocols, wherein the gossip matrix also evolves with time [10, 11]. third direction that of two-timescale DSA schemes [8, 6]. On the MARL side, important algorithms like distributed Q-learning [17] and its variants need more careful analysis and we believe our techniques would be instrumental for this as well. Finally, would like to study the effect of momentum in MARL algorithms [1].
Acknowledgments and Disclosure of Funding
We would like to thank Prof. Vivek Borkar for suggesting this exciting problem. We would also like thank the anonymous reviewers for providing helpful and constructive feedback the pa- per. Research of Gugan Thoppe is supported by IISc's start up grants SG/MHRD-19-005. and SR/MHRD-199-0440.
References
[1] Konstantin Avrachenkov, Kishor Patil, and Gugan Thoppe. Online algorithms for estimating change rates web pages. arXiv preprint arXiv:2009.08144 2020.
[2] Michel Benaïm. Dynamics of stochastic approximation algorithms. In Seminaire de proba- bilites XXXIII. pages 1-68. Springer. 1999.
[3] Pascal Bianchi, Gersende Fort, and Walid Hachem. Performance distributed stochastic ap- proximation algorithm. IEEE Transactions Information Theory, 59(11):7405-74) 2013.
[4] Vivek S Borkar. Stochastic approximation: dynamical systems viewpoint, volume 48. Springer, 2009.
[5] Ziyi Chen, Yi Zhou, and Rongrong Chen. Multi-agent off off-policy td learning: Finite-time analysis with near-optimal sample complexity and communication complexity. arXiv preprint arXiv:2103.13147, 2021.
[6] Gal Dalal, Balazs Szorenyi, and Gugan Thoppe. A tale of two-timescale reinforcement learn- ing with the tightest finite-time bound. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34(04), pages 3701-3708, 2020.

---

[7] Gal Dalal, Balázs Szörényi, Gugan Thoppe. and Shie Mannor. Finite sample analyses for td (0) with function approximation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[8] Gal Dalal, Gugan Thoppe, Balázs Szörényi, and Shie Mannor. Finite sample analysis of two- timescale stochastic approximation with applications to reinforcement learning. Conference On Learning Theory, pages 1199-1233. PMLR, 2018.
[9] Dongsheng Ding, Xiaohan Wei, Zhuoran Yang. Zhaoran Wang. and Mihailo R Jovanovic. Fast multi-agent temporal-difiin difreeecefee learning via homotopy stochastic primal-dual method. In Optimization Foundations for Reinforcement Learning Workshop, 33rd Conference on Neural Information Processing Systems, 2019.
[10] Thinh Doan, Siva Maguluri, and Justin Romberg. Finite-time analysis of distributed td (0) with linear function approximation on multi-agent reinforcement learning. In International Conference on Machine Learning, pages 1626-1635, 2019.
[11] Thinh T Doan, Siva Theja Maguluri, and Justin Romberg. Finite-time performance of dis- tributed cemporal-differentt learning with linear function approximation. SIAM Journal on Mathematics of Data Science, 3(1):298-33) 2021.
[12] Marie Duño. Random iterative models, volume 34. Springer Science & Business Media, 2013.
[13] Paulo Heredia and Shaoshuai Mou. Finite-sample analysis of multi-agent policy evaluation with kernelized gradient temporal difference. In 2020 59th IEEE Conference on Decision and Control (CDC), pages 5647-5652. IEEE, 2020.
[14] Maxim Kaledin, Eric Moulines, Alexey Naumov, Vladislav Tadic, and Hoi-To Wai. Finite time analysis of linear two-timescale stochastic approximation with markovian noise. In Conference on Learning Theory, pages
PMLR, 2020.
[15] Soummya Kar, José MF Moura, and H Vincent Poor. QD-learning: A collaborative distributed strategy for multi-agent reinforcement learning through consensus + innovations. IEEE Trans- actions on Signal Processing, 61(7):1848-188 2013.
[16] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized sgd with changing topology and local updates. In International Conference Machine Learning, pages 5381-5393. PMLR, 2020.
[17] Martin Lauer and Martin Riedmiller. An algorithm for distributed reinforcement learning in cooperative multi-agent systems. In In Proceedings of the Seventeenth International Confer- ence on Machine Learning. Citeseer, 2000.
[18] Donghwan Lee, Hyungjin Yoon, and Naira Hovakimyan. Primal-dual algorithm for distributed reinforcement learning: distributed gtd. In 2018 IEEE Conference Decision and Control (CDC), pages 1967-1972. IEEE, 2018.
[19] Jae Won Lee and Byoung- -ak Zhang. Stock trading system using reinforcement learning with cooperative agents. In Proceedings of the Nineteenth International Conference Machine Learning, pages 451-458. 2002.
[20] Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decen- tralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent. arXiv preprini arXiv: / 705.09050 2017.
[21] Michael Littman and Justin Boyan. A distributed reinforcement learning scheme for network routing. In Proceedings of the international workshop on applications of neural networks to telecommunications pages 55 61. Psychology Press, 2013.
[22] Michael L Littman. Markov games as framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pages 157-163. Elsevier, 1994.
[23] Bo Liu, Ji Liu, Mohammad Ghavamzadeh, Sridhar Mahadevan, and Marek Petrik. Finite- sample analysis of proximal gradient td algorithms. In UAI, pages 504-513. Citeseer, 2015.
10

---

[24] Adwaitvedant S Mathkar and Vivek S Borkar. Nonlinear gossip. SIAM Journal on Control and Optimization, 54(3):15351557, 2016.
[25] Abdelkader Mokkadem and Mariane Pelletier. Convergence rate and averaging of nonlin- ear two-time-scale stochastic approximation algorithms. The Annals of Applied Probubility, 16(3:1671-1702, 2006.
[26] Gemma Morral, Pascal Bianchi, and Gersende Fort. Success and failure of adaptation adaatation-ddifusionn diffusion algorithms for consensus in multi-agent networks. In 53rd IEEE Conference on Decision and Control, pages 1476-1483 1481. IEEE, 2014.
[27] Gemma Morral, Pascal Bianchi, and Gersende Fort. Success and failure adaptation-diffusion algorithms with decaying step size in multiagent networks. IEEE Transactions on Signal Pro- cessing, (5(11))2798-23) 2017.
[28] Openai: Openai five. https: http://paaai.ccoll//o////eeeeeee wwt.coo///////. five// 2021. 05-24.
Accessed: 2021-
[29] Jun Ota. Multi-agent robot systems as distributed autonomous systems. Advanced engineering informatics, 2091)55 2006.
[30] Mariane Pelletier. On the almost sure asymptotic behaviour of stochastic algorithms. Stochastic processes and their applications, 78(2)22172244, 1998.
[31] Shi Pu and Angelia Nedié. Distributed stochastic gradient tracking methods. Mathematical Programming, pages 1-49, 2020.
[32] Shi Pu, Alex Olshevsky, and Ioannis Ch Paschalidis. Asymptotic network independence in dis- tributed stochastic optimization for machine learning: Examining distributed and centralized stochastic gradient descent. IEEE Signal Processing Magazine, 37(3):114-122, 14-122, 2020.
[33] Jineng Ren, Jarvis Haupt, and Zehua Guo. Communication- effficiinn hicrarchical distributed optimization for multi-agent policy evaluation. Journal of Computational Science, 49:101280, 2021.
[34] Martin Riedmiller, Andrew Moore, and Jeff Schneider. Reinforcement learning for cooperat- ing and communicating reactive agents in electrical power grids. In Workshop on Balancing Reactivity and Social Deliberation in Multi-Agent Systems, pages 137-149. Springer, 2000.
[35] Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforce- ment learning for autonomous driving. arXiv preprint drXiv:1610.03295, 2016.
[36] Miloš S Stanković, Marko Beko, and Srdjan S Stanković. Distributed gradient temporal dif- ference off-policy learning with eligibility traces: Weak convergence. Panesnnapes, (12):156331568, 2020.
[37] Jun Sun, Gang Wang, Georgios Giannakis, Qinmin Yang, and Zaiyue Yang. Finite-time analysis of decentralized -iiffrra-difffeencee learning with lincar function approximation. In International Conference on Artificial Intelligence and Statistics, pages 4485-4495. PMLR, 2020.
[38] Tao Sun, Tianyi Chen, Yuejiao Sun, Qing Liao, and Dongsheng Li. Decentralized markov chain gradient descent. arXiv preprint arXiv: 10238, 2019.
[39] Wesley Suttle, Zhuoran Yang. Kaiqing Zhang, Zhaoran Wang, Tamer Başar, and Ji Liu. A multi-agent off-policy actor-critic algorithm for distributed reinforcement learning. IFAC- PapersOnLine, 1342):154-1154, 2020.
[40] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[41] Richard Sutton, Csaba Szepesvári, and Hamid Reza Maei. A convergent o (n) temporal- difference algorithm for off off-policy learning with linear function approximation. In NIPS, 2008.

---

[42] John Tsitsiklis, Dimitri Bertsekas, and Michael Athans. Distributed asynchronous determinis- tic and stochastic gradient optimization algorithms. IEEE transactions on automatic control, 31(9):803-815 812, 1986.
[43] John N Tsitsiklis and Benjamin Van Roy. An analysis of temporal-diiference learning with function approximation. IEEE transactions on automatic control, 42(5)x674-690, 1997.
[44] Hoi-To Wai. On the convergence of consensus algorithms with markovian noise and gradient bias. In 2020 59th IEEE Conference Decision and Control (CDC), pages 4897-4902. IEEE, 2020.
[45] Hoi To Wai, Zhuoran Yang. Mingyi Hong, and Zhaoran Wang. Multi-agent reinforcement learning via double averaging primal-dual optimization. Advances in Neural Information Pro- cessing Systems, 201 119::899999909 9660, 2018.
[46] Yue Xu, Zengde Deng, Mengdi Wang, Wenjun Xu, Anthony Man-Cho So, and Shuguang Cui. Voting-based multi-agent reinforcement learning for intelligent iot. IEEE Internet of Things Journal, 2020.
[47] Kun Yuan, Qing Ling, and Wotao Yin. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 1835)11855-1854, 2016.
[48] Sihan Zeng, Aqeel Anwar, Thinh Doan, Justin Romberg, and Arijit Raychowdhury. A de- centralized policy gradient approach multi-task reinforcement learning. arXiv preprint vrXiv:2006.04335 2020.
[49] Sihan Zeng, Thinh T Doan, and Justin Romberg, Finite-time analysis of decentralized stochas- tic approximation with applications in multi-agent and multi-task learning. arXiv preprint arXiv:2010. 15088, 2020.
[50] Kaiqing Zhang, Zhuoran Yang, and Tamer Basar. Networked multi-agent reinforcement learn- ing continuous spaces. 2018 IEEE Conference on Decision and Control (CDC), pages 2771-2776. IEEE, 2018.
[51] Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-agent reinforcement learning: A selec- tive overview of theories and algorithms. Handbook of Reinforcement Learning and Control, pages 321-384, 2021.
[52] Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Basar. Fully decentralized multi-agent reinforcement learning with networked agents. In International Conference on Machine Learning, pages 5872-5881. PMLR, 2018
[53] Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Basar. Finite-sample anal- ysis for decentralized batch multi-agent reinforcement learning with networked agents. IEEE Transactions on Automatic Control, 2021.
[54] Xiaoxiao Zhao, Peng Yi, and Li Li. agent reinforcement learning. Control Theory and Technology. 18(4)3362-378, 2020.
Li. Distributed policy evaluation via inexact admm in multi-
12


Reviews:
[{"review_id": "lMoXkj_IZo2", "reviewer": "Reviewer_KYP4", "summary": "This paper studies a family of distributed nonlinear stochastic approximation for MARL, and derives a law of iterated logarithm, which describes the convergence rate on the converging sample path. It also presents an application using TD(0) with linear function approximation, by establishing the convergence rate and showing that it does not depend on the interaction graph. \n", "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": "- The problem in consideration is interesting. The paper is also well written and the ideas are carefully presented. \n- It would be useful if the authors could provide more intuitive explanation for Assume A2, e.g., what type of scenarios does it imply, or why is it necessary? \n- The application example appears to rely on the linear form of h(x). This is consistent with A2. Can this result be generalized to other cases? \n- Section 4.3 appears to be technical and not well positioned. \n- It would be helpful if the paper could provide an example for the distributed nonlinear SA case? Although Assumption A2 allows nonlinearity (assuming through the two f functions), the application seems to focus on the linear case. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It would be useful if the authors could provide more intuitive explanation for Assume A2, as well as more concrete application examples. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "cM5ndETAIcr", "reviewer": "Reviewer_jy9o", "summary": "This paper studies asymptotic convergence rates for a family of distributed Stochastic Approximation Schemes in a cooperative multi-agent learning setting (Nonlinear Gossip models). They provide convergence rates which applies almost surely on sample paths, improving over the existing analysis that analyse the expected behavior. In addition they have weaker assumptions on the Gossip matrix and the step sizes (removing square summability).\n\nAs a result, they analyze policy evaluation through TD(0) with linear function approximation for the infinite horizon reinforcement learning problem and the convergence rates follow for TD(0).\n\n", "questions": "", "limitations": "", "rating": 7, "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": "The model studied here is not widely studied in ML literature, but they show how their results apply to TD(0) with linear function approximation in the MARL setting. The main improvement is providing convergence rates over sample paths, eventhough it is asymptotic. This applies to a subclass of cooperative multi-agent RL where agents use TD(0).\n\n1) Could this framework be used to analyze a competitive setting or where the agents maybe negatively correlated? For instance, the setting of Markov games (Daskalakis et al. 2021)?\n\n2) Are there any conditions that guarantee the uniqueness of $x^*$?\n\n3) I believe a reason for the asymptotic nature is moving from the discrete updates to the limiting behavior of the ODE and I feel it would be better to add more discussion on this part (even if some of it comes from a different reference).\n\n4) What are the challenges of understanding other function approximation schemes, maybe quadratic (for example), could this be subsumed in the function h(x)? \n\n5) For the reduction to the RL setting the IID assumption seems to be key to ensure A and B dont depend on n, is there a work around for this? Would it be fruitful to look at the state-action visitation distribution? \n\nAdditional Reference:\nDaskalakis, Constantinos, Dylan J. Foster, and Noah Golowich. \"Independent policy gradient methods for competitive reinforcement learning.\" arXiv preprint arXiv:2101.04233 (2021).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above for limitations.", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "Oz1G1MB3nFQ", "reviewer": "Reviewer_Yt7X", "summary": "This paper presents a Law of Iterated Logarithm (LIL) for Distributed Stochastic Approximation (DSA) schemes, which characterizes the rate of convergence of the updates to their stable equilibrium. The conditions are more general than previous works (in particular the gossip matrix is not required to be doubly stochastic and step-sizes need not be square summable). An application to the case of TD(0) with linear function approximation is given. ", "questions": "", "limitations": "", "rating": 8, "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": "This is a well-written paper with a seemingly strong technical contribution to the DSA literature (although I am not an expert in that area), so I am recommending acceptance. \n\nThe writing is very clear, in particular the related works are well-covered. The proof outline (Section 4) is well sketched-out. \n\nOne question that I had was about the nature of the convergence guarantee. The theorem statement gives a convergence rate which holds “almost surely on E(x_\\star)”, where E(x_\\star) is the set of sequences which converges to x_star. It seems that this does not actually quantify the probability of convergence, but simply says that IF x_n converges to x_\\star then the rate will be as given (and this rate holds with probability one). Am I interpreting this correctly? If so, are there other results in the literature guaranteeing convergence with high probability (or with probability one) for the same conditions considered here? Some discussion about this point in the text would be appreciated. \n\nI am also wondering about the applicability of this theorem to other RL algorithms? The discussion mentions that Q-learning would require extending the analysis but have the authors tried applying this theorem to other policy evaluation algorithms (which are more likely to be “linear” and could fall under the umbrella of Assumption 2). Some discussion on this point in the text would also be helpful. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As mentioned above, some further discussion about the implications of the LIL would be appreciated.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "9ubxLoSHTqy", "reviewer": "Reviewer_ftij", "summary": "The paper introduces a new distributed stochastic approximations scheme that can be exploited in the Multi-Objective RL (MARL). They show that for TD(0) with linear function approximation, we can enjoy the convergence rate of $\\mathcal{O}(\\sqrt{n^{-\\gamma}\\log n})$.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "\n**Originality and Quality**\n\nAlthough the theoretical material and proof techniques are novel, the paper requires major improvement in writing to be accessible to the RL community. The paper motivates their stochastic approximation scheme by having application in MARL. However, the paper, as it is, is very inaccessible to the RL community. \n\nIn many cases, it's better that authors first provide better intuition before jumping into the math and the assumptions. \nMany terminologies are assumed to be known by the readers in the RL community, which is not the case. The paper needs to be re-written and be more self-contained so that people don't need to look for the definition of the terminologies in the references. \n\n**Clarity**\n\nThe paper needs major improvement in writing.\n\n**Significance**\n\nThe paper needs major improvement to be accessible and of interest to the RL community.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations and societal impact have been adequately addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies a family of distributed nonlinear stochastic approximation for MARL, and derives a law of iterated logarithm, which describes the convergence rate on the converging sample path. It also presents an application using TD(0) with linear function approximation, by establishing the convergence rate and showing that it does not depend on the interaction graph. All reviewers are convinced on the novelty and contribution of this paper. Reviewers still recommend authors to take their advices in restructuring certain part of the paper to make it more accessible to the general RL community.
Decision: Accept (Poster)