Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Games
This provides a provably faster convergence guarantee for multi-agent learning in potential games, which is incremental but addresses a known bottleneck in scalability.
The paper tackles the problem of multi-agent reinforcement learning in Markov potential games by analyzing an independent natural policy gradient (NPG) algorithm, showing it achieves an ε-Nash Equilibrium in O(1/ε) iterations, improving upon the previous O(1/ε²) result and matching the single-agent case.
This work studies an independent natural policy gradient (NPG) algorithm for the multi-agent reinforcement learning problem in Markov potential games. It is shown that, under mild technical assumptions and the introduction of the \textit{suboptimality gap}, the independent NPG method with an oracle providing exact policy evaluation asymptotically reaches an $ε$-Nash Equilibrium (NE) within $\mathcal{O}(1/ε)$ iterations. This improves upon the previous best result of $\mathcal{O}(1/ε^2)$ iterations and is of the same order, $\mathcal{O}(1/ε)$, that is achievable for the single-agent case. Empirical results for a synthetic potential game and a congestion game are presented to verify the theoretical bounds.