Geometric Exploration for Online Control
This work addresses the challenge of online control with unknown dynamics, offering improved regret bounds for researchers and practitioners in control theory and machine learning, though it builds incrementally on prior methods.
The paper tackles the problem of controlling an unknown linear dynamical system under convex costs, achieving optimal regret bounds with polynomial-time algorithms. For known cost functions, they obtain $n^3\\sqrt{T}$-regret, improving from $T^{2/3}$, and for bandit feedback, they achieve $poly(n)\\sqrt{T}$-regret.
We study the control of an \emph{unknown} linear dynamical system under general convex costs. The objective is minimizing regret vs. the class of disturbance-feedback-controllers, which encompasses all stabilizing linear-dynamical-controllers. In this work, we first consider the case of known cost functions, for which we design the first polynomial-time algorithm with $n^3\sqrt{T}$-regret, where $n$ is the dimension of the state plus the dimension of control input. The $\sqrt{T}$-horizon dependence is optimal, and improves upon the previous best known bound of $T^{2/3}$. The main component of our algorithm is a novel geometric exploration strategy: we adaptively construct a sequence of barycentric spanners in the policy space. Second, we consider the case of bandit feedback, for which we give the first polynomial-time algorithm with $poly(n)\sqrt{T}$-regret, building on Stochastic Bandit Convex Optimization.