Timezone: »

 
Poster
Policy Optimization Provably Converges to Nash Equilibria in Zero-Sum Linear Quadratic Games
Kaiqing Zhang · Zhuoran Yang · Tamer Basar

Wed Dec 11 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #193
in Reinforcement Learning and Planning -- Decision and Control »

We study the global convergence of policy optimization for finding the Nash equilibria (NE) in zero-sum linear quadratic (LQ) games. To this end, we first investigate the landscape of LQ games, viewing it as a nonconvex-nonconcave saddle-point problem in the policy space. Specifically, we show that despite its nonconvexity and nonconcavity, zero-sum LQ games have the property that the stationary point of the objective function with respect to the linear feedback control policies constitutes the NE of the game. Building upon this, we develop three projected nested-gradient methods that are guaranteed to converge to the NE of the game. Moreover, we show that all these algorithms enjoy both globally sublinear and locally linear convergence rates. Simulation results are also provided to illustrate the satisfactory convergence properties of the algorithms. To the best of our knowledge, this work appears to be the first one to investigate the optimization landscape of LQ games, and provably show the convergence of policy optimization methods to the NE. Our work serves as an initial step toward understanding the theoretical aspects of policy-based reinforcement learning algorithms for zero-sum Markov games in general.

Keywords: Multi-Agent RL · Reinforcement Learning and Planning
[ Paper]  [ Slides] 

Author Information

Kaiqing Zhang (University of Illinois at Urbana-Champaign (UIUC))
Zhuoran Yang (Princeton University)
Tamer Basar (University of Illinois at Urbana-Champaign)

More from the Same Authors