Rate-Optimal Online Convex Optimization in Adaptive Linear Control
Abstract
We consider the problem of controlling an unknown linear dynamical system under adversarially-changing convex costs and full feedback of both the state and cost function. We present the first computationally-efficient algorithm that attains an optimal $\sqrt{T}$-regret rate compared to the best stabilizing linear controller in hindsight, while avoiding stringent assumptions on the costs such as strong convexity. Our approach is based on a careful design of non-convex lower confidence bounds for the online costs, and uses a novel technique for computationally-efficient regret minimization of these bounds that leverages their particular non-convex structure.
Cite
Text
Cassel et al. "Rate-Optimal Online Convex Optimization in Adaptive Linear Control." Neural Information Processing Systems, 2022.Markdown
[Cassel et al. "Rate-Optimal Online Convex Optimization in Adaptive Linear Control." Neural Information Processing Systems, 2022.](https://mlanthology.org/neurips/2022/cassel2022neurips-rateoptimal/)BibTeX
@inproceedings{cassel2022neurips-rateoptimal,
title = {{Rate-Optimal Online Convex Optimization in Adaptive Linear Control}},
author = {Cassel, Asaf Benjamin and Peled-Cohen, Alon and Koren, Tomer},
booktitle = {Neural Information Processing Systems},
year = {2022},
url = {https://mlanthology.org/neurips/2022/cassel2022neurips-rateoptimal/}
}