Timezone: »

Rate-Optimal Online Convex Optimization in Adaptive Linear Control
Asaf Benjamin Cassel · Alon Peled-Cohen · Tomer Koren

Wed Nov 30 02:00 PM -- 04:00 PM (PST) @ Hall J #722
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.

Author Information

Asaf Benjamin Cassel (Tel Aviv University)
Alon Peled-Cohen (Tel Aviv University)
Tomer Koren (Tel Aviv University & Google)

More from the Same Authors