Online Control of Linear Systems with Unbounded and Degenerate Noise
Kaito Ito Taira Tsuchiya
This paper investigates the problem of controlling a linear system under
possibly unbounded and degenerate noise with unknown cost functions, known as
an online control problem. In contrast to the existing work, which assumes the
boundedness of noise, we reveal that for convex costs, an $
\widetilde{O}(\sqrt{T}) $ regret bound can be achieved even for unbounded
noise, where $ T $ denotes the time horizon. Moreover, when the costs are
strongly convex, we establish an $ O({\rm poly} (\log T)) $ regret bound
without the assumption that noise covariance is non-degenerate, which has been
required in the literature. The key ingredient in removing the rank assumption
on noise is a system transformation associated with the noise covariance. This
simultaneously enables the parameter reduction of an online control algorithm.