Logarithmic Regret for Adversarial Online Control

Dylan Foster, Max Simchowitz
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:3211-3221, 2020.

Abstract

We introduce a new algorithm for online linear-quadratic control in a known system subject to adversarial disturbances. Existing regret bounds for this setting scale as $\sqrt{T}$ unless strong stochastic assumptions are imposed on the disturbance process. We give the first algorithm with logarithmic regret for arbitrary adversarial disturbance sequences, provided the state and control costs are given by known quadratic functions. Our algorithm and analysis use a characterization for the optimal offline control law to reduce the online control problem to (delayed) online learning with approximate advantage functions. Compared to previous techniques, our approach does not need to control movement costs for the iterates, leading to logarithmic regret.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-foster20b, title = {Logarithmic Regret for Adversarial Online Control}, author = {Foster, Dylan and Simchowitz, Max}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {3211--3221}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/foster20b/foster20b.pdf}, url = {https://proceedings.mlr.press/v119/foster20b.html}, abstract = {We introduce a new algorithm for online linear-quadratic control in a known system subject to adversarial disturbances. Existing regret bounds for this setting scale as $\sqrt{T}$ unless strong stochastic assumptions are imposed on the disturbance process. We give the first algorithm with logarithmic regret for arbitrary adversarial disturbance sequences, provided the state and control costs are given by known quadratic functions. Our algorithm and analysis use a characterization for the optimal offline control law to reduce the online control problem to (delayed) online learning with approximate advantage functions. Compared to previous techniques, our approach does not need to control movement costs for the iterates, leading to logarithmic regret.} }
Endnote
%0 Conference Paper %T Logarithmic Regret for Adversarial Online Control %A Dylan Foster %A Max Simchowitz %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-foster20b %I PMLR %P 3211--3221 %U https://proceedings.mlr.press/v119/foster20b.html %V 119 %X We introduce a new algorithm for online linear-quadratic control in a known system subject to adversarial disturbances. Existing regret bounds for this setting scale as $\sqrt{T}$ unless strong stochastic assumptions are imposed on the disturbance process. We give the first algorithm with logarithmic regret for arbitrary adversarial disturbance sequences, provided the state and control costs are given by known quadratic functions. Our algorithm and analysis use a characterization for the optimal offline control law to reduce the online control problem to (delayed) online learning with approximate advantage functions. Compared to previous techniques, our approach does not need to control movement costs for the iterates, leading to logarithmic regret.
APA
Foster, D. & Simchowitz, M.. (2020). Logarithmic Regret for Adversarial Online Control. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:3211-3221 Available from https://proceedings.mlr.press/v119/foster20b.html.

Related Material