Learning Linear-Quadratic Regulators Efficiently with only $\sqrtT$ Regret

Alon Cohen; Tomer Koren; Yishay Mansour

ICML 2019oral224 citations

Learning Linear-Quadratic Regulators Efficiently with only $\sqrtT$ Regret

Abstract

We present the first computationally-efficient algorithm with $\widetilde{O}(\sqrt{T})$ regret for learning in Linear Quadratic Control systems with unknown dynamics. By that, we resolve an open question of Abbasi-Yadkori and Szepesvari (2011) and Dean,Mania, Matni, Recht, and Tu (2018).

BibTeX

@InProceedings{pmlr-v97-cohen19b,
  title = 	 {Learning Linear-Quadratic Regulators Efficiently with only $\sqrt{T}$ Regret},
  author =       {Cohen, Alon and Koren, Tomer and Mansour, Yishay},
  booktitle = 	 {Proceedings of the 36th International Conference on Machine Learning},
  pages = 	 {1300--1309},
  year = 	 {2019},
  editor = 	 {Chaudhuri, Kamalika and Salakhutdinov, Ruslan},
  volume = 	 {97},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {09--15 Jun},
  publisher =    {PMLR},
  pdf = 	 {http://proceedings.mlr.press/v97/cohen19b/cohen19b.pdf},
  url = 	 {https://proceedings.mlr.press/v97/cohen19b.html},
  abstract = 	 {We present the first computationally-efficient algorithm with $\widetilde{O}(\sqrt{T})$ regret for learning in Linear Quadratic Control systems with unknown dynamics. By that, we resolve an open question of Abbasi-Yadkori and Szepesvari (2011) and Dean,Mania, Matni, Recht, and Tu (2018).}
}