Summary and Contributions: The paper proposes an online algorithm that utilizes predictions made by a machine learning model for a generalization of the classical ski rental problem called multi-shop ski rental. In the multi-shop ski rental problem, there are ‘n’ ski shops each of which provides the option of renting skis for $r_i or buying skis for $b_i. The skier needs to decide which shop to choose and whether to rent or buy. Importantly, the skier must choose the shop upfront and then continue renting (or buying) from that same shop. Clearly, this generalizes the classical ski rental problem which is a special case with a single shop. In the learning augmented framework, the algorithm receives a prediction ‘y’ regarding the number of days the skier wishes to ski. The paper generalizes the results of [17] to the multi-shop setup and obtains consistent and robust online algorithms (deterministic and randomized). The paper also considers a setup with multiple predictions.
Strengths: The paper studies a natural generalization of the ski rental problem and generalizes the learning-augmented online algorithm for ski rental for the more general multi-shop ski rental problem. The paper is also well-written and includes significant experimental evaluation as well of the proposed algorithms.
Weaknesses: While it has natural applications, the multi-shop ski rental problem seems to be a minor generalization of the standard ski rental problem and essentially the same algorithms (with minor adaptations) yield optimal results. I find the paper lacking in technical novelty since the algorithms are minor variants of those for the standard ski rental problem. In the setup with multiple predictions, the error is defined to be the error of the \emph{worst} prediction unlike prior work [4] that obtains competitive ratios in terms of the error of the \emph{best} prediction (which can of course be much lower).
Correctness: Yes
Clarity: Yes
Relation to Prior Work: Yes
Reproducibility: Yes
Additional Feedback: Other comments: The MSSR problem mandates that the skier first chooses a shop and then must rent / buy at that same shop for the entire instance. Without this restriction the problem boils down to the standard ski rental problem with rent cost r_i and buy cost b_n since the algorithm can always rent from shop 1 and buy from shop n. It will be good to emphasize the importance of this restriction more in the model. In Lemma 1, the best deterministic online algorithm can choose any of the n shops depending on the argmin of specified term. However, both the randomized and deterministic algorithms that utilize the predictions only buy from either the first shop or the last shop. Isn’t it possible to obtain better robustness / consistency tradeoff by considering these other shops as alternatives? Line 193 is incorrect. As currently described even with lambda = 1, Algorithm 2 does not equal BDOA and in particular does not completely ignore the predictions. It still looks at the prediction to decide which shop to buy from. This is related to the comment above - it would be nice if Algorithm 2 reduced to BDOA for lambda = 1. Also Fig 1 clearly shows that the competitive ratio of the algorithm with lambda =1 does depend on the error.
Summary and Contributions: The authors propose online algorithms using ML predictions for multi-shop ski-rental problem which is a generalization of the classic ski-rental problem where the decision problem is restricted to buying or renting the ski equipment from a single store. The consider all the special cases where the predictions come from a single predictor as well as multiple ML models. They present empirical evaluation of their algorithms for different values of hyperparameters.
Strengths: The paper considers all the important cases of the problem and presents both deterministic and randomized algorithms for the problem. The theoretical analysis is complete and clear. The empirical evaluation is also complete.
Weaknesses: One of the drawbacks of the model is the assumption of the skier having to transact with one store after selecting a store. Even though the authors give an example of cloud service providers, I believe each shop offering multiple levels of service might also induce the customer to choose between each level on different days. It'll help to distinguish from such a setting. After reading the rebuttal, I think addressing the extensions MSSR-S/E might help in strengthening the contributions of the paper. The authors did not offer a single proof in the main paper and moved all technical analysis to the supplementary material. Presenting proof sketches will help the reading.
Correctness: Though I did not read all the proofs carefully, they look correct.
Clarity: The paper is a little dense in results and sparse on details in the technical analysis section.
Relation to Prior Work: The work clearly compares with the previous work.
Reproducibility: Yes
Additional Feedback:
Summary and Contributions: This paper considers the multi shop ski rental problem in the online algorithms with advice model. This is a popular emerging model in the intersection of algorithms and machine learning. The idea is that an online algorithm is given access to a prediction. Then the algorithm can use the prediction to make decisions. The goal is to bound the competitive ratio in terms of the error of the prediction. Recently, there has been a paper in this model addressing the ski rental problem. Tis paper considers the multi-shop ski rental problem. The paper shoes consistency and robustness results for the model. These follow along the same lines as prior work. Overall, I find that the algorithm and analysis are applications of the ideas that are used in prior work. They were also fairly simple even in the first paper addressing this. For this reason, I find the results good to know, but not particularly exciting. The reason to consider accepting the paper is the contribution to the growing interest in this line of work. It does indeed contribute to this theory. For these reasons, I believe this is a borderline paper.
Strengths: contributions to theory of online algorithms with predictions. Extends prior work and makes it more robust
Weaknesses: Algorithmic and analysis contributions are extensions not particularly novel
Correctness: I believe the claims are correct
Clarity: It is reasonably well-written
Relation to Prior Work: the paper does a good job overviewing the area
Reproducibility: Yes
Additional Feedback: