Learning-augmented Rent-or-Buy with a Sample

In this paper, we study the rent-or-buy problem (also called the Bahncard problem) in the learning-augmented setting. In this problem, a traveler must complete a sequence of trips that are revealed online over time, each of which has an associated cost with it. The traveler has the option of buying a discount card at a fixed cost that gives a discount on trip costs for a fixed time after buying the card. The goal is to minimize the overall cost of all the trips, including the money spent on buying discount cards. For this problem, it is well-known that the best deterministic algorithm has a competitive ratio of 2. In this paper, we ask whether we can do better if the traveler has a sample of trips available offline, e.g., obtained from an ML model based on historical data. We show that even a sparse sample of the input can significantly improve the competitive ratio of the algorithm from 2 to 3/2, and further to close to 1 under some additional conditions. We also verify our theoretical bounds via numerical simulations, which reveal that our proposed algorithm obtains nearly optimal solutions for a variety of natural input classes.

In the rent-or-buy problem (also known as the Bahncard problem), a traveler must decide how to pay for a sequence of trips that arrive over time without knowing the future. For each trip, the traveler can either pay the full price directly or purchase a discount card for a fixed cost, which reduces the prices of trips taken during a fixed time period afterward. The goal is to minimize the total amount spent on trips and discount cards. Our paper studies whether access to partial information about the future can help the traveler make better decisions. In particular, we consider the setting where the traveler can see a random subset of future trips in advance. We prove that this additional information can significantly reduce the traveler’s total cost when individual trips are much cheaper than the discount card. Under additional assumptions on trip costs, we further show that the traveler’s cost can become nearly optimal. Finally, we validate our theoretical results through simulations, demonstrating that our algorithms perform well across a range of practical scenarios.