Provably Global Convergence of Actor-Critic: A Case for Linear Quadratic Regulator with Ergodic Cost
Zhuoran Yang · Yongxin Chen · Mingyi Hong · Zhaoran Wang

Wed Dec 11th 05:00 -- 07:00 PM @ East Exhibition Hall B + C #212

Despite the empirical success of the actor-critic algorithm, its theoretical understanding lags behind. In a broader context, actor-critic can be viewed as an online alternating update algorithm for bilevel optimization, whose convergence is known to be fragile. To understand the instability of actor-critic, we focus on its application to linear quadratic regulators, a simple yet fundamental setting of reinforcement learning. We establish a nonasymptotic convergence analysis of actor- critic in this setting. In particular, we prove that actor-critic finds a globally optimal pair of actor (policy) and critic (action-value function) at a linear rate of convergence. Our analysis may serve as a preliminary step towards a complete theoretical understanding of bilevel optimization with nonconvex subproblems, which is NP-hard in the worst case and is often solved using heuristics.

Author Information

Zhuoran Yang (Princeton University)
Yongxin Chen (Georgia Institute of Technology)
Mingyi Hong (University of Minnesota)
Zhaoran Wang (Northwestern University)

More from the Same Authors