{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:15:01Z","timestamp":1750220101259,"version":"3.41.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,2,24]],"date-time":"2022-02-24T00:00:00Z","timestamp":1645660800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2022,2,24]]},"abstract":"<jats:p>We consider the problem of controlling a Linear Quadratic Regulator (LQR) system over a finite horizon T with fixed and known cost matrices Q,R, but unknown and non-stationary dynamics A_t, B_t. The sequence of dynamics matrices can be arbitrary, but with a total variation, V_T, assumed to be o(T) and unknown to the controller. Under the assumption that a sequence of stabilizing, but potentially sub-optimal controllers is available for all t, we present an algorithm that achieves the optimal dynamic regret of O(V_T^2\/5 T^3\/5 ). With piecewise constant dynamics, our algorithm achieves the optimal regret of O(sqrtST ) where S is the number of switches. The crux of our algorithm is an adaptive non-stationarity detection strategy, which builds on an approach recently developed for contextual Multi-armed Bandit problems. We also argue that non-adaptive forgetting (e.g., restarting or using sliding window learning with a static window size) may not be regret optimal for the LQR problem, even when the window size is optimally tuned with the knowledge of $V_T$. The main technical challenge in the analysis of our algorithm is to prove that the ordinary least squares (OLS) estimator has a small bias when the parameter to be estimated is non-stationary. Our analysis also highlights that the key motif driving the regret is that the LQR problem is in spirit a bandit problem with linear feedback and locally quadratic cost. This motif is more universal than the LQR problem itself, and therefore we believe our results should find wider application.<\/jats:p>","DOI":"10.1145\/3508029","type":"journal-article","created":{"date-parts":[[2022,2,28]],"date-time":"2022-02-28T23:44:29Z","timestamp":1646091869000},"page":"1-72","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Dynamic Regret Minimization for Control of Non-stationary Linear Dynamical Systems"],"prefix":"10.1145","volume":"6","author":[{"given":"Yuwei","family":"Luo","sequence":"first","affiliation":[{"name":"Stanford University, Stanford, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Varun","family":"Gupta","sequence":"additional","affiliation":[{"name":"University of Chicago, Chicago, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mladen","family":"Kolar","sequence":"additional","affiliation":[{"name":"University of Chicago, Chicago, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,2,28]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Yasin Abbasi-Yadkori D\u00e1vid P\u00e1l and Csaba Szepesv\u00e1ri. 2011. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems. 2312--2320.  Yasin Abbasi-Yadkori D\u00e1vid P\u00e1l and Csaba Szepesv\u00e1ri. 2011. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems. 2312--2320."},{"key":"e_1_2_1_2_1","volume-title":"Conference on Learning Theory. 1--26","author":"Abbasi-Yadkori Yasin","year":"2011","unstructured":"Yasin Abbasi-Yadkori and Csaba Szepesv\u00e1ri . 2011 . Regret bounds for the adaptive control of linear quadratic systems . In Conference on Learning Theory. 1--26 . Yasin Abbasi-Yadkori and Csaba Szepesv\u00e1ri. 2011. Regret bounds for the adaptive control of linear quadratic systems. In Conference on Learning Theory. 1--26."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1971.1099818"},{"volume-title":"Dynamic programming and optimal control","author":"Bertsekas Dimitri","key":"e_1_2_1_4_1","unstructured":"Dimitri Bertsekas . 2012. Dynamic programming and optimal control : Volume I . Vol. 1. Athena scientific. Dimitri Bertsekas. 2012. Dynamic programming and optimal control: Volume I. Vol. 1. Athena scientific."},{"key":"e_1_2_1_5_1","volume-title":"Stochastic multi-armed-bandit problem with non-stationary rewards. Advances in neural information processing systems","author":"Besbes Omar","year":"2014","unstructured":"Omar Besbes , Yonatan Gur , and Assaf Zeevi . 2014. Stochastic multi-armed-bandit problem with non-stationary rewards. Advances in neural information processing systems , Vol. 27 ( 2014 ), 199--207. Omar Besbes, Yonatan Gur, and Assaf Zeevi. 2014. Stochastic multi-armed-bandit problem with non-stationary rewards. Advances in neural information processing systems , Vol. 27 (2014), 199--207."},{"key":"e_1_2_1_6_1","unstructured":"Nicholas M Boffi Stephen Tu and Jean-Jacques E Slotine. 2021. Regret bounds for adaptive nonlinear control. In Learning for Dynamics and Control. PMLR 471--483.  Nicholas M Boffi Stephen Tu and Jean-Jacques E Slotine. 2021. Regret bounds for adaptive nonlinear control. In Learning for Dynamics and Control. PMLR 471--483."},{"key":"e_1_2_1_7_1","volume-title":"International Conference on Machine Learning. PMLR, 1328--1337","author":"Cassel Asaf","year":"2020","unstructured":"Asaf Cassel , Alon Cohen , and Tomer Koren . 2020 . Logarithmic regret for learning linear quadratic regulators efficiently . In International Conference on Machine Learning. PMLR, 1328--1337 . Asaf Cassel, Alon Cohen, and Tomer Koren. 2020. Logarithmic regret for learning linear quadratic regulators efficiently. In International Conference on Machine Learning. PMLR, 1328--1337."},{"key":"e_1_2_1_8_1","unstructured":"Yifang Chen Chung-Wei Lee Haipeng Luo and Chen-Yu Wei. 2019. A New Algorithm for Non-stationary Contextual Bandits: Efficient Optimal and Parameter-free. In COLT. 696--726. http:\/\/proceedings.mlr.press\/v99\/chen19b.html  Yifang Chen Chung-Wei Lee Haipeng Luo and Chen-Yu Wei. 2019. A New Algorithm for Non-stationary Contextual Bandits: Efficient Optimal and Parameter-free. In COLT. 696--726. http:\/\/proceedings.mlr.press\/v99\/chen19b.html"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of Machine Learning Research (Proceedings of Machine Learning Research","volume":"1087","author":"Cheung Wang Chi","year":"2019","unstructured":"Wang Chi Cheung , David Simchi-Levi , and Ruihao Zhu . 2019 a. Learning to Optimize under Non-Stationarity . In Proceedings of Machine Learning Research (Proceedings of Machine Learning Research , Vol. 89), Kamalika Chaudhuri and Masashi Sugiyama (Eds.). PMLR, 1079-- 1087 . http:\/\/proceedings.mlr.press\/v89\/cheung19b.html Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. 2019 a. Learning to Optimize under Non-Stationarity. In Proceedings of Machine Learning Research (Proceedings of Machine Learning Research, Vol. 89), Kamalika Chaudhuri and Masashi Sugiyama (Eds.). PMLR, 1079--1087. http:\/\/proceedings.mlr.press\/v89\/cheung19b.html"},{"key":"e_1_2_1_10_1","volume-title":"2019 b. Non-stationary reinforcement learning: The blessing of (more) optimism. Available at SSRN 3397818","author":"Cheung Wang Chi","year":"2019","unstructured":"Wang Chi Cheung , David Simchi-Levi , and Ruihao Zhu . 2019 b. Non-stationary reinforcement learning: The blessing of (more) optimism. Available at SSRN 3397818 ( 2019 ). Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. 2019 b. Non-stationary reinforcement learning: The blessing of (more) optimism. Available at SSRN 3397818 (2019)."},{"key":"e_1_2_1_11_1","first-page":"340","article-title":"Control methods for macroeconomic policy analysis","volume":"66","author":"Chow Gregory C","year":"1976","unstructured":"Gregory C Chow . 1976 . Control methods for macroeconomic policy analysis . The American Economic Review , Vol. 66 , 2 (1976), 340 -- 345 . Gregory C Chow. 1976. Control methods for macroeconomic policy analysis. The American Economic Review , Vol. 66, 2 (1976), 340--345.","journal-title":"The American Economic Review"},{"key":"e_1_2_1_12_1","volume-title":"Online linear quadratic control. arXiv preprint arXiv:1806.07104","author":"Cohen Alon","year":"2018","unstructured":"Alon Cohen , Avinatan Hassidim , Tomer Koren , Nevena Lazic , Yishay Mansour , and Kunal Talwar . 2018. Online linear quadratic control. arXiv preprint arXiv:1806.07104 ( 2018 ). Alon Cohen, Avinatan Hassidim, Tomer Koren, Nevena Lazic, Yishay Mansour, and Kunal Talwar. 2018. Online linear quadratic control. arXiv preprint arXiv:1806.07104 (2018)."},{"key":"e_1_2_1_13_1","volume-title":"Learning Linear-Quadratic Regulators Efficiently with only $sqrtT$ Regret. arxiv","author":"Cohen Alon","year":"1902","unstructured":"Alon Cohen , Tomer Koren , and Yishay Mansour . 2019. Learning Linear-Quadratic Regulators Efficiently with only $sqrtT$ Regret. arxiv : 1902 .06223 [cs.LG] Alon Cohen, Tomer Koren, and Yishay Mansour. 2019. Learning Linear-Quadratic Regulators Efficiently with only $sqrtT$ Regret. arxiv: 1902.06223 [cs.LG]"},{"key":"e_1_2_1_14_1","volume-title":"International Conference on Machine Learning . PMLR, 1405--1411","author":"Daniely Amit","year":"2015","unstructured":"Amit Daniely , Alon Gonen , and Shai Shalev-Shwartz . 2015 . Strongly adaptive online learning . In International Conference on Machine Learning . PMLR, 1405--1411 . Amit Daniely, Alon Gonen, and Shai Shalev-Shwartz. 2015. Strongly adaptive online learning. In International Conference on Machine Learning . PMLR, 1405--1411."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/3327144.3327332"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2018.2883241"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.automatica.2020.108950"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/9.59806"},{"key":"e_1_2_1_19_1","volume-title":"A sliding-window algorithm for Markov decision processes with arbitrarily changing rewards and transitions. arXiv preprint arXiv:1805.10066","author":"Gajane Pratik","year":"2018","unstructured":"Pratik Gajane , Ronald Ortner , and Peter Auer . 2018. A sliding-window algorithm for Markov decision processes with arbitrarily changing rewards and transitions. arXiv preprint arXiv:1805.10066 ( 2018 ). Pratik Gajane, Ronald Ortner, and Peter Auer. 2018. A sliding-window algorithm for Markov decision processes with arbitrarily changing rewards and transitions. arXiv preprint arXiv:1805.10066 (2018)."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/2050345.2050365"},{"key":"e_1_2_1_21_1","volume-title":"Regret-optimal Estimation and Contro. arXiv preprint arXiv:2106.12097","author":"Goel Gautam","year":"2021","unstructured":"Gautam Goel and Babak Hassibi . 2021. Regret-optimal Estimation and Contro. arXiv preprint arXiv:2106.12097 ( 2021 ). Gautam Goel and Babak Hassibi. 2021. Regret-optimal Estimation and Contro. arXiv preprint arXiv:2106.12097 (2021)."},{"key":"e_1_2_1_22_1","volume-title":"Adaptive regret for control of time-varying dynamics. arXiv preprint arXiv:2007.04393","author":"Gradu Paula","year":"2020","unstructured":"Paula Gradu , Elad Hazan , and Edgar Minasyan . 2020. Adaptive regret for control of time-varying dynamics. arXiv preprint arXiv:2007.04393 ( 2020 ). Paula Gradu, Elad Hazan, and Edgar Minasyan. 2020. Adaptive regret for control of time-varying dynamics. arXiv preprint arXiv:2007.04393 (2020)."},{"key":"e_1_2_1_23_1","volume-title":"Hitting-time and occupation-time bounds implied by drift analysis with applications. Advances in Applied probability","author":"Hajek Bruce","year":"1982","unstructured":"Bruce Hajek . 1982. Hitting-time and occupation-time bounds implied by drift analysis with applications. Advances in Applied probability ( 1982 ), 502--525. Bruce Hajek. 1982. Hitting-time and occupation-time bounds implied by drift analysis with applications. Advances in Applied probability (1982), 502--525."},{"key":"e_1_2_1_24_1","unstructured":"Elad Hazan Sham Kakade and Karan Singh. 2020. The nonstochastic control problem. In Algorithmic Learning Theory. PMLR 408--421.  Elad Hazan Sham Kakade and Karan Singh. 2020. The nonstochastic control problem. In Algorithmic Learning Theory. PMLR 408--421."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1553374.1553425"},{"key":"e_1_2_1_26_1","volume-title":"Tracking the best expert. Machine learning","author":"Herbster Mark","year":"1998","unstructured":"Mark Herbster and Manfred K Warmuth . 1998. Tracking the best expert. Machine learning , Vol. 32 , 2 ( 1998 ), 151--178. Mark Herbster and Manfred K Warmuth. 1998. Tracking the best expert. Machine learning , Vol. 32, 2 (1998), 151--178."},{"key":"e_1_2_1_27_1","unstructured":"Morteza Ibrahimi Adel Javanmard and Benjamin V Roy. 2012. Efficient reinforcement learning for high dimensional linear quadratic systems. In Advances in Neural Information Processing Systems. 2636--2644.  Morteza Ibrahimi Adel Javanmard and Benjamin V Roy. 2012. Efficient reinforcement learning for high dimensional linear quadratic systems. In Advances in Neural Information Processing Systems. 2636--2644."},{"key":"e_1_2_1_28_1","unstructured":"Yassir Jedra and Alexandre Proutiere. 2021. Minimal Expected Regret in Linear Quadratic Control. arxiv: 2109.14429 [cs.LG]  Yassir Jedra and Alexandre Proutiere. 2021. Minimal Expected Regret in Linear Quadratic Control. arxiv: 2109.14429 [cs.LG]"},{"key":"e_1_2_1_29_1","volume-title":"Adaptive estimation of a quadratic functional by model selection. Annals of Statistics","author":"Laurent Beatrice","year":"2000","unstructured":"Beatrice Laurent and Pascal Massart . 2000. Adaptive estimation of a quadratic functional by model selection. Annals of Statistics ( 2000 ), 1302--1338. Beatrice Laurent and Pascal Massart. 2000. Adaptive estimation of a quadratic functional by model selection. Annals of Statistics (2000), 1302--1338."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/2946645.2946684"},{"key":"e_1_2_1_31_1","volume-title":"Certainty equivalence is efficient for linear quadratic control. arXiv preprint arXiv:1902.07826","author":"Mania Horia","year":"2019","unstructured":"Horia Mania , Stephen Tu , and Benjamin Recht . 2019. Certainty equivalence is efficient for linear quadratic control. arXiv preprint arXiv:1902.07826 ( 2019 ). Horia Mania, Stephen Tu, and Benjamin Recht. 2019. Certainty equivalence is efficient for linear quadratic control. arXiv preprint arXiv:1902.07826 (2019)."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1561\/1700000031"},{"key":"e_1_2_1_33_1","unstructured":"Ronald Ortner Pratik Gajane and Peter Auer. 2020. Variational regret bounds for reinforcement learning. In Uncertainty in Artificial Intelligence. PMLR 81--90.  Ronald Ortner Pratik Gajane and Peter Auer. 2020. Variational regret bounds for reinforcement learning. In Uncertainty in Artificial Intelligence. PMLR 81--90."},{"key":"e_1_2_1_34_1","volume-title":"Garnett (Eds.)","volume":"32","author":"Russac Yoan","year":"2019","unstructured":"Yoan Russac , Claire Vernade , and Olivier Capp\u00e9 . 2019 . Weighted Linear Bandits for Non-Stationary Environments. In Advances in Neural Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. dtextquotesingle Alch\u00e9-Buc, E. Fox, and R . Garnett (Eds.) , Vol. 32 . Curran Associates, Inc. https:\/\/proceedings.neurips.cc\/paper\/ 2019\/file\/263fc48aae39f219b4c71d9d4bb4aed2-Paper.pdf Yoan Russac, Claire Vernade, and Olivier Capp\u00e9. 2019. Weighted Linear Bandits for Non-Stationary Environments. In Advances in Neural Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. dtextquotesingle Alch\u00e9-Buc, E. Fox, and R. Garnett (Eds.), Vol. 32. Curran Associates, Inc. https:\/\/proceedings.neurips.cc\/paper\/2019\/file\/263fc48aae39f219b4c71d9d4bb4aed2-Paper.pdf"},{"key":"e_1_2_1_35_1","volume-title":"International Conference on Machine Learning . PMLR, 8937--8948","author":"Simchowitz Max","year":"2020","unstructured":"Max Simchowitz and Dylan Foster . 2020 . Naive exploration is optimal for online LQR . In International Conference on Machine Learning . PMLR, 8937--8948 . Max Simchowitz and Dylan Foster. 2020. Naive exploration is optimal for online LQR. In International Conference on Machine Learning . PMLR, 8937--8948."},{"key":"e_1_2_1_36_1","volume-title":"Conference on Learning Theory. PMLR, 3320--3436","author":"Simchowitz Max","year":"2020","unstructured":"Max Simchowitz , Karan Singh , and Elad Hazan . 2020 . Improper learning for non-stochastic control . In Conference on Learning Theory. PMLR, 3320--3436 . Max Simchowitz, Karan Singh, and Elad Hazan. 2020. Improper learning for non-stochastic control. In Conference on Learning Theory. PMLR, 3320--3436."},{"key":"e_1_2_1_37_1","volume-title":"Underactuated robotics: Learning, planning, and control for efficient and agile machines course notes for MIT 6.832. Working draft edition","author":"Tedrake Russ","year":"2009","unstructured":"Russ Tedrake . 2009. Underactuated robotics: Learning, planning, and control for efficient and agile machines course notes for MIT 6.832. Working draft edition , Vol. 3 ( 2009 ). Russ Tedrake. 2009. Underactuated robotics: Learning, planning, and control for efficient and agile machines course notes for MIT 6.832. Working draft edition , Vol. 3 (2009)."},{"key":"e_1_2_1_38_1","volume-title":"Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027","author":"Vershynin Roman","year":"2010","unstructured":"Roman Vershynin . 2010. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027 ( 2010 ). Roman Vershynin. 2010. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027 (2010)."},{"key":"e_1_2_1_39_1","volume-title":"Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach. arXiv preprint arXiv:2102.05406","author":"Wei Chen-Yu","year":"2021","unstructured":"Chen-Yu Wei and Haipeng Luo . 2021. Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach. arXiv preprint arXiv:2102.05406 ( 2021 ). Chen-Yu Wei and Haipeng Luo. 2021. Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach. arXiv preprint arXiv:2102.05406 (2021)."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1090.0397"},{"key":"e_1_2_1_41_1","volume-title":"Non-stationary linear bandits revisited. arXiv preprint arXiv:2103.05324","author":"Zhao Peng","year":"2021","unstructured":"Peng Zhao and Lijun Zhang . 2021. Non-stationary linear bandits revisited. arXiv preprint arXiv:2103.05324 ( 2021 ). Peng Zhao and Lijun Zhang. 2021. Non-stationary linear bandits revisited. arXiv preprint arXiv:2103.05324 (2021)."},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 20th international conference on machine learning (icml-03)","author":"Zinkevich Martin","year":"2003","unstructured":"Martin Zinkevich . 2003 . Online convex programming and generalized infinitesimal gradient ascent . In Proceedings of the 20th international conference on machine learning (icml-03) . 928--936. Martin Zinkevich. 2003. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03) . 928--936."}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3508029","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3508029","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:10:18Z","timestamp":1750183818000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3508029"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,24]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,2,24]]}},"alternative-id":["10.1145\/3508029"],"URL":"https:\/\/doi.org\/10.1145\/3508029","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2022,2,24]]},"assertion":[{"value":"2022-02-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}