# Logarithmic Regret for Online Control

arXiv: https://arxiv.org/abs/1909.05062 · HTML: https://mlsanity.com/paper/1909.05062/

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Sep 2019.

## Built on by (most cited first, 30 of 38)

- [Adversarial Tracking Control via Strongly Adaptive Online Learning with Memory](https://mlsanity.com/paper/2102.01623/) (2021)
- [Lazy OCO: Online Convex Optimization on a Switching Budget](https://mlsanity.com/paper/2102.03803/) (2021)
- [Sample-Efficient Linear Representation Learning from Non-IID Non-Isotropic Data](https://mlsanity.com/paper/2308.04428/) (2023)
- [Online Policy Gradient for Model Free Learning of Linear Quadratic Regulators with √T Regret](https://mlsanity.com/paper/2102.12608/) (2021)
- [Safe Adaptive Learning-based Control for Constrained Linear Quadratic Regulators with Regret Guarantees](https://mlsanity.com/paper/2111.00411/) (2021)
- [Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learning](https://mlsanity.com/paper/2205.11470/) (2022)
- [A Regret Minimization Approach to Iterative Learning Control](https://mlsanity.com/paper/2102.13478/) (2021)
- [Optimal Rates for Bandit Nonstochastic Control](https://mlsanity.com/paper/2305.15352/) (2023)
- [Regret Analysis of Distributed Online LQR Control for Unknown LTI Systems](https://mlsanity.com/paper/2105.07310/) (2021)
- [Adaptive Composite Online Optimization: Predictions in Static and Dynamic Environments](https://mlsanity.com/paper/2205.00446/) (2022)
- [Online Convex Optimization with Unbounded Memory](https://mlsanity.com/paper/2210.09903/) (2022)
- [Universal Sequence Preconditioning](https://mlsanity.com/paper/2502.06545/) (2025)
- [Online Optimization with Feedback Delay and Nonlinear Switching Cost](https://mlsanity.com/paper/2111.00095/) (2021)
- [Rate-Optimal Online Convex Optimization in Adaptive Linear Control](https://mlsanity.com/paper/2206.01426/) (2022)
- [Online Nonstochastic Control with Adversarial and Static Constraints](https://mlsanity.com/paper/2302.02426/) (2023)
- [Predictive Linear Online Tracking for Unknown Targets](https://mlsanity.com/paper/2402.10036/) (2024)
- [Finite-time System Identification and Adaptive Control in Autoregressive Exogenous Systems](https://mlsanity.com/paper/2108.11959/) (2021)
- [Efficient Online Linear Control with Stochastic Convex Costs and Unknown Dynamics](https://mlsanity.com/paper/2203.01170/) (2022)
- [Online Learning for Predictive Control with Provable Regret Guarantees](https://mlsanity.com/paper/2111.15041/) (2021)
- [Implications of Regret on Stability of Linear Dynamical Systems](https://mlsanity.com/paper/2211.07411/) (2022)
- [Dynamical Linear Bandits](https://mlsanity.com/paper/2211.08997/) (2022)
- [Adaptive Online Non-stochastic Control](https://mlsanity.com/paper/2310.02261/) (2023)
- [Optimistic Online Non-stochastic Control via FTRL](https://mlsanity.com/paper/2404.03309/) (2024)
- [Online Control in Population Dynamics](https://mlsanity.com/paper/2406.01799/) (2024)
- [Combining Federated Learning and Control: A Survey](https://mlsanity.com/paper/2407.11069/) (2024)
- [Predictive Control and Regret Analysis of Non-Stationary MDP with Look-ahead Information](https://mlsanity.com/paper/2409.08434/) (2024)
- [Tight Rates for Bandit Control Beyond Quadratics](https://mlsanity.com/paper/2410.00993/) (2024)
- [A New Approach to Controlling Linear Dynamical Systems](https://mlsanity.com/paper/2504.03952/) (2025)
- [Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memory](https://mlsanity.com/paper/2602.06902/) (2026)
- [Regret Analysis of Distributed Online Control for LTI Systems with Adversarial Disturbances](https://mlsanity.com/paper/2310.03206/) (2023)

## Abstract (arXiv)

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(√T), where T is the time horizon. We show that the optimal regret in this setting can be significantly smaller, scaling as O(poly(log T)). This regret bound is achieved by two different efficient iterative methods, online gradient descent and online natural gradient.