Derivative-Free Methods for Policy Optimization: Guarantees for Linear Quadratic Systems

Abstract

We study derivative-free methods for policy optimization over the class of linear policies. We focus on characterizing the convergence rate of these methods when applied to linear-quadratic systems, and study various settings of driving noise and reward feedback. We show that these methods provably converge to within any pre-specified tolerance of the optimal policy with a number of zero-order evaluations that is an explicit polynomial of the error tolerance, dimension, and curvature properties of the problem. Our analysis reveals some interesting differences between the settings of additive driving noise and random initialization, as well as the settings of one-point and two-point reward feedback. Our theory is corroborated by extensive simulations of derivative-free methods on these systems. Along the way, we derive convergence rates for stochastic zero-order optimization algorithms when applied to a certain class of non-convex problems.

Version v3 consistent with paper appearing in JMLR

Cited by in corpus (26)

• Certainty Equivalence is Efficient for Linear Quadratic Control
• Variance-reduced $Q$-learning is minimax optimal
• Finite-time Analysis of Approximate Policy Iteration for the Linear Quadratic Regulator
• Near-Optimal Design of Safe Output Feedback Controllers from Noisy Data
• A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning
• Non-asymptotic and Accurate Learning of Nonlinear Dynamical Systems
• From self-tuning regulators to reinforcement learning and back again
• Stabilizing Dynamical Systems via Policy Gradient Methods
• Logarithmic Regret for Learning Linear Quadratic Regulators Efficiently
• Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling
• Policy-Gradient Algorithms Have No Guarantees of Convergence in Linear Quadratic Games
• Asynchronous Distributed Reinforcement Learning for LQR Control via Zeroth-Order Block Coordinate Descent
• Data-Driven System Level Synthesis
• Global Convergence of Policy Gradient Primal-dual Methods for Risk-constrained LQRs
• On the Analysis of Model-free Methods for the Linear Quadratic Regulator
• Primal-dual Learning for the Model-free Risk-constrained Linear Quadratic Regulator
• Improve Single-Point Zeroth-Order Optimization Using High-Pass and Low-Pass Filters
• Distributed Online Linear Quadratic Control for Linear Time-invariant Systems
• Robust Reinforcement Learning: A Case Study in Linear Quadratic Regulation
• Regret Analysis of Distributed Online LQR Control for Unknown LTI Systems
• Zeroth-Order Non-Convex Optimization for Cooperative Multi-Agent Systems with Diminishing Step Size and Smoothing Radius
• Small errors in random zeroth-order optimization are imaginary
• Online Policy Gradient for Model Free Learning of Linear Quadratic Regulators with $\sqrt{T}$ Regret
• Model-Free Design of Stochastic LQR Controller from Reinforcement Learning and Primal-Dual Optimization Perspective
• Sample Complexity of the Robust LQG Regulator with Coprime Factors Uncertainty
• Model-Free $\mu$ Synthesis via Adversarial Reinforcement Learning