Strategies for choosing update timing cut resource waste and performance loss
Learning When to Update: A Near-Optimal Timing Bandit Approach
Machine Learning
Summary
Systems like AI models or digital replicas need to update regularly to keep working well, but updating too often wastes effort and updating too rarely lets them perform badly. The authors studied a situation where the way performance gets worse over time is unknown. They created a new way to pick when to update by treating it like a game where each choice covers multiple time points and feedback comes in continuously. Their approach learns to update at near-best times, reducing wasted updates and poor performance.
What this means in practice
- •For system engineers: Schedule updates for complex digital twins under uncertainty to balance cost and accuracy more efficiently.
- •For machine learning engineers: Optimize retraining times for machine learning models that degrade unpredictably to save resources without hurting performance.
Authors
Qiulin Lin, Junyan Su, Liyuan Wang, Minghua Chen
Abstract
Systems operating in dynamic environments require timely updates to sustain performance. For resource-intensive systems such as machine learning models and digital twins, strategically timing updates is essential. Updating too frequently wastes resources, while updating too infrequently leads to costly performance degradation. The problem is particularly challenging when the system's degradation pattern is unknown a priori, as is common in new operating environments. We formalize this challenge as a novel \emph{timing bandit} problem, where each arm represents a candidate update interval with a fixed update cost and an unknown, stochastic degradation cost. Three structural properties distinguish this setting from standard multi-armed bandits: selecting an interval commits the learner to multiple time slots before the next update; arm costs are composed of per-step degradation costs and a fixed update cost; and selecting a longer interval naturally reveals degradation at every intermediate step, providing consecutive feedback relevant to shorter intervals. By exploiting these structures, we develop Balanced Consecutive Arm Elimination (BCAE). BCAE achieves $\tilde{O}(\sqrt{T})$ regret, improving upon the $\tildeΩ(K\sqrt{T})$ regret of standard bandit algorithms in this setting, where $K$ is the number of candidate update intervals. We further propose an Optimism-Enhanced variant (OE-BCAE) that integrates lower-confidence-bound principles to improve empirical adaptivity while preserving the same regret order. Moreover, the regret bound achieved by our algorithms matches the theoretical lower bound up to logarithmic factors. Simulation results demonstrate that our algorithms achieve low regret and remain stable as both the number of arms and the update cost vary.