The Nonstochastic Control Problem

Elad Hazan, Sham Kakade, Karan Singh
Proceedings of the 31st International Conference on Algorithmic Learning Theory, PMLR 117:408-421, 2020.

Abstract

We consider the problem of controlling an unknown linear dynamical system in the presence of (nonstochastic) adversarial perturbations and adversarial convex loss functions. In contrast to classical control, the a priori determination of an optimal controller here is hindered by the latter’s dependence on the yet unknown perturbations and costs. Instead, we measure regret against an optimal linear policy in hindsight, and give the first efficient algorithm that guarantees a sublinear regret bound, scaling as T^(2/3), in this setting.

Cite this Paper

BibTeX
@InProceedings{pmlr-v117-hazan20a, title = {The Nonstochastic Control Problem}, author = {Hazan, Elad and Kakade, Sham and Singh, Karan}, booktitle = {Proceedings of the 31st International Conference on Algorithmic Learning Theory}, pages = {408--421}, year = {2020}, editor = {Kontorovich, Aryeh and Neu, Gergely}, volume = {117}, series = {Proceedings of Machine Learning Research}, month = {08 Feb--11 Feb}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v117/hazan20a/hazan20a.pdf}, url = {https://proceedings.mlr.press/v117/hazan20a.html}, abstract = {We consider the problem of controlling an unknown linear dynamical system in the presence of (nonstochastic) adversarial perturbations and adversarial convex loss functions. In contrast to classical control, the a priori determination of an optimal controller here is hindered by the latter’s dependence on the yet unknown perturbations and costs. Instead, we measure regret against an optimal linear policy in hindsight, and give the first efficient algorithm that guarantees a sublinear regret bound, scaling as T^(2/3), in this setting.} }
Endnote
%0 Conference Paper %T The Nonstochastic Control Problem %A Elad Hazan %A Sham Kakade %A Karan Singh %B Proceedings of the 31st International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Aryeh Kontorovich %E Gergely Neu %F pmlr-v117-hazan20a %I PMLR %P 408--421 %U https://proceedings.mlr.press/v117/hazan20a.html %V 117 %X We consider the problem of controlling an unknown linear dynamical system in the presence of (nonstochastic) adversarial perturbations and adversarial convex loss functions. In contrast to classical control, the a priori determination of an optimal controller here is hindered by the latter’s dependence on the yet unknown perturbations and costs. Instead, we measure regret against an optimal linear policy in hindsight, and give the first efficient algorithm that guarantees a sublinear regret bound, scaling as T^(2/3), in this setting.
APA
Hazan, E., Kakade, S. & Singh, K.. (2020). The Nonstochastic Control Problem. Proceedings of the 31st International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 117:408-421 Available from https://proceedings.mlr.press/v117/hazan20a.html.

Related Material