Learning to Control Linear Systems can be Hard

Anastasios Tsiamis, Ingvar M Ziemann, Manfred Morari, Nikolai Matni, George J. Pappas
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:3820-3857, 2022.

Abstract

In this paper, we study the statistical difficulty of learning to control linear systems. We focus on two standard benchmarks, the sample complexity of stabilization, and the regret of the online learning of the Linear Quadratic Regulator (LQR). Prior results state that the statistical difficulty for both benchmarks scales polynomially with the system state dimension up to system-theoretic quantities. However, this does not reveal the whole picture. By utilizing minimax lower bounds for both benchmarks, we prove that there exist non-trivial classes of systems for which learning complexity scales dramatically, i.e. exponentially, with the system dimension. This situation arises in the case of underactuated systems, i.e. systems with fewer inputs than states. Such systems are structurally difficult to control and their system theoretic quantities can scale exponentially with the system dimension dominating learning complexity. Under some additional structural assumptions (bounding systems away from uncontrollability), we provide qualitatively matching upper bounds. We prove that learning complexity can be at most exponential with the controllability index of the system, that is the degree of underactuation.

Cite this Paper

BibTeX
@InProceedings{pmlr-v178-tsiamis22a, title = {Learning to Control Linear Systems can be Hard}, author = {Tsiamis, Anastasios and Ziemann, Ingvar M and Morari, Manfred and Matni, Nikolai and Pappas, George J.}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {3820--3857}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/tsiamis22a/tsiamis22a.pdf}, url = {https://proceedings.mlr.press/v178/tsiamis22a.html}, abstract = {In this paper, we study the statistical difficulty of learning to control linear systems. We focus on two standard benchmarks, the sample complexity of stabilization, and the regret of the online learning of the Linear Quadratic Regulator (LQR). Prior results state that the statistical difficulty for both benchmarks scales polynomially with the system state dimension up to system-theoretic quantities. However, this does not reveal the whole picture. By utilizing minimax lower bounds for both benchmarks, we prove that there exist non-trivial classes of systems for which learning complexity scales dramatically, i.e. exponentially, with the system dimension. This situation arises in the case of underactuated systems, i.e. systems with fewer inputs than states. Such systems are structurally difficult to control and their system theoretic quantities can scale exponentially with the system dimension dominating learning complexity. Under some additional structural assumptions (bounding systems away from uncontrollability), we provide qualitatively matching upper bounds. We prove that learning complexity can be at most exponential with the controllability index of the system, that is the degree of underactuation.} }
Endnote
%0 Conference Paper %T Learning to Control Linear Systems can be Hard %A Anastasios Tsiamis %A Ingvar M Ziemann %A Manfred Morari %A Nikolai Matni %A George J. Pappas %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-tsiamis22a %I PMLR %P 3820--3857 %U https://proceedings.mlr.press/v178/tsiamis22a.html %V 178 %X In this paper, we study the statistical difficulty of learning to control linear systems. We focus on two standard benchmarks, the sample complexity of stabilization, and the regret of the online learning of the Linear Quadratic Regulator (LQR). Prior results state that the statistical difficulty for both benchmarks scales polynomially with the system state dimension up to system-theoretic quantities. However, this does not reveal the whole picture. By utilizing minimax lower bounds for both benchmarks, we prove that there exist non-trivial classes of systems for which learning complexity scales dramatically, i.e. exponentially, with the system dimension. This situation arises in the case of underactuated systems, i.e. systems with fewer inputs than states. Such systems are structurally difficult to control and their system theoretic quantities can scale exponentially with the system dimension dominating learning complexity. Under some additional structural assumptions (bounding systems away from uncontrollability), we provide qualitatively matching upper bounds. We prove that learning complexity can be at most exponential with the controllability index of the system, that is the degree of underactuation.
APA
Tsiamis, A., Ziemann, I.M., Morari, M., Matni, N. & Pappas, G.J.. (2022). Learning to Control Linear Systems can be Hard. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:3820-3857 Available from https://proceedings.mlr.press/v178/tsiamis22a.html.

Related Material