Online Optimization with Memory and Competitive Control
This work addresses online optimization and control problems with memory effects, offering competitive algorithms for applications like resource management, but it is incremental as it builds on Smoothed Online Convex Optimization.
The paper tackles the problem of online optimization with memory, where the learner minimizes a sum of hitting and switching costs dependent on past decisions, and achieves a constant, dimension-free competitive ratio. It also connects this to online control with adversarial disturbances, resulting in a new constant-competitive policy for a broad class of control problems.
This paper presents competitive algorithms for a novel class of online optimization problems with memory. We consider a setting where the learner seeks to minimize the sum of a hitting cost and a switching cost that depends on the previous $p$ decisions. This setting generalizes Smoothed Online Convex Optimization. The proposed approach, Optimistic Regularized Online Balanced Descent, achieves a constant, dimension-free competitive ratio. Further, we show a connection between online optimization with memory and online control with adversarial disturbances. This connection, in turn, leads to a new constant-competitive policy for a rich class of online control problems.