In this work we study online rent-or-buy problems as a sequential decision making problem. We show how one can integrate predictions, typically coming from a machine learning (ML) setup, into this framework. Specifically, we consider the ski-rental problem and the dynamic TCP acknowledgment problem. We present new online algorithms and obtain explicit performance bounds in-terms of the accuracy of the prediction. Our algorithms are close to optimal with accurate predictions while hedging against less accurate predictions.

In this work we study online rent-buy problems as a sequential decision making problem.

In this work we study online rent-buy problems as a sequential decision making problem.

Additional Feedback: There were many thinks liked about the paper, including the idea of having an ML-advisor algorithm be e-close and alpha-accurate. I also liked the interpretation of a Hedge algorithm with an advisor give on page 5. In some ways the Hedge formalization, though, seems to minimize the use of predictors to just giving a prior. As someone interested in this area I find that a not especially hopeful or compelling message, but perhaps for some problems that's the right methodology. The experiments don't seem that useful.

It is shown how one can integrate predictions, typically coming from a machine learning algorithm, into this framework using a multiplicative weight algorithm. The paper has been positively evaluated by all the reviewers, with a uniform score of 6. The reviewers liked the overall idea of using ML predictions to improve the performance of online algorithms while still keeping the worst case guarantees, as well as incorporation of the multiplicative weights algorithm. On the other hand, the novelty of the paper seems a bit weak from a methodological perspective: the authors apply a well-known Hedge algorithm with ML predictions just incorporated within the prior. Also, contribution comparing to [13] seems somewhat incremental.

In this work we study online rent-or-buy problems as a sequential decision making problem. We show how one can integrate predictions, typically coming from a machine learning (ML) setup, into this framework. Specifically, we consider the ski-rental problem and the dynamic TCP acknowledgment problem. We present new online algorithms and obtain explicit performance bounds in-terms of the accuracy of the prediction. Our algorithms are close to optimal with accurate predictions while hedging against less accurate predictions.