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

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keythoppe2021a

Related papers

• Multi-agent Reinforcement Learning In Stochastic Networked Systems (2020)0.00
• Global Convergence Of Localized Policy Iteration In Networked Multi-agent Reinforcement Learning (2022)2.26
• A Finite Time Analysis Of Distributed Q-learning (2024)0.00
• Faster Last-iterate Convergence Of Policy Optimization In Zero-sum Markov Games (2022)0.00
• From Game-theoretic Multi-agent Log Linear Learning To Reinforcement Learning (2018)0.00
• Multi-agent Reinforcement Learning With Reward Delays (2022)0.00
• Fully Decentralized Multi-agent Reinforcement Learning With Networked Agents (2018)0.00
• Scalable And Sample Efficient Distributed Policy Gradient Algorithms In Multi-agent Networked Systems (2022)0.00