Abstract: Traditional online algorithms are designed to make decisions online in the face of uncertainty to perform well in comparison with the optimal offline algorithm for the worst-case inputs. On the other hand, machine learning algorithms try to extrapolate the pattern from the past inputs to predict the future and take decisions online on basis of the predictions to perform well for the average-case inputs. There have been recent studies to augment traditional online algorithms with machine learning oracles to get better performance for all the possible inputs. The machine learning augmented online algorithms perform provably better than the traditional online algorithms when the error of the machine learning oracle is low for the worst-case inputs and all other average-case inputs. In this paper, we integrate the advantages of the traditional online algorithms and the machine learning algorithms in the context of a novel variant of the ski rental problem. Firstly, we propose the ski rental problem with a discount: in this problem, the rent of the ski, instead of being fixed over time, varies as a function of time. Secondly, we discuss the design and performance evaluation of the online algorithms with machine learning advice to solve the ski rental problem with a discount. Finally, we extend this study to the situation where multiple independent machine learning advice is available. This algorithm design framework motivates to redesign of several online algorithms by augmenting them with one or more machine learning oracles to improve the performance.

Machine Learning Advised Ski Rental Problem with a Discount