Improved Learning-Augmented Algorithms and (Tight) Lower Bounds for Multi-Option Ski Rental Problem

We present improved learning-augmented algorithms for the multi-option ski rental problem. Learning-augmented algorithms take machine learning (ML) predictions as an added part of the input and incorporate these predictions in solving the given problem. Due to their unique strength that combines the power of ML predictions with provable performance guarantees, they have been extensively studied in the context of online optimization problems. Whilst the multi-option ski rental problem provides a natural generalization of the classical rent-or-buy variant, only deterministic algorithms for this problem were previously known, with or without learning augmentation. In this paper, we first present that a very simple modification to a previously known algorithm suffices to give an improved deterministic learning-augmented algorithm. In fact, we prove that this algorithm has the best possible performance of a deterministic algorithm by giving a matching lower bound. Then we present the first randomized learning-augmented algorithm, which surpasses the lower bound of deterministic algorithms; this learning-augmented algorithm is based on a new best-possible randomized competitive algorithm. These results are complemented by lower bounds for randomized competitive/learning-augmented algorithms.