In this paper, we study the two-level ski-rental problem,where a user needs
to fulfill a sequence of demands for multiple items by choosing one of the
three payment options: paying for the on-demand usage (i.e., rent), buying
individual items (i.e., single purchase), and buying all the items (i.e., combo
purchase). Without knowing future demands, the user aims to minimize the total
cost (i.e., the sum of the rental, single purchase, and combo purchase costs)
by balancing the trade-off between the expensive upfront costs (for purchase)
and the potential future expenses (for rent). We first design a robust online
algorithm (RDTSR) that offers a worst-case performance guarantee. While online
algorithms are robust against the worst-case scenarios, they are often overly
cautious and thus suffer a poor average performance in typical scenarios. On
the other hand, Machine Learning (ML) algorithms typically show promising
average performance in various applications but lack worst-case performance
guarantees. To harness the benefits of both methods, we develop a
learning-augmented algorithm (LADTSR) by integrating ML predictions into the
robust online algorithm, which outperforms the robust online algorithm under
accurate predictions while ensuring worst-case performance guarantees even when
predictions are inaccurate. Finally, we conduct numerical experiments on both
synthetic and real-world trace data to corroborate the effectiveness of our
approach.

我们研究了两层滑雪租借问题，其中用户需要通过选择三个支付选项之一来满足多个项目的一系列需求：按需使用支付（即租赁），购买单个项目（即单独购买）和购买所有项目（即组合购买）。我们设计了一种稳健的在线算法（RDTSR），它能提供最坏情况下的性能保证。为了兼顾在线算法的稳健性和机器学习的平均性能，我们开发了一种学习增强算法（LADTSR），通过将机器学习预测集成到稳健的在线算法中，即使预测不准确也能确保最坏情况下的性能保证。最后，我们对合成数据和真实迹线数据进行了数值实验以验证我们方法的有效性。