Steady-state Based Approach to Online Non-stochastic Control
For researchers in online control, this provides stronger performance guarantees by broadening the comparison class to affine controllers, though the improvement is incremental over existing steady-state benchmarks.
This paper extends online non-stochastic control to achieve O(√T) regret against a richer benchmark of steady-states attainable by affine controllers, combining Follow-The-Perturbed-Leader with batching for stability. Numerical experiments show lower total cost with similar computation to existing methods.
We study the problem of online non-stochastic control (ONC), which is the control of a linear system under adversarial disturbances and adversarial cost functions, with the aim of minimizing the total cost incurred. A recent line of literature in ONC develops algorithms that enjoy sublinear regret with respect to a benchmark based on the set of steady-states that are attainable by a constant input. In this work, we extend this research direction by giving an algorithm that enjoys $\mathcal{O}(\sqrt{T})$ regret with respect to a richer benchmark set, namely the set of steady-states attainable under an \emph{affine controller}. Since this benchmark substantially broadens the comparison class, it provides significantly stronger performance guarantees. Our proposed algorithm combines a Follow-The-Perturbed-Leader-style online non-convex optimization approach with a batching method that maintains stability despite changing policies. Although our proposed algorithm requires solving non-convex subproblems, we show that an approximate solution to this subproblem is sufficient to ensure $\mathcal{O}(\sqrt{T})$ regret. Furthermore, numerical experiments show that our algorithm enjoys lower total cost and similar computation to existing methods in certain settings.