Gradient Play In Stochastic Games: Stationary Points, Convergence, And Sample Complexity

Abstract

We study the performance of the gradient play algorithm for stochastic games (SGs), where each agent tries to maximize its own total discounted reward by making decisions independently based on current state information which is shared between agents. Policies are directly parameterized by the probability of choosing a certain action at a given state. We show that Nash equilibria (NEs) and first-order stationary policies are equivalent in this setting, and give a local convergence rate around strict NEs. Further, for a subclass of SGs called Markov potential games (which includes the setting with identical rewards as an important special case), we design a sample-based reinforcement learning algorithm and give a non-asymptotic global convergence rate analysis for both exact gradient play and our sample-based learning algorithm. Our result shows that the number of iterations to reach an \(\epsilon\)-NE scales linearly, instead of exponentially, with the number of agents. Local geometry

Stats

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

Related papers

• On The Convergence Of Policy Gradient Methods To Nash Equilibria In General Stochastic Games (2022)0.00
• Independent Policy Gradient For Large-scale Markov Potential Games: Sharper Rates, Function Approximation, And Game-agnostic Convergence (2022)0.00
• On The Global Convergence Rates Of Decentralized Softmax Gradient Play In Markov Potential Games (2022)0.00
• Decentralized Policy Gradient For Nash Equilibria Learning Of General-sum Stochastic Games (2022)0.00
• Convergence Analysis Of Gradient-based Learning With Non-uniform Learning Rates In Non-cooperative Multi-agent Settings (2019)0.00
• Asynchronous Gradient Play In Zero-sum Multi-agent Games (2022)0.00
• Last-iterate Convergence Of Decentralized Optimistic Gradient Descent/ascent In Infinite-horizon Competitive Markov Games (2021)0.00
• Policy-gradient Algorithms Have No Guarantees Of Convergence In Linear Quadratic Games (2019)5.24