A Law of Iterated Logarithm for Multi-Agent Reinforcement Learning
This provides foundational theoretical insights for researchers in MARL, offering a first-of-its-kind result in distributed setups with weaker assumptions.
The paper tackles the problem of analyzing convergence rates in multi-agent reinforcement learning by deriving a novel law of iterated logarithm for distributed nonlinear stochastic approximation schemes, showing that distributed TD(0) achieves convergence rates of O(√(n^{-γ} ln n)) a.s. for stepsize n^{-γ} and O(√(n^{-1} ln ln n)) a.s. for 1/n stepsize.
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 $γ\in (0, 1),$ the distributed TD(0) algorithm with linear function approximation has a convergence rate of $O(\sqrt{n^{-γ} \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.