AdaSwitch: An Adaptive Switching Meta-Algorithm for Learning-Augmented Bounded-Influence Problems
This work addresses the challenge of integrating machine learning predictions into online decision-making for problems like lead-time quotation and resource allocation, offering a flexible solution with broad applicability.
The paper tackles the problem of multi-period online decision-making with unreliable sequence-based predictions by introducing a bounded-influence framework and the AdaSwitch meta-algorithm, which achieves performance close to an offline benchmark when predictions are accurate while maintaining competitive-ratio guarantees under inaccurate predictions.
We study a class of multi-period online decision-making problems with sequence-based predictions, which may be generated by machine learning models but whose accuracy is not guaranteed. In each period, the decision-maker observes the realized request and must take an irrevocable action that yields a reward or incurs a cost, without knowledge of future arrivals. We introduce a bounded-influence framework, in which past decisions and requests exert only limited impact on the future optimal reward. Within this framework, we propose the AdaSwitch meta-algorithm, which exploits predictions to attain performance close to the offline benchmark when predictions are accurate, while preserving classical competitive-ratio guarantees under highly inaccurate predictions. Our framework and meta-algorithm apply to diverse settings, including lead-time quotation in processing systems, the $k$-server problem, and online allocation of reusable resources. These applications illustrate the flexibility and broad applicability of our approach to learning-augmented online decision-making.