mlsanityData to 7 Oct 2026

Optimal Dynamic Regret in LQR Control

arXiv 2206.09257 ↗First posted 18 Jun 2022cs.LG math.DS math.OCcited by 6

Not on the map. Why?

Abstract (arXiv)

We consider the problem of nonstochastic control with a sequence of quadratic losses, i.e., LQR control. We provide an efficient online algorithm that achieves an optimal dynamic (policy) regret of tildeO(maxn1/3 TV(M1:n)2/3, 1), where TV(M1:n) is the total variation of any oracle sequence of Disturbance Action policies parameterized by M1,...,Mn -- chosen in hindsight to cater to unknown nonstationarity. The rate improves the best known rate of tildeO(√n (TV(M1:n)+1) ) for general convex losses and we prove that it is information-theoretically optimal for LQR. Main technical components include the reduction of LQR to online linear regression with delayed feedback due to Foster and Simchowitz (2020), as well as a new proper learning algorithm with an optimal tildeO(n1/3) dynamic regret on a family of ``minibatched'' quadratic losses, which could be of independent interest.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 36 of its 60 references that are in the map. First posted on arXiv 18 Jun 2022.

Builds on

36 of 60 references.

References · 36

  1. 2015End-to-End Training of Deep Visuomotor Policiescited by 847
  2. 2019Introduction to Online Convex Optimizationcited by 793
  3. 2013Non-stationary Stochastic Optimizationcited by 173
  4. 2013Online Learning under Delayed Feedbackcited by 137
  5. 2018Adaptive Online Learning in Dynamic Environmentscited by 130
  6. 2018Black-Box Reductions for Parameter-free Online Learning in Banach Spacescited by 124
  7. 2015Strongly Adaptive Online Learningcited by 102
  8. 2015Online Optimization : Competing with Dynamic Comparatorscited by 99
  9. 2019Online Control with Adversarial Disturbancescited by 92
  10. 2020Dynamic Regret of Convex and Smooth Functionscited by 90
  11. 2020Improper Learning for Non-Stochastic Controlcited by 83
  12. 2016Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradientcited by 65
24 more
  1. 2018Online Linear Quadratic Controlcited by 55
  2. 2019The Nonstochastic Control Problemcited by 52
  3. 2016Improved Strongly Adaptive Online Learning using Coin Bettingcited by 48
  4. 2022Parameter-free Mirror Descentcited by 45
  5. 2020Logarithmic Regret for Adversarial Online Controlcited by 41
  6. 2021Optimal Dynamic Regret in Exp-Concave Online Learningcited by 39
  7. 2020Adaptive Regret for Control of Time-Varying Dynamicscited by 38
  8. 2020Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functionscited by 33
  9. 2021Non-stationary Online Learning with Memory and Non-stochastic Controlcited by 33
  10. 2019Online Forecasting of Total-Variation-bounded Sequencescited by 30
  11. 2022Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyondcited by 27
  12. 2018Smoothed Online Optimization for Regression and Controlcited by 26
  13. 2020Making Non-Stochastic Control (Almost) as Easy as Stochasticcited by 24
  14. 2020Non-Stochastic Control with Bandit Feedbackcited by 17
  15. 2019Dual Adaptivity: A Universal Algorithm for Minimizing the Adaptive Regret of Convex Functionscited by 15
  16. 2020Adaptive Online Estimation of Piecewise Polynomial Trendscited by 11
  17. 2020The Power of Linear Controllers in LQR Controlcited by 10
  18. 2020Bandit Linear Controlcited by 10
  19. 2021Regret-optimal Estimation and Controlcited by 10
  20. 2021An Optimal Reduction of TV-Denoising to Adaptive Online Learningcited by 9
  21. 2020Non-stationary Online Regressioncited by 6
  22. 2021Dynamic Regret Minimization for Control of Non-stationary Linear Dynamical Systemscited by 4
  23. 2021Dynamic Regret for Strongly Adaptive Methods and Optimality of Online KRRcited by 4
  24. 2022Spatially Adaptive Online Prediction of Piecewise Regular Functionscited by 1

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 3; 2025: 2.

6 papers.

  1. 2023Adapting to Continuous Covariate Shift via Online Density Ratio Estimationcited by 15
  2. 2024Online Linear Regression in Dynamic Environments via Discountingcited by 10
  3. 2025Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixabilitycited by 6
  4. 2024Predictive Linear Online Tracking for Unknown Targetscited by 5
  5. 2025Adapting to Online Distribution Shifts in Deep Learning: A Black-Box Approachcited by 2
  6. 2024Regret Analysis of Policy Optimization over Submanifolds for Linearly Constrained Online LQGcited by 0