Provable Policy Gradient Methods for Average-Reward Markov Potential Games
This provides theoretical guarantees for policy gradient methods in multi-agent reinforcement learning with average rewards, addressing a gap compared to discounted rewards, but it is incremental as it extends existing methods to a new criterion.
The paper tackles the problem of learning Nash equilibria in Markov potential games under the average reward criterion, proving that policy gradient methods converge globally with time complexity O(1/ε²) and sample complexity Õ(1/ε⁵).
We study Markov potential games under the infinite horizon average reward criterion. Most previous studies have been for discounted rewards. We prove that both algorithms based on independent policy gradient and independent natural policy gradient converge globally to a Nash equilibrium for the average reward criterion. To set the stage for gradient-based methods, we first establish that the average reward is a smooth function of policies and provide sensitivity bounds for the differential value functions, under certain conditions on ergodicity and the second largest eigenvalue of the underlying Markov decision process (MDP). We prove that three algorithms, policy gradient, proximal-Q, and natural policy gradient (NPG), converge to an $ε$-Nash equilibrium with time complexity $O(\frac{1}{ε^2})$, given a gradient/differential Q function oracle. When policy gradients have to be estimated, we propose an algorithm with $\tilde{O}(\frac{1}{\min_{s,a}π(a|s)δ})$ sample complexity to achieve $δ$ approximation error w.r.t~the $\ell_2$ norm. Equipped with the estimator, we derive the first sample complexity analysis for a policy gradient ascent algorithm, featuring a sample complexity of $\tilde{O}(1/ε^5)$. Simulation studies are presented.