Improving Online Rent-or-Buy Algorithms with Sequential Decision Making and ML Predictions

Part of Advances in Neural Information Processing Systems 33 (NeurIPS 2020)

Authors

Shom Banerjee

Abstract

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.