Switching Constrained OCO with Predictions and Feedback Delays

We examine Online Convex Optimization (OCO) problems with feedback delay and a strict limit on decision switching, which exists in applications such as smart grid and learning. Existing algorithms developed for traditional OCO struggle in this setting, often violating switching constraints or incurring high regrets, as evidenced by simulations. In this paper, we establish a new algorithm, Follow-the-Maximally- Coupled-Latest-Leader (FMCLL), achieving a near-optimal regret of O(T/S) for such problems with delayed feedbacks and a bound of O(T/S − τ) for problems with predictions of τ rounds, even though the player is only allowed to move at most S times in expectation across T rounds. FMCLL meets performance bounds in scenarios with delays and predictions by using maximal coupling sampling to inform algorithm design for switching-constrained problems. It is also extended to a bandit feedback setting. Simulations demonstrate FMCLL's superiority over traditional Gradient Descent or Follow-the-Leader algorithms, excelling under adversarial or stochastic losses and reducing constraint violations.