Improper Learning for Non-Stochastic Control

Abstract

We consider the problem of controlling a possibly unknown linear dynamical system with adversarial perturbations, adversarially chosen convex loss functions, and partially observed states, known as non-stochastic control. We introduce a controller parametrization based on the denoised observations, and prove that applying online gradient descent to this parametrization yields a new controller which attains sublinear regret vs. a large class of closed-loop policies. In the fully-adversarial setting, our controller attains an optimal regret bound of $\sqrt{T}$-when the system is known, and, when combined with an initial stage of least-squares estimation, $T^{2/3}$ when the system is unknown; both yield the first sublinear regret for the partially observed setting. Our bounds are the first in the non-stochastic control setting that compete with \emph{all} stabilizing linear dynamical controllers, not just state feedback. Moreover, in the presence of semi-adversarial noise containing both stochastic and adversarial components, our controller attains the optimal regret bounds of $\mathrm{poly}(\log T)$ when the system is known, and $\sqrt{T}$ when unknown. To our knowledge, this gives the first end-to-end $\sqrt{T}$ regret for online Linear Quadratic Gaussian controller, and applies in a more general setting with adversarial losses and semi-adversarial noise.

References in corpus (6)

• On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
• Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
• Online Control with Adversarial Disturbances
• Logarithmic Regret for Online Control
• Online Least Squares Estimation with Self-Normalized Processes: An Application to Bandit Problems
• Naive Exploration is Optimal for Online LQR

Cited by in corpus (24)

• Non-asymptotic Identification of Linear Dynamical Systems Using Multiple Trajectories
• Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems
• Logarithmic Regret for Adversarial Online Control
• Near-Optimal Design of Safe Output Feedback Controllers from Noisy Data
• System-level, Input-output and New Parameterizations of Stabilizing Controllers, and Their Numerical Computation
• Black-Box Control for Linear Dynamical Systems
• DiffLoop: Tuning PID controllers by differentiating through the feedback loop
• Adaptive Regret for Control of Time-Varying Dynamics
• Non-stationary Online Learning with Memory and Non-stochastic Control
• Dynamic Regret Minimization for Control of Non-stationary Linear Dynamical Systems
• Certainty Equivalent Perception-Based Control
• Regret Analysis of Distributed Online LQR Control for Unknown LTI Systems
• When is Particle Filtering Efficient for Planning in Partially Observed Linear Dynamical Systems?
• Generating Adversarial Disturbances for Controller Verification
• Task-Optimal Exploration in Linear Dynamical Systems
• Provable Regret Bounds for Deep Online Learning and Control
• Towards a Dimension-Free Understanding of Adaptive Linear Control
• Regret-Optimal Filtering for Prediction and Estimation
• On the Sample Complexity of Decentralized Linear Quadratic Regulator with Partially Nested Information Structure
• Learning the Linear Quadratic Regulator from Nonlinear Observations
• Online Learning Robust Control of Nonlinear Dynamical Systems
• Sample Complexity of the Robust LQG Regulator with Coprime Factors Uncertainty
• Meta-Learning Guarantees for Online Receding Horizon Learning Control
• Adversarial Tracking Control via Strongly Adaptive Online Learning with Memory