Abstract
We study the problem of controlling linear timeinvariant systems with known noisy dynamics and adversarially chosen quadratic losses. We present the first efficient online learning ? algorithms in setting that guarantee O( T) regret under mild assumptions, where T is the time horizon. Our algorithms rely on a novel SDP relaxation for the steady-state distribution of the system. Crucially and in contrast to previously proposed relaxations the feasible solutions of our SDP all correspond t “strongly stable” policies that mix exponentially fast to a steady state.