Adaptive Regret for Control of Time-Varying Dynamics

Paula Gradu, Elad Hazan, Edgar Minasyan
Proceedings of The 5th Annual Learning for Dynamics and Control Conference, PMLR 211:560-572, 2023.

Abstract

We consider the problem of online control of systems with time-varying linear dynamics. To state meaningful guarantees over changing environments, we introduce the metric of {\it adaptive regret} to the field of control. This metric, originally studied in online learning, measures performance in terms of regret against the best policy in hindsight on {\it any interval in time}, and thus captures the adaptation of the controller to changing dynamics. Our main contribution is a novel efficient meta-algorithm: it converts a controller with sublinear regret bounds into one with sublinear {\it adaptive regret} bounds in the setting of time-varying linear dynamical systems. The underlying technical innovation is the first adaptive regret bound for the more general framework of online convex optimization with memory. Furthermore, we give a lower bound showing that our attained adaptive regret bound is nearly tight for this general framework.

Cite this Paper

BibTeX
@InProceedings{pmlr-v211-gradu23a, title = {Adaptive Regret for Control of Time-Varying Dynamics}, author = {Gradu, Paula and Hazan, Elad and Minasyan, Edgar}, booktitle = {Proceedings of The 5th Annual Learning for Dynamics and Control Conference}, pages = {560--572}, year = {2023}, editor = {Matni, Nikolai and Morari, Manfred and Pappas, George J.}, volume = {211}, series = {Proceedings of Machine Learning Research}, month = {15--16 Jun}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v211/gradu23a/gradu23a.pdf}, url = {https://proceedings.mlr.press/v211/gradu23a.html}, abstract = {We consider the problem of online control of systems with time-varying linear dynamics. To state meaningful guarantees over changing environments, we introduce the metric of {\it adaptive regret} to the field of control. This metric, originally studied in online learning, measures performance in terms of regret against the best policy in hindsight on {\it any interval in time}, and thus captures the adaptation of the controller to changing dynamics. Our main contribution is a novel efficient meta-algorithm: it converts a controller with sublinear regret bounds into one with sublinear {\it adaptive regret} bounds in the setting of time-varying linear dynamical systems. The underlying technical innovation is the first adaptive regret bound for the more general framework of online convex optimization with memory. Furthermore, we give a lower bound showing that our attained adaptive regret bound is nearly tight for this general framework.} }
Endnote
%0 Conference Paper %T Adaptive Regret for Control of Time-Varying Dynamics %A Paula Gradu %A Elad Hazan %A Edgar Minasyan %B Proceedings of The 5th Annual Learning for Dynamics and Control Conference %C Proceedings of Machine Learning Research %D 2023 %E Nikolai Matni %E Manfred Morari %E George J. Pappas %F pmlr-v211-gradu23a %I PMLR %P 560--572 %U https://proceedings.mlr.press/v211/gradu23a.html %V 211 %X We consider the problem of online control of systems with time-varying linear dynamics. To state meaningful guarantees over changing environments, we introduce the metric of {\it adaptive regret} to the field of control. This metric, originally studied in online learning, measures performance in terms of regret against the best policy in hindsight on {\it any interval in time}, and thus captures the adaptation of the controller to changing dynamics. Our main contribution is a novel efficient meta-algorithm: it converts a controller with sublinear regret bounds into one with sublinear {\it adaptive regret} bounds in the setting of time-varying linear dynamical systems. The underlying technical innovation is the first adaptive regret bound for the more general framework of online convex optimization with memory. Furthermore, we give a lower bound showing that our attained adaptive regret bound is nearly tight for this general framework.
APA
Gradu, P., Hazan, E. & Minasyan, E.. (2023). Adaptive Regret for Control of Time-Varying Dynamics. Proceedings of The 5th Annual Learning for Dynamics and Control Conference, in Proceedings of Machine Learning Research 211:560-572 Available from https://proceedings.mlr.press/v211/gradu23a.html.

Related Material