Rate-Optimal Online Convex Optimization in Adaptive Linear Control
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 $\smash{\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.