Logarithmic Regret for Online Control

Abstract

We study optimal regret bounds for control in linear dynamical systems under adversarially changing strongly convex cost functions, given the knowledge of transition dynamics. This includes several well studied and fundamental frameworks such as the Kalman filter and the linear quadratic regulator. State of the art methods achieve regret which scales as $O(\sqrt{T})$, where $T$ is the time horizon. We show that the optimal regret in this setting can be significantly smaller, scaling as $O(\text{poly}(\log T))$. This regret bound is achieved by two different efficient iterative methods, online gradient descent and online natural gradient.

Cited by in corpus (32)

• Improper Learning for Non-Stochastic Control
• Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems
• Logarithmic Regret for Adversarial Online Control
• Naive Exploration is Optimal for Online LQR
• Online Optimization with Memory and Competitive Control
• Information Theoretic Regret Bounds for Online Nonlinear Control
• Black-Box Control for Linear Dynamical Systems
• Adaptive Regret for Control of Time-Varying Dynamics
• Safe Adaptive Learning-based Control for Constrained Linear Quadratic Regulators with Regret Guarantees
• Logarithmic Regret for Learning Linear Quadratic Regulators Efficiently
• Perturbation-based Regret Analysis of Predictive Control in Linear Time Varying Systems
• The Nonstochastic Control Problem
• The Power of Predictions in Online Control
• Making Non-Stochastic Control (Almost) as Easy as Stochastic
• Online Agnostic Boosting via Regret Minimization
• Non-Stochastic Control with Bandit Feedback
• Online Optimal Control with Affine Constraints
• An Iterative Riccati Algorithm for Online Linear Quadratic Control
• Distributed Online Linear Quadratic Control for Linear Time-invariant Systems
• A Regret Minimization Approach to Iterative Learning Control
• Regret Analysis of Distributed Online LQR Control for Unknown LTI Systems
• Online Robust Control of Nonlinear Systems with Large Uncertainty
• Bandit Linear Control
• When is Particle Filtering Efficient for Planning in Partially Observed Linear Dynamical Systems?
• Optimistic robust linear quadratic dual control
• Online Learning Robust Control of Nonlinear Dynamical Systems
• Lazy OCO: Online Convex Optimization on a Switching Budget
• Online Policy Gradient for Model Free Learning of Linear Quadratic Regulators with $\sqrt{T}$ Regret
• Regret Bounds for Adaptive Nonlinear Control
• Meta-Learning Guarantees for Online Receding Horizon Learning Control
• Adversarial Tracking Control via Strongly Adaptive Online Learning with Memory
• A Meta-Learning Control Algorithm with Provable Finite-Time Guarantees