A Law of Iterated Logarithm for Multi-Agent Reinforcement Learning

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, 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−γ with γ ∈ (0, 1), the distributed TD(0) algorithm with linear function approximation has a convergence rate of O( √ n−γ lnn) a.s.; for the 1/n type stepsize, the same is O( √ n−1 ln lnn) a.s. These decay rates do not depend on the graph depicting the interactions among the different agents.

text: √ n−γ lnn) a.s.; for
the 1/n type stepsize, the same is O( √ n−1 ln lnn) a.s. These decay rates do not depend on the graph depicting the interactions among the different agents.

heading: 1 Introduction
text: Can a machine train itself in the same way an infant learns to sit up, crawl, and walk? That is, can a 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 an iterative scheme that helps find zeroes or optimal points of a function, for which only noisy evaluations are possible. In this work, we analyze a family of 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 or learners that continually engage with a shared environment: the agents pick local actions, and the environment responds by transitioning to a 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 as diverse as 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 a DSA scheme withm distributed nodes can be described as follows. Let G
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
be a directed graph representing the connections between these nodes, andW ≡ (Wij) ∈ [0, 1]m×m a matrix whose ij-th entry denotes the strength of the edge j → i. It is assumed thatW is compatible with G, i.e., Wij > 0 only if j → i ∈ G. Then, at agent i, the above scheme (written as row vectors) has the update rule
xn+1(i) = ∑ j∈Ni Wijxn(j) + αn[hi(xn) +Mn+1(i)], n ≥ 0, (1)
where xn ∈ Rm×d is the joint estimate of the solution at time n, its j-th row, i.e., xn(j) denotes1 the estimate obtained at agent j,Ni represents the set of in-neighbors of node i in G, αn is the stepsize, hi : Rm×n → Rd is the driving function at agent i, and Mn+1(i) ∈ Rd 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
xn+1 =Wxn + αn[h(xn) +Mn+1], (2)
where Mn+1 is the m × d matrix whose i-th row is Mn+1(i), and h is the function that maps x ∈ Rm×d to the m× d matrix whose i-th row is hi(x). Two important points about the above framework are as follows: i.) we allow hi to be a function of all of xn and not just of xn(i), as 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 a 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 offpolicy 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.
Finite-time literature, in contrast, majorly talks about expectation bounds. Assuming there exists a unique x∗ that solves ∑m i=1 hi(x) = 0, these results describe the rate at which E∥xn − 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 ϵ, the expected error decreases linearly to a ball of radius O( √ ϵ ln(1/ϵ)). On the other hand, [44] deals with the case where h is additionally non-convex and shows that E∥xn−x∗∥ = O(n−1/4 √ lnn), which is comparable to the best known bound in the centralized setting.
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 a result similar to the one in [49] holds for this method under constant stepsizes. In contrast, when αn is of the 1/n type, it is proven that E∥xn − x∗∥ = O(1/ √ n). Similar bounds have also been derived 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).
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, it 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 square-summable stepsizes. Nothing is known about the slowly-decaying non-square-summable
1By default, all our vectors are row vectors. We use ′ for conjugate transpose.
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 are as follows.
1. Law of Iterated Logarithm (LIL): We derive a novel law of iterated logarithm for the DSA scheme given in (2). That is, for a suitably defined x∗, we show that lim sup[αn ln tn+1] −1/2∥xn − x∗∥ ≤ C a.s. on every sample path in the event
E(x∗) := {xn → x∗}. (3) Here, C ≥ 0 is some constant2 and tn = ∑n−1
k=0 αk. Also, the norm that we work is the operator norm. In particular, for any x ∈ Cm×d,
∥x∥ := sup u∈Cm,v∈Cd
{|uxv′| : ∥u∥ = ∥v∥ = 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 (xn)n≥0 than other existing results, which only discuss convergence rates in the expected or the CLT sense.
2. Analysis and Gossip Matrix: The above result is obtained via a new approach we develop here for analyzing DSA schemes. Let π ∈ Rm be such that πW = π and let
Q := I− 1′π, (5)
where 1 ∈ Rm denotes the vector of all ones. Then an outline of our approach is that we express xn−x∗ as a sum of 1′π(xn−x∗) andQxn and, thereafter, analyze each summand by treating its update rule as a separate SA scheme. This contrasts the usual approach (e.g., [27, 10, 11]) where the error is split into (1′1/m)(xn − x∗) and (I− 1′1/m)xn. 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 a law of iterated logarithm for the distributed TD(0) algorithm with linear function approximation. This is the first such result in MARL.
Contents: The rest of the paper is structured as 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 a demonstration of how our 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 on 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 a summary of our findings and discuss some interesting future directions.

heading: 2 Assumptions and Main Result
text: Throughout this work, we assume that the following four technical assumptions, i.e., A1, . . . ,A4, hold for the DSA scheme in (2).
A1. Property of the Gossip Matrix: W is an irreducible aperiodic row stochastic matrix.
This condition implies there exists a unique vector π ∈ Rm such that
πW = π. (6) 2Throughout, 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.
Accordingly, based on [24, Theorem 1], one would expect (2) to eventually converge to an invariant set of the m-fold product of the d-dimensional ODE
ẏ(t) = m∑ i=1 πihi(1′y(t)) = πh(1′y(t)). (7)
By an m-fold product, we refer to the dynamics in Rm×d where each row individually satisfies (7). A natural invariant set of this dynamics is S := {1′y : y ∈ Rd} ⊂ Rm×d. With this in mind, let
x∗ = 1′y∗ ∈ S, (8)
where y∗ ∈ Rd is an asymptotically stable equilibrium of (7). Notice that we 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(x∗), where x∗ is as defined above and E(x∗) is as defined in (3).
A2. Nature of h near x∗: There exists a neighbourhood U of x∗ such that, for x ∈ U ,
h(x) = −1′π(x− x∗)A+ 1′πf1(x) +Q(B + f2(x)), (9)
where A ∈ Rd×d is such that yAy′ > 0 for all y ̸= 0, B ∈ Rm×d is some constant matrix, f2 : U → Rm×d is some arbitrary continuous function, while f1 : U → Rm×d is another continuous function that additionally satisfies
∥1′πf1(x)∥ = O(∥1′π(x− x∗)∥a), as x→ x∗, (10)
for some a > 1.
Note that A2 is a generalization of Assumption (A1) in [30]. As in [30], this also is local in nature: it only prescribes a specific behavior for h close to x∗. Furthermore, this condition ensures that the driving function πh(x) in (7) equals −π(x − x∗)A + πf1(x); the first term is the linear part while the second term represents the nonlinear portions. Separately, observe thatQh(x) = Q(B+f2(x)). 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 A are as defined above3. Clearly, if b(i) and x(i) are the i-th rows of B and x, respectively, then the i-component function here is hi(x) = b(i) − x(i)A. The fact that the scaling matrix A is the same for each i is crucial for A2 to hold. Also, observe that this function does not depend on π. The other members of the family are obtained by adding various π-dependent nonlinear perturbations to this simple setup, i.e., by making different choices4 for f1 and f2.
A3. Stepsize Behavior: There exists some decreasing positive function α defined on [0,∞) such that the stepsize αn = α(n). Further, α is either of Type 1 or Type γ. (a) Type 1: α(n) = α0/n for some α0 > 1/(2λmin), where
λmin := min{R(λ) : λ ∈ spectrum(A)} (11)
with R(λ) denoting the real part of λ; (b) Type γ : The function α is differentiable and its derivative varies regularly with exponent
−1− γ, where 0 < γ < 1.
The regularly varying condition above implies that ∣∣∣ dα(x)dx ∣∣∣ = x−γ−1L(x) for some slowly varying function L, e.g., L(x) = C for some C > 0, or L(x) = (lnx)η for some η ∈ R. Thus, examples of αn here include Cn−γ and n−γ(lnn)η, which are non-square-summable for γ ∈ (0, 1/2].
A4. Noise Attributes: With Fn = σ(x0,M1, . . . ,Mn), and E(x∗), as in (3), the following hold. (a) E(Mn+1|Fn) = 0 a.s.
3A verification of all the conditions mentioned in A2 for h(x) = B− xA has been done in Section 3; there we also discuss usefulness of this function in the context of policy evaluation in MARL.
4For example, we can let f1(x) = g1(π(x− x∗)) and f2(x) = −xA+ g2(x), where g1 : Rd → Rm×d is such that, as z → 0, ∥g1(z)∥ = O(∥z∥a) for some a > 1, and g2 is an arbitrary continuous function.
(b) There exists C ≥ 0 such that ∥QMn+1∥ ≤ C (1 + ∥Q(xn − x∗)∥) a.s. on E(x∗). (c) There is a non-random symmetric positive semi-definite matrix M ∈ Rd×d such that
lim n→∞
E(M ′n+1π′πMn+1 | Fn) =M a.s. on E(x∗). (12)
(d) There exists b > 2 such that supn≥0 E(∥πMn+1∥b|Fn) <∞ a.s. on E(x∗).
These noise conditions are extensions of the standard assumptions in the SA literature [30, 25, 4].
Our main result can now be stated as follows. This generalizes Theorem 1 from [30].
Theorem 2.1 (Main Result: Law of Iterated Logarithm). Suppose A1, . . . , A4 hold and γ > 2/b if α is of Type γ. Then, there exists some deterministic constant C ≥ 0 such that
lim sup[αn ln tn+1] −1/2∥xn − x∗∥ ≤ C a.s. on E(x∗).
This result is called a law of iterated logarithm since its proof crucially relies on Lemma 4.6, which indeed is a 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 E(x∗), ∥xn − x∗∥ is O( √ n−1 ln lnn) in the Type 1
case, and O( √ n−γ lnn) in the Type γ case. Note that, since we require γ > 2/b, our result applies for smaller values of γ, only if A4.(d) holds for a 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 P{E(x∗)} = 1. As mentioned in Section 1, the existing results are of two kinds: finite-time expectation bounds and the CLT. Indeed a finite-time bound has several benefits and is not directly comparable to an asymptotic 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, 11], which show E∥xn − x∗∥ = O( √ lnn/ √ n), then ours is tighter (it has ln lnn in place of lnn). Furthermore, while a CLT can at the best show that lim supα −1/2 n ∥xn−x∗∥ = ∞ a.s., our result is more precise in stating that the expression becomes
bounded if it is divided by an additional √ ln tn+1 term.

heading: 3 Application to Reinforcement Learning
text: We apply our result here to a 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, {Ui},P, {Ri}, γ,G). Here, S = {1, . . . , L} is the global state space, Ui and Ri are the set of actions and the reward function at agent i, respectively, P describes the transition probabilities, γ is the discount factor, and G ≡ (V, E) is a directed graph that represents the connectivity structure among the m agents.
Let Ni and W be as in (1). We assume that this W satisfies the conditions in A1. Then, for this matrix, there is a unique vector π ≡ (πi) satisfying (6). Let µi be the stationary policy of agent i and let µ ≡ (µi). Also, let µ(a|s) = ∏ i µi(ai|s) be the
probability for choosing the joint action a ≡ (ai) ∈ ∏
i Ui. This policy µ then induces a Markov chain on S, which we assume is aperiodic and irreducible. Therefore, it also has a unique stationary distribution and we denote the same by φ ∈ RL. At each step, the above system evolves as follows. First, each agent i sees the current state s and applies an action ai ∈ Ui sampled from µi(·|s). Based on the joint action a, the system then moves to a new state s̃. Equivalently, the joint action a and the state s̃ can be seen as samples of µ(·|s) and P(·|s, a), respectively. Finally, each agent i receives an instantaneous reward Ri(s, a, s̃). Objective and Algorithm: The goal of the multi-agent system is to cooperatively estimate the value function Jµ ∈ RL corresponding to µ. This is defined as the solution to the Bellman equation
Jµ(s) = E [∑
i
πiRi(s, a, s̃) + γJµ(s̃) ] , s ∈ S,
where the expectation is over a ∼ µ(·|s) and s̃ ∼ P(·|s, a). This expression differs from the ones in [10, 11], in that, the coefficients πi 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 Φ ∈ RL×d with full column rank. And then, with ϕ(s) denoting the s-th row of Φ, try and find a θ ∈ Rd such that Jµ(s) ≈ ϕ(s)θ′ for all s ∈ S. The distributed TD(0) algorithm is helpful in this latter context. Let (sn, an, s̃n), n ≥ 0, be IID5 samples of (s, a, s̃), where s ∼ φ(·), a ∼ µ(·|s), and s̃ ∼ P(·|s, a). Then, at agent i, this distributed algorithm has the update rule:
θn+1(i) = ∑ j∈Ni Wijθn(j) + αn(bn(i)− θn(i)An), (13)
where bn(i) = Ri(sn, an, s̃n)ϕ(sn) ∈ Rd and An = ϕ′(sn)ϕ(sn)− γϕ′(s̃n)ϕ(sn) ∈ Rd×d. Analysis: We first express the update rule given in (13) for different i in the standard DSA form. Let6 A = E[An] and B = E[Bn], where Bn ∈ Rm×d is the matrix whose i-th row is bn(i). Both A and B do not depend on n since (sn, an, s̃n), n ≥ 0, is IID. Next, for n ≥ 0, let xn ∈ Rm×d be the matrix whose i-th row is θn(i). Then, (13) for different i can be jointly written as shown in (2) for
h(x) = B − xA and Mn+1 = (Bn −B)− xn(An −A). (14)
Next, we look at the limiting ODE given in (7). In our case, this has the form ẏ(t) = πB − y(t)A. Now, A is known to be positive definite [40], i.e., θAθ′ > 0 for all θ ̸= 0. Hence, it is invertible and the real parts of all its eigenvalues are positive, i.e., −A is Hurwitz stable. This then shows that θ∗ = πBA −1 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 f1(x) = 0 and f2(x) = −xA for x ∈ Rm×d. Further, let x∗ = 1′θ∗. Then, h(x) = −1π(x − x∗)A + (I − 1π)(B + f2(x)), as desired. In order to satisfy A3, we simply choose a stepsize sequence that fulfills one of the criteria mentioned there.
It now only remains to establish A4. Let Fn be as defined there. Then, part (a) follows from the definitions of A and B and the fact that (sn, an, s̃n) 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, s̃n) is independent of the past, the only quantity that is random in E[M ′n+1π′πMn+1|Fn] is xn. Also, trivially, E[M ′n+1π′πMn+1|Fn] is a symmetric positive semidefinite matrix. Therefore, on the event E(x∗), it is easy to see that part (c) holds as well. Finally, notice that ∥πMn+1∥ ≤ C(1+∥xn−x∗∥) for some C ≥ 0; this follows as in part (b) above. Hence, on E(x∗), supn≥0 E[∥πMn+1∥b|Fn] <∞ a.s. for any b ≥ 0. This verifies part (d). Thus, Theorem 2.1 holds for the distributed TD(0) algorithm with linear function approximation.

heading: 4 Theoretical Analysis: Proof of the Main Result
text: We now turn to the technical details of our analysis. With Q as in (5) and x∗ as in (8), observe that 1′πx∗ = x∗ and, hence, xn − x∗ = 1′π(xn − x∗) + Qxn. 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 xn−x∗ is split into (1′1/m)(xn − x∗) and (I − (1′1/m))xn. 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.
5The 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 is beyond the scope of this paper. The good news though is that, as shown in previous works [14, 10, 11], the asymptotic behaviours with and without the Markovian noise are often similar.
6The matrix A is usually defined to be the transpose of the expression we use.
Lemma 4.1. (Agreement Error) Almost surely on E(x∗),
lim sup n→∞ ∥1′π(xn − x∗)∥√ αn ln tn+1 ≤ C, (15)
where C ≥ 0 is some deterministic constant. Lemma 4.2. (Disagreement Error) Let δ > 0. Then,
∥Qxn∥ = O ( αn(lnn) 1+δ )
a.s. on E(x∗). (16) Remark 4.3. Up to logarithmic factors, the rate at which the disagreement error decreases is 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
∥xn − x∗∥ ≤ ∥1′π(xn − x∗)∥+ ∥Qxn∥.
Also, ln tn+1 is O(lnn) and O(ln lnn) in the Type γ and Type 1 cases, respectively. The desired result is now easy to see from Lemmas 4.1 and 4.2.

heading: 4.1 Bound on agreement error ∥1′π(xn − x∗)∥
text: We first focus on the details of our analysis for the first ingredient, i.e., the agreement error. Let
ψn+1 := n∑ k=0 αk1′πMk+1e−(tn+1−tk+1)A, n ≥ 0, (17)
and ∆n := 1′π(xn − x∗)− ψn, n ≥ 0. (18)
Clearly, to prove Lemma 4.1, it suffices to obtain bounds on the rate at which ∥ψn∥ and ∥∆n∥ decay. These bounds are stated below. Note that these results are generalizations of Lemmas 1 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, ψn,∆n, are matrix-valued, unlike the ones in [30] which were vector-valued. Lemma 4.4. Let b be as in A4. Suppose that either α is of Type 1 or that α is of Type γ with γ > 2/b. Then, there exists some deterministic constant C ≥ 0 such that
lim sup n→∞
(αn ln tn+1) −1/2 ∥ψn+1∥ ≤ C a.s. on E(x∗) (19)
Lemma 4.5. Suppose A2, A3 and A4 hold. Then, for any λ ∈ (0, λmin),
∥∆n∥ = O max e−λ∑nk=0 αk , n∑ j=0 αje −λ ∑n k=j+1 αk [αj∥ψj∥+ ∥ψj∥a]   (20)
a.s. on E(x∗), where a is as in (10). Furthermore,
1. If α is of Type 1, then ∥∆n∥ = O ( max{n−λα0 ;n− a2 ;n−1.5}(lnn) a2+1 ) a.s. on E(x∗).
2. If α is of Type γ with 2/b < γ < 1, then ∥∆n∥ = O ( αn(αn ln tn+1) 1/2 + (αn ln tn+1) a/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 one point which we would like to emphasize here. That is, ψn is a sum of scaled (matrix-valued) martingale differences. And, to derive its decay rate, we use the following law of iterated logarithm.
Let LL(x) = ln ln(x).
Lemma 4.6. For n ≥ 0, let Un+1 = ∑n
k=0 ϕkϵk+1, where {ϵn} is a real-valued martingale difference sequence adapted to a filtration {Fn}, and {ϕn} is a sequence of real-valued scalars, again adapted to {Fn}. Let {Tn}, also adapted to {Fn}, be such that, for n ≥ 0, |ϕn| ≤ Tn a.s. and τn := ∑n k=0 T 2 k satisfies limn→∞ τn = ∞ a.s. Further, assume supn≥0 E[ϵ2n+1|Fn] ≤ σ2 a.s. for some constant σ2. Also, let β > 0 be such that ∑ n T 2+2β n τ −1−β n [LL(τn)] β <∞ and supn≥0 E [ |ϵn+1|2+2β
∣∣Fn] <∞ a.s. Then, lim sup[2τnLLτn]−1/2|Un+1| ≤ σ a.s. (21) Remark 4.7. The condition ∑ n T 2+2β n τ −1−β n [LL(τn)]
β < ∞ differs from the one in [12, Corollary 6.4.25]; in that, it includes the additional term [LL(τn)]β . The impact of this is that we no longer require β to be in (0, 1) as was the case in [12, Corollary 6.4.25]. Instead, β can now take any positive value. This is precisely what allows Theorem 2.1 to be applicable even when the stepsizes are non-square summable.
Remark 4.8. The above result goes through even if we have lim supn→∞ E[ϵ2n+1|Fn] ≤ σ2 instead of supn≥0 E[ϵ2n+1|Fn] ≤ σ2; 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′π(xn − x∗)∥ ≤ ∥ψn∥+ ∥∆n∥.
First consider the case where α is of Type γ. From Lemmas 4.4 and 4.5, we have
lim sup n→∞ ∥1′π(xn − x∗)∥ (αn ln tn+1) 1/2 ≤ C + lim sup n→∞ O ( αn + (αn ln tn+1) (a−1)/2 ) = C,
where the last display holds because limn→∞ αn = 0, limn→∞ αn ln tn+1 = 0, and a > 1.
Next consider the case where α is of Type 1. Again, from Lemmas 4.4 and 4.5, we get
lim sup n→∞ ∥1′π(xn − x∗)∥ (αn ln tn+1) 1/2 ≤ C + lim sup n→∞ O ( max(n−λα0 ;n− a 2 ;n−1.5)(lnn)1+a/2 (n−1 lnn)1/2 ) = C,
where the last display holds because λα0 > 12 and a > 1.
The desired result now follows.

heading: 4.2 Bound on disagreement error ∥Qxn∥
text: We now turn to the detailed analysis of the disagreement component of the error. Let
χn+1 := n∑ j=0 αjW n−jQMj+1e −(tn+1−tj+1)A, n ≥ −1, (22)
and Γn := Qxn − χn, n ≥ 0. (23)
Note that χn represents the cumulative noise in Qxn. It is also easy to see that
χn+1 =Wχne −αnA + αnQMn+1, n ≥ 0. (24)
We now state our bounds for ∥χn∥ and ∥Γn∥. Note that χn and Γn are peculiar to the DSA setup and do not have analogues in the one-timescale analysis.
Lemma 4.9. Let δ > 0. Then, ∥χn+1∥ = O ( αn(lnn) 1+δ ) a.s. on E(x∗) (25)
Lemma 4.10. Almost surely on E(x∗),
∥Γn+1∥ = O (αn) . (26)
We refer readers to the Appendix for proofs of Lemma 4.9 and 4.10. The overall disagreement error can now be bounded as shown below.
Proof of Lemma 4.2. Observe that
∥Qxn∥ ≤ ∥Γn∥+ ∥χn∥.
Using lemmas 4.9 and 4.10, we then have ∥Qxn∥ = O (αn) +O ( αn(lnn) 1+δ ) = O ( αn(lnn) 1+δ ) ,
as desired.

heading: 5 Discussion
text: We derive a novel law of iterated logarithm for a family of nonlinear DSA algorithms that is useful in MARL. This law can also be seen as an 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 a sum of martingale differences.
While our DSA framework is fairly general, a key limitation is that the scaling matrix (i.e., A) in each component function hi 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]. A third direction is 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, we 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 to thank the anonymous reviewers for providing helpful and constructive feedback on the paper. Research of Gugan Thoppe is supported by IISc’s start up grants SG/MHRD-19-0054 and SR/MHRD-19-0040.

Review summaries:
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).  As 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).  

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.