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^{-\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.

Some typos corrected; 19 pages

References in corpus (8)

• Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Finite-Sample Analysis of Proximal Gradient TD Algorithms
• Finite-Time Analysis of Distributed TD(0) with Linear Function Approximation for Multi-Agent Reinforcement Learning
• Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise
• Decentralized Markov Chain Gradient Descent
• A Decentralized Policy Gradient Approach to Multi-task Reinforcement Learning
• Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexity