Abstract
In Multi-Agent Reinforcement Learning (MARL), multiple agents interact with acommon environment, as also with each other, for solving a shared problem insequential decision-making. It has wide-ranging applications in gaming,robotics, finance, etc. In this work, we derive a novel law of iteratedlogarithm for a family of distributed nonlinear stochastic approximationschemes that is useful in MARL. In particular, our result describes theconvergence rate on almost every sample path where the algorithm converges.This result is the first of its kind in the distributed setup and providesdeeper insights than the existing ones, which only discuss convergence rates inthe expected or the CLT sense. Importantly, our result holds undersignificantly weaker assumptions: neither the gossip matrix needs to be doublystochastic 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 graphdepicting the interactions among the different agents.