# A Law of Iterated Logarithm for Multi-Agent Reinforcement Learning

arXiv: https://arxiv.org/abs/2110.15092 · HTML: https://mlsanity.com/paper/2110.15092/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 53 references that are in the map.
- First posted on arXiv 27 Oct 2021.

## Builds on (most cited first, 23 of 23)

- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1610.03295/) (2016)
- [Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents](https://mlsanity.com/paper/1802.08757/) (2018)
- [On the Convergence of Decentralized Gradient Descent](https://mlsanity.com/paper/1310.7063/) (2013)
- [Distributed Stochastic Gradient Tracking Methods](https://mlsanity.com/paper/1805.11454/) (2018)
- [Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2002.01268/) (2020)
- [Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization](https://mlsanity.com/paper/1806.00877/) (2018)
- [Finite-Sample Analysis of Proximal Gradient TD Algorithms](https://mlsanity.com/paper/2006.14364/) (2020)
- [A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Bound](https://mlsanity.com/paper/1911.09157/) (2019)
- [A Decentralized Policy Gradient Approach to Multi-task Reinforcement Learning](https://mlsanity.com/paper/2006.04338/) (2020)
- [A Multi-Agent Off-Policy Actor-Critic Algorithm for Distributed Reinforcement Learning](https://mlsanity.com/paper/1903.06372/) (2019)
- [Finite-Time Performance of Distributed Temporal Difference Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.12530/) (2019)
- [On the Convergence of Consensus Algorithms with Markovian Noise and Gradient Bias](https://mlsanity.com/paper/2008.07841/) (2020)
- [Asymptotic Network Independence in Distributed Stochastic Optimization for Machine Learning](https://mlsanity.com/paper/1906.12345/) (2019)
- [Finite-Sample Analysis of Decentralized Temporal-Difference Learning with Linear Function Approximation](https://mlsanity.com/paper/1911.00934/) (2019)
- [Primal-Dual Algorithm for Distributed Reinforcement Learning: Distributed GTD](https://mlsanity.com/paper/1803.08031/) (2018)
- [Online Algorithms for Estimating Change Rates of Web Pages](https://mlsanity.com/paper/2009.08142/) (2020)
- [Voting-Based Multi-Agent Reinforcement Learning for Intelligent IoT](https://mlsanity.com/paper/1907.01385/) (2019)
- [Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexity](https://mlsanity.com/paper/2103.13147/) (2021)
- [Decentralized Markov Chain Gradient Descent](https://mlsanity.com/paper/1909.10238/) (2019)
- [Success and Failure of Adaptation-Diffusion Algorithms for Consensus in Multi-Agent Networks](https://mlsanity.com/paper/1410.6956/) (2014)

## Built on by (most cited first, 1 of 1)

- [Online Learning with Adversaries: A Differential-Inclusion Analysis](https://mlsanity.com/paper/2304.01525/) (2023)

## Abstract (arXiv)

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-γ ln n ) a.s.; for the 1/n type stepsize, the same is O(√n-1 ln ln n) a.s. These decay rates do not depend on the graph depicting the interactions among the different agents.