A Law of Iterated Logarithm for Multi-Agent Reinforcement Learning

Gugan Thoppe, Bhumesh Kumar

Abstract: This paper establishes a novel Law of Iterated Logarithm (LIL) for distributed reinforcement learning, providing the first "almost sure" convergence rates for individual sample paths in multi-agent systems. Unlike previous theoretical frameworks that rely on restrictive assumptions like doubly stochastic communication matrices or specific learning rates, this work proves convergence under realistic conditions, including directed communication graphs and slowly decaying stepsizes. The authors demonstrate that agents converge at a rate of $O(\sqrt{n^{-\gamma} \ln n})$, offering a significantly sharper characterization of the fluctuations in Multi-Agent Reinforcement Learning (MARL) than previously available.

1. Introduction

In Multi-Agent Reinforcement Learning (MARL), a collective of agents seeks to solve a global task by interacting with a shared environment and exchanging information via a communication network, often referred to as "gossiping." The mathematical backbone for analyzing these systems is Stochastic Approximation (SA), a framework used to find optimal points (such as value functions or policies) using noisy, iterative data.

Despite the prevalence of MARL, existing theoretical guarantees suffer from two primary limitations. First, most proofs focus on convergence in expectation or the Central Limit Theorem (CLT). While these describe the "average" behavior or the distribution of errors, they fail to characterize the behavior of a single specific run of an algorithm. Second, previous proofs often required "doubly stochastic" gossip matrices—where information flow is perfectly balanced—and "square-summable" learning rates. In practice, communication networks are often directed (lopsided), and learning rates are chosen to decay slowly to maintain exploration. This paper addresses these gaps by deriving a Law of Iterated Logarithm (LIL) for Distributed Stochastic Approximation (DSA).

2. Theoretical Framework: The Law of Iterated Logarithm

The Law of Iterated Logarithm occupies a unique "middle ground" in probability theory. While the Law of Large Numbers (LLN) guarantees that an algorithm will eventually converge to the correct value, and the CLT describes the asymptotic distribution of the error, the LIL provides a tight bound on the magnitude of the fluctuations (the "peaks" of the noise) during the convergence process.

By establishing an LIL for MARL, the authors provide a more precise characterization of the "almost sure" convergence rate—meaning the rate at which a single realization of the learning process approaches the optimum with probability one.

3. Methodology

The authors analyze a family of Distributed Stochastic Approximation (DSA) schemes, specifically focusing on their application to Distributed TD(0) with linear function approximation. Their derivation relies on three technical innovations:

  • Novel Error Decomposition: The error is split into an "agreement" component (consensus among agents) and a "disagreement" component (individual deviations from the consensus). This allows for a granular analysis of how communication affects learning.
  • Refined LIL for Martingales: The researchers improved classical concentration inequalities (specifically from Duflo, 2013) for sums of martingale differences. This improvement allows the theory to remain valid even when the stepsize (learning rate) is not square-summable (i.e., it decays slower than $1/n$).
  • Projection Matrix $Q$: By introducing a specific projection matrix ($Q = I - \mathbf{1}'\pi$), the authors decoupled the requirements for the gossip matrix. This allows the theory to apply to directed graphs where information might flow more heavily in one direction (e.g., broadcast nodes).

4. Key Results and Insights

The paper provides concrete, almost sure convergence rates for Distributed TD(0) based on the type of stepsize used:

  1. Type $\gamma$ Stepsizes: For learning rates such as $n^{-\gamma}$ (where $\gamma \in (0,1)$), the convergence rate is $O(\sqrt{n^{-\gamma} \ln n})$.
  2. Type 1 Stepsizes: For standard $1/n$ learning rates, the rate is $O(\sqrt{n^{-1} \ln \ln n})$. This is a much tighter bound than the $O(1/\sqrt{n})$ bounds typically found in expectation-based studies.

4.1 Graph Independence

A surprising finding is that the final decay rate of the error is independent of the specific structure of the interaction graph, provided the graph is connected and aperiodic. While the graph structure influences the speed of consensus, it does not change the fundamental asymptotic rate of convergence.

4.2 Consensus vs. Learning

The authors proved that the "disagreement" between agents vanishes significantly faster than the overall approximation error. This implies that agents reach a consensus relatively quickly, and the primary bottleneck for learning is the inherent noise in the environment rather than the limitations of the communication network.

5. Discussion and Limitations

While this work provides a significant theoretical upgrade, several avenues for future research remain:

  • Heterogeneous Scaling: The current model assumes the scaling matrix (the local dynamics) is identical across all agents. Future work is needed to address systems where agents have different local transition dynamics.
  • Network Dynamics: The proofs assume a static communication graph. Extending this to time-varying or stochastic networks (where connections may drop) would increase real-world applicability.
  • Noise Models: The study assumes martingale noise. Transitioning to Markovian noise—where the noise is state-dependent—is a necessary next step for broader RL applications.

6. Conclusion

By deriving the Law of Iterated Logarithm for MARL, this paper provides a rigorous mathematical foundation for understanding the sample-path behavior of distributed learning algorithms. The results confirm that distributed agents can achieve tight convergence bounds even under flexible communication and learning rate conditions, reinforcing the viability of decentralized reinforcement learning in complex, directed networks.

Summary updated

BibTeX
@inproceedings{thoppe2021law,
  author = {Gugan Thoppe and Bhumesh Kumar},
  title = {{A Law of Iterated Logarithm for Multi-Agent Reinforcement Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=6w4rGOrHfC},
}
Figure