# Online Control of Unknown Time-Varying Dynamical Systems arXiv: https://arxiv.org/abs/2202.07890 · HTML: https://mlsanity.com/paper/2202.07890/ ## Key facts - Cited by 13 papers in the map (data through 14 Oct 2026). - Builds on 25 of its 47 references that are in the map. - First posted on arXiv 16 Feb 2022. ## Builds on (most cited first, 25 of 25) - [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021) - [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019) - [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018) - [Naive Exploration is Optimal for Online LQR](https://mlsanity.com/paper/2001.09576/) (2020) - [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015) - [Online Control with Adversarial Disturbances](https://mlsanity.com/paper/1902.08721/) (2019) - [Information Theoretic Regret Bounds for Online Nonlinear Control](https://mlsanity.com/paper/2006.12466/) (2020) - [Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator](https://mlsanity.com/paper/1805.09388/) (2018) - [Improper Learning for Non-Stochastic Control](https://mlsanity.com/paper/2001.09254/) (2020) - [Non-asymptotic Identification of LTI Systems from a Single Trajectory](https://mlsanity.com/paper/1806.05722/) (2018) - [Learning Linear-Quadratic Regulators Efficiently with only √T Regret](https://mlsanity.com/paper/1902.06223/) (2019) - [The Nonstochastic Control Problem](https://mlsanity.com/paper/1911.12178/) (2019) - [Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems](https://mlsanity.com/paper/2003.11227/) (2020) - [Adaptive Regret for Control of Time-Varying Dynamics](https://mlsanity.com/paper/2007.04393/) (2020) - [Regret Bounds for Adaptive Nonlinear Control](https://mlsanity.com/paper/2011.13101/) (2020) - [Adaptive Regret of Convex and Smooth Functions](https://mlsanity.com/paper/1904.11681/) (2019) - [Making Non-Stochastic Control (Almost) as Easy as Stochastic](https://mlsanity.com/paper/2006.05910/) (2020) - [Learning the Linear Quadratic Regulator from Nonlinear Observations](https://mlsanity.com/paper/2010.03799/) (2020) - [Certainty Equivalent Perception-Based Control](https://mlsanity.com/paper/2008.12332/) (2020) - [A System Level Approach to Controller Synthesis](https://mlsanity.com/paper/1610.04815/) (2016) - [A Regret Minimization Approach to Iterative Learning Control](https://mlsanity.com/paper/2102.13478/) (2021) - [Regret Minimization in Partially Observable Linear Quadratic Control](https://mlsanity.com/paper/2002.00082/) (2020) - [Iterative Linearized Control: Stable Algorithms and Complexity Guarantees](https://mlsanity.com/paper/1908.07615/) (2019) - [On the Stability of Nonlinear Receding Horizon Control: A Geometric Perspective](https://mlsanity.com/paper/2103.15010/) (2021) - [Stable Online Control of Linear Time-Varying Systems](https://mlsanity.com/paper/2104.14134/) (2021) ## Built on by (most cited first, 13 of 13) - [Adaptive Gradient Methods with Local Guarantees](https://mlsanity.com/paper/2203.01400/) (2022) - [Online Convex Optimization with Unbounded Memory](https://mlsanity.com/paper/2210.09903/) (2022) - [Best of Both Worlds in Online Control: Competitive Ratio and Policy Regret](https://mlsanity.com/paper/2211.11219/) (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) - [A Nonstochastic Control Approach to Optimization](https://mlsanity.com/paper/2301.07902/) (2023) - [On the Computational Efficiency of Adaptive and Dynamic Regret Minimization](https://mlsanity.com/paper/2207.00646/) (2022) - [Online Nonstochastic Model-Free Reinforcement Learning](https://mlsanity.com/paper/2305.17552/) (2023) - [A New Approach to Controlling Linear Dynamical Systems](https://mlsanity.com/paper/2504.03952/) (2025) - [Learning to Control under Time-Varying Environment](https://mlsanity.com/paper/2206.02507/) (2022) - [Efficient Spectral Control of Partially Observed Linear Dynamical Systems](https://mlsanity.com/paper/2505.20943/) (2025) - [Online Multi-Agent Control with Adversarial Disturbances](https://mlsanity.com/paper/2506.18814/) (2025) - [T2S-MPC: Time-Embedded Online Adaptive Model Predictive Control for Time-Varying Dynamics](https://mlsanity.com/paper/2605.24852/) (2026) ## Abstract (arXiv) We study online control of time-varying linear systems with unknown dynamics in the nonstochastic control model. At a high level, we demonstrate that this setting is qualitatively harder than that of either unknown time-invariant or known time-varying dynamics, and complement our negative results with algorithmic upper bounds in regimes where sublinear regret is possible. More specifically, we study regret bounds with respect to common classes of policies: Disturbance Action (SLS), Disturbance Response (Youla), and linear feedback policies. While these three classes are essentially equivalent for LTI systems, we demonstrate that these equivalences break down for time-varying systems. We prove a lower bound that no algorithm can obtain sublinear regret with respect to the first two classes unless a certain measure of system variability also scales sublinearly in the horizon. Furthermore, we show that offline planning over the state linear feedback policies is NP-hard, suggesting hardness of the online learning problem. On the positive side, we give an efficient algorithm that attains a sublinear regret bound against the class of Disturbance Response policies up to the aforementioned system variability term. In fact, our algorithm enjoys sublinear adaptive regret bounds, which is a strictly stronger metric than standard regret and is more appropriate for time-varying systems. We sketch extensions to Disturbance Action policies and partial observation, and propose an inefficient algorithm for regret against linear state feedback policies.