Rate-Optimal Online Convex Optimization in Adaptive Linear Control
This work addresses a fundamental challenge in adaptive control for unknown linear systems, offering a practical solution with optimal regret guarantees, though it is incremental in improving computational efficiency over prior methods.
The paper tackles the problem of controlling an unknown linear dynamical system with adversarially changing convex costs and full feedback, presenting the first computationally-efficient algorithm that achieves an optimal √T-regret rate compared to the best stabilizing linear controller in hindsight, without requiring strong convexity assumptions on the costs.
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.