2020/10/25 by Plevrakis, Orestis, Hazan, Elad
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2010.13178
We study the control of an 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 n3√(T)-regret, where n is the dimension of the state plus the dimension of control input. The √(T)-horizon dependence is optimal, and improves upon the previous best known bound of T2/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)√(T)-regret, building on Stochastic Bandit Convex Optimization.