Online Algorithms with Costly Predictions

Marina Drygala, Sai Ganesh Nagarajan, Ola Svensson
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:8078-8101, 2023.

Abstract

In recent years there has been a significant research effort on incorporating predictions into online algorithms. However, work in this area often makes the underlying assumption that predictions come for free (e.g., without any computational or monetary costs). In this paper, we consider a cost associated with making predictions. We show that interesting algorithmic subtleties arise for even the most basic online problems, such as ski rental and its generalization, the Bahncard problem. In particular, we show that with costly predictions, care needs to be taken in (i) asking for the prediction at the right time, (ii) deciding if it is worth asking for the prediction, and (iii) how many predictions we ask for, in settings where it is natural to consider making multiple predictions. Specifically, (i) in the basic ski-rental setting, we compute the optimal delay before asking the predictor, (ii) in the same setting, given apriori information about the true number of ski-days through its mean and variance, we provide a simple algorithm that is near-optimal, under some natural parameter settings, in deciding if it is worth asking for the predictor and (iii) in the setting of the Bahncard problem, we provide a $(1+\varepsilon)$-approximation algorithm and quantify lower bounds on the number of queries required to do so. In addition, we show that solving the problem optimally would require almost complete information of the instance.

Cite this Paper


BibTeX
@InProceedings{pmlr-v206-drygala23a, title = {Online Algorithms with Costly Predictions}, author = {Drygala, Marina and Nagarajan, Sai Ganesh and Svensson, Ola}, booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics}, pages = {8078--8101}, year = {2023}, editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem}, volume = {206}, series = {Proceedings of Machine Learning Research}, month = {25--27 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v206/drygala23a/drygala23a.pdf}, url = {https://proceedings.mlr.press/v206/drygala23a.html}, abstract = {In recent years there has been a significant research effort on incorporating predictions into online algorithms. However, work in this area often makes the underlying assumption that predictions come for free (e.g., without any computational or monetary costs). In this paper, we consider a cost associated with making predictions. We show that interesting algorithmic subtleties arise for even the most basic online problems, such as ski rental and its generalization, the Bahncard problem. In particular, we show that with costly predictions, care needs to be taken in (i) asking for the prediction at the right time, (ii) deciding if it is worth asking for the prediction, and (iii) how many predictions we ask for, in settings where it is natural to consider making multiple predictions. Specifically, (i) in the basic ski-rental setting, we compute the optimal delay before asking the predictor, (ii) in the same setting, given apriori information about the true number of ski-days through its mean and variance, we provide a simple algorithm that is near-optimal, under some natural parameter settings, in deciding if it is worth asking for the predictor and (iii) in the setting of the Bahncard problem, we provide a $(1+\varepsilon)$-approximation algorithm and quantify lower bounds on the number of queries required to do so. In addition, we show that solving the problem optimally would require almost complete information of the instance.} }
Endnote
%0 Conference Paper %T Online Algorithms with Costly Predictions %A Marina Drygala %A Sai Ganesh Nagarajan %A Ola Svensson %B Proceedings of The 26th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2023 %E Francisco Ruiz %E Jennifer Dy %E Jan-Willem van de Meent %F pmlr-v206-drygala23a %I PMLR %P 8078--8101 %U https://proceedings.mlr.press/v206/drygala23a.html %V 206 %X In recent years there has been a significant research effort on incorporating predictions into online algorithms. However, work in this area often makes the underlying assumption that predictions come for free (e.g., without any computational or monetary costs). In this paper, we consider a cost associated with making predictions. We show that interesting algorithmic subtleties arise for even the most basic online problems, such as ski rental and its generalization, the Bahncard problem. In particular, we show that with costly predictions, care needs to be taken in (i) asking for the prediction at the right time, (ii) deciding if it is worth asking for the prediction, and (iii) how many predictions we ask for, in settings where it is natural to consider making multiple predictions. Specifically, (i) in the basic ski-rental setting, we compute the optimal delay before asking the predictor, (ii) in the same setting, given apriori information about the true number of ski-days through its mean and variance, we provide a simple algorithm that is near-optimal, under some natural parameter settings, in deciding if it is worth asking for the predictor and (iii) in the setting of the Bahncard problem, we provide a $(1+\varepsilon)$-approximation algorithm and quantify lower bounds on the number of queries required to do so. In addition, we show that solving the problem optimally would require almost complete information of the instance.
APA
Drygala, M., Nagarajan, S.G. & Svensson, O.. (2023). Online Algorithms with Costly Predictions. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 206:8078-8101 Available from https://proceedings.mlr.press/v206/drygala23a.html.

Related Material