Logarithmic Regret for Learning Linear Quadratic Regulators Efficiently

Asaf Cassel, Alon Cohen, Tomer Koren
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:1328-1337, 2020.

Abstract

We consider the problem of learning in Linear Quadratic Control systems whose transition parameters are initially unknown. Recent results in this setting have demonstrated efficient learning algorithms with regret growing with the square root of the number of decision steps. We present new efficient algorithms that achieve, perhaps surprisingly,regret that scales only (poly-)logarithmically with the number of steps, in two scenarios: when only the state transition matrix A is unknown, and when only the state-action transition matrix B is unknown and the optimal policy satisfies a certain non-degeneracy condition. On the other hand, we give a lower bound which shows that when the latter condition is violated, square root regret is unavoidable.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-cassel20a, title = {Logarithmic Regret for Learning Linear Quadratic Regulators Efficiently}, author = {Cassel, Asaf and Cohen, Alon and Koren, Tomer}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {1328--1337}, 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/cassel20a/cassel20a.pdf}, url = {https://proceedings.mlr.press/v119/cassel20a.html}, abstract = {We consider the problem of learning in Linear Quadratic Control systems whose transition parameters are initially unknown. Recent results in this setting have demonstrated efficient learning algorithms with regret growing with the square root of the number of decision steps. We present new efficient algorithms that achieve, perhaps surprisingly,regret that scales only (poly-)logarithmically with the number of steps, in two scenarios: when only the state transition matrix A is unknown, and when only the state-action transition matrix B is unknown and the optimal policy satisfies a certain non-degeneracy condition. On the other hand, we give a lower bound which shows that when the latter condition is violated, square root regret is unavoidable.} }
Endnote
%0 Conference Paper %T Logarithmic Regret for Learning Linear Quadratic Regulators Efficiently %A Asaf Cassel %A Alon Cohen %A Tomer Koren %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-cassel20a %I PMLR %P 1328--1337 %U https://proceedings.mlr.press/v119/cassel20a.html %V 119 %X We consider the problem of learning in Linear Quadratic Control systems whose transition parameters are initially unknown. Recent results in this setting have demonstrated efficient learning algorithms with regret growing with the square root of the number of decision steps. We present new efficient algorithms that achieve, perhaps surprisingly,regret that scales only (poly-)logarithmically with the number of steps, in two scenarios: when only the state transition matrix A is unknown, and when only the state-action transition matrix B is unknown and the optimal policy satisfies a certain non-degeneracy condition. On the other hand, we give a lower bound which shows that when the latter condition is violated, square root regret is unavoidable.
APA
Cassel, A., Cohen, A. & Koren, T.. (2020). Logarithmic Regret for Learning Linear Quadratic Regulators Efficiently. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:1328-1337 Available from https://proceedings.mlr.press/v119/cassel20a.html.

Related Material