Timezone: »

 
Oral
Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence
Dongsheng Ding · Chen-Yu Wei · Kaiqing Zhang · Mihailo Jovanovic

Tue Jul 19 01:45 PM -- 02:05 PM (PDT) @ Room 318 - 320
in RL: Multi-agent »
We examine global non-asymptotic convergence properties of policy gradient methods for multi-agent reinforcement learning (RL) problems in Markov potential games (MPGs). To learn a Nash equilibrium of an MPG in which the size of state space and/or the number of players can be very large, we propose new independent policy gradient algorithms that are run by all players in tandem. When there is no uncertainty in the gradient evaluation, we show that our algorithm finds an $\epsilon$-Nash equilibrium with $O(1/\epsilon^2)$ iteration complexity which does not explicitly depend on the state space size. When the exact gradient is not available, we establish $O(1/\epsilon^5)$ sample complexity bound in a potentially infinitely large state space for a sample-based algorithm that utilizes function approximation. Moreover, we identify a class of independent policy gradient algorithms that enjoy convergence for both zero-sum Markov games and Markov cooperative games with the players that are oblivious to the types of games being played. Finally, we provide computational experiments to corroborate the merits and the effectiveness of our theoretical developments.
Keywords: OPT: Control and Optimization · OPT: First-order · OPT: Non-Convex · RL: Function Approximation · RL: Multi-agent · RL: Policy Search · T: Game Theory · T: Optimization

Author Information

Dongsheng Ding (University of Southern California)
Chen-Yu Wei (University of Southern California)
Kaiqing Zhang (MIT)
Mihailo Jovanovic (University of Southern California)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors