On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulator

Abstract

We study the global convergence of generative adversarial imitation learning for linear quadratic regulators, which is posed as minimax optimization. To address the challenges arising from non-convex-concave geometry, we analyze the alternating gradient algorithm and establish its Q-linear rate of convergence to a unique saddle point, which simultaneously recovers the globally optimal policy and reward function. We hope our results may serve as a small step towards understanding and taming the instability in imitation learning as well as in more general non-convex-concave alternating minimax optimization that arises from reinforcement learning and generative adversarial learning.

References in corpus (12)

• Evolution Strategies as a Scalable Alternative to Reinforcement Learning
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation
• Learning One-hidden-layer Neural Networks with Landscape Design
• On the Sample Complexity of the Linear Quadratic Regulator
• Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification
• Nonconvex Statistical Optimization: Minimax-Optimal Sparse PCA in Polynomial Time
• Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexity
• A Tour of Reinforcement Learning: The View from Continuous Control
• First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problems
• Solving Non-Convex Non-Concave Min-Max Games Under Polyak-Łojasiewicz Condition
• Online ICA: Understanding Global Dynamics of Nonconvex Optimization via Diffusion Processes

Cited by in corpus (8)

• Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems
• On the Global Convergence of Actor-Critic: A Case for Linear Quadratic Regulator with Ergodic Cost
• On Computation and Generalization of Generative Adversarial Imitation Learning
• Generative Adversarial Imitation Learning with Neural Networks: Global Optimality and Convergence Rate
• When Will Generative Adversarial Imitation Learning Algorithms Attain Global Convergence
• Minimax Problems with Coupled Linear Constraints: Computational Complexity, Duality and Solution Methods
• Provably Efficient Generative Adversarial Imitation Learning for Online and Offline Setting with Linear Function Approximation
• Convex-Concave Min-Max Stackelberg Games