Learning-Augmented Algorithms for the Bahncard Problem

Weakness 1 & Question 1

Our specific contributions are to (1) develop an effective learning-augmented algorithm PFSUM for the Bahncard problem using predictions on an immediate future only, which is more practical since the predictor is much easier to train; (2) analyze the competitive ratio of PFSUM as a function of prediction error by a divide-and-conquer approach and a holistic analysis of card purchasing patterns and their concatenations; (3) experimentally evaluate PFSUM and compare it with state-of-the-art algorithms in the literature. Moreover, we would like to point out that we focus on a continuous time setting of the Bahncard problem where requests can arise and cards can be purchased at any time instant along the time dimension. This is motivated by applications such as cloud instance reservation (in clouds, reserved VM instances can be purchased at any time instant). Our setting is more general than the slotted time setting (where requests are made only at the beginning of discrete time slots and so do card purchases) studied by prior work including reference [12] and Online algorithms with costly predictions (2023) you mentioned. The unbounded robustness $1/\beta$ of PFSUM when $\beta$ goes to 0 arises from the continuous time setting. The worst-case example is that there are an infinite number of small-cost travel requests made continuously over time and predictions always forecast low total cost in the future interval (so that the total ticket price is infinite while PFSUM does not purchase cards due to bad predictions). This example does not apply to the slotted time setting because the number of requests in an interval is limited (if the total ticket price goes to infinity, the price of individual requests also goes to infinity, and for any request with price exceeding $\gamma$ at time $t$, PFSUM purchases a card at $t$ by definition in lines 175-176). In the continuous time setting, $T$ does not affect the competitive ratio as changing $T$ just implies scaling time up or down. This is akin to the optimal conventional Bahncard algorithm SUM having a competitive ratio $2-\beta$ independent of $T$.

Weakness 2

Thank you for pointing us to these papers. We will include them in the related work. Learning-Augmented Online Algorithm for Two-Level Ski-Rental Problem (2024) studies an extended version of ski-rental problem, which extends ski-rental along the item dimension (from one item to multiple items and introduces a new option of combo purchase), whereas the Bahncard problem extends ski-rental along the time dimension (making decisions repeatedly). They have different problem structures. Online algorithms with costly predictions (2023) focuses on how many predictions are required to gather enough information to output a near-optimal buying schedule, assuming all predictions are correct. The learning-augmented algorithm proposed takes a suggested sequence of buying times as input and assumes a slotted time setting, thereby sharing similar drawbacks to reference [12]. The paper studies only the consistency and robustness of the proposed algorithm, and does not derive the competitive ratio as a function of prediction error. Without the latter, one could not judge how tolerant the algorithm is to errors. If there is no ratio function of the error, the ratio of the algorithm will jump directly from consistent to robust if the prediction is slightly wrong (which usually happens in practice). Moreover, there was no experimental evaluation.

Weakness 3 & Question 3

Thank you for your comments and questions. In the experiments, cost ratio refers to the ratio between the cost produced by an online algorithm and the offline optimal cost for a given input (i.e., travel requests). In the theoretical analysis, competitive ratio refers to the worst-case cost ratio across all possible inputs. So, they are consistent. As with most papers in this field, the experiments tend to show better performance than the theoretically analyzed bounds due to the use of particular datasets.

Robustness is an upper bound of the competitive ratio across all possible prediction errors, which means the worst-case scenario typically arising from extreme inputs. Our experiments generate travel requests from distributions that resemble real-world scenarios, which are unlikely to encounter such extreme situations. Hence, it is not surprising that the empirical results do not demonstrate the theoretical bound of robustness. The main purpose of the experiments is to compare the empirical cost ratios of different algorithms with realistic travel request patterns, rather than demonstrating theoretical worst-case bounds.

For experimental benchmarks, we have tried to find all papers related to the Bahncard problem. The only article that conducts experiments for the Bahncard problem is reference [28]. We therefore refer to their experimental setup of traveler profiles and include various types of ticket price distributions in our paper. Reference [12] did not conduct experiments for the Bahncard problem. We implement its algorithm (PDLA), and include it in our comparison. Thus, our experiments provide comprehensive empirical evaluation and comparison.

Question 2

We appreciate your insight. Section 4.1 of our paper studies a prediction interval shorter than $T$ and shows that it is not good. If the length of the prediction interval is $T + \epsilon$ (for any $\epsilon > 0$), it means at time $t$, we know the predicted total regular cost in $[t, t + T + \epsilon)$. But it may happen that all the cost in $[t, t + T + \epsilon)$ is incurred before $t+ T$ (i.e., in $[t, t + T)$) or all the cost is incurred beyond $t+T$ (i.e., in $[t + T, t+T+\epsilon)$). Thus, it is not helpful to make the correct purchase decision at time $t$, because a Bahncard purchased at $t$ can reduce the cost in $[t, t + T)$ only.

Thank you for the detailed responses from the authors. I thought through your work and your responses. Although I like your work and enjoy reading the text, a couple of unsolved issues hesitate me to improve my score.

1. Since your algorithm predicts the near future, the advice complexity could be much larger than those algorithms predicting a long-term future. It will be interesting to explore the cumulative average competitive ratio versus the competitive ratio of a long-term prediction to prove whether the proposed online algorithm is more practical.

2. Relating the prediction errors to the competitive ratio is interesting but is not new, which can date back to the paper “Improving Online Algorithms via ML Predictions” (2018). The better bounded competitive ratio seems to be more attractive and convincing. Furthermore, if we let β = 0, we can observe that the consistency of PFSUM converges to at least 2. As is known, in the ski rental problem, the worst-case competitive ratio is 2. It means when β = 0, the consistency of PFSUM is worse than the robustness of other online algorithms.

3. If T is related to the prediction errors, will it affect the competitive ratio?

4. As mentioned, you only found one work that conducted experiments on the Bahncard problem, you can still employ other online algorithms on the Bahncard problem, as you do with your reference [12]. A single benchmark cannot show your proposed contributions, particularly in ML/AI conferences. Those works mostly conducted extensive experiments on numerous datasets compared across multiple benchmarks. With the current shape of the paper and your arguments, I just feel this problem as the Achilles’s heel of the work. If the theoretical and experimental results of the Bahncard problem are still limited, you can put your algorithm into a ski rental problem with β = 0 and T converging to infinity. Then, you can have more benchmarks even they may not be the perfect one. This issue makes me wonder whether this venue is the right place for this work. In my opinion, the theoretical computing conferences, e.g., STOC, FOCS, SODA, may be a better fit for this work as they pay more attention on theoretical contributions and will have more audiences to read and cite the work.

Dear Reviewer AGsA, we deeply appreciate your acknowledgment and support of our work! Below, we respond to the weakness and questions 1-5, one by one.

Weakness

We greatly appreciate your constructive comments. In particular, we greatly appreciate that you understood our paper in depth. We will rewrite the proof of Proposition 4.6 and hope the new version makes this proposition clearer for readers. The new proof is presented below.

Proof. Let $x = c(\sigma; [\tau_i, \tau_i + T))$. Based on the definition of Pattern II, $\textsf{OPT}(\sigma; [\tau_i, \tau_i + T)) = C + \beta x$ (OPT buys a card at $\tau_i$) and $\textsf{PFSUM}(\sigma; [\tau_i, \tau_i + T)) = x$ (by definition, PFSUM does not buy cards during any off phase). Hence, the cost ratio is $\frac{x}{C + \beta x}$, which increases with $x$ since $\beta < 1$. By Lemma 4.3, $x < 2\gamma + \eta$. Hence, the cost ratio is bounded by $\frac{2\gamma + \eta}{C + \beta (2\gamma + \eta)} = \frac{2\gamma + \eta}{(1-\beta)\gamma + \beta (2\gamma + \eta)} = \frac{2\gamma + \eta}{(1+\beta)\gamma + \beta \eta}$.

Question 1

Thank you for your extensive review. We will follow your suggestion to add more description to Section 4.1 to help readers to understand.

Question 2

We agree with you. Making more fine-grained predictions for future requests and defining the error function accordingly might help to improve the bounds, which is indeed an interesting direction for future research. Thanks for your valuable suggestion.

Question 3

Your insight is reasonable. Actually, Lemma 4.3 describes the case you mentioned, in which the time interval $[t, t+T)$ is fully contained in an off phase, and does not intersect on phases on either sides. Therefore, we omit this case in the figure associated with Lemma 4.4.

Question 4

Thanks for pointing out this. You are right, we made a typo here. $x$ should be an integer.

Question 5

Thanks for alerting us to this ambiguous description. Firstly, yes, there will be no regular requests during an on phase. An on phase refers to a period during which PFSUM has a valid Bahncard. On the other hand, the total regular cost in an on phase refers to the sum of the original ticket prices before discounts in this phase (please refer to line 108). Therefore, the regular cost of a given interval is fixed and independent of the algorithm.

Dear Reviewer m14s, we are immensely grateful for your positive comments! Below is our response to the weakness.

Weakness

We greatly appreciate your keen observation between the experimental results and the theoretical robustness bound $1 / \beta$. Allow us to start by revisiting the following three definitions, although you might already fully understand them.

• Cost ratio: the ratio between the cost produced by an online algorithm and the cost of the offline optimum for a given input (i.e., travel requests).
• Competitive ratio: the worst-case cost ratio across all possible inputs, comparing an online algorithm with the offline optimum.
• Robustness: an upper bound of the competitive ratio across all possible prediction errors. Therefore, the theoretical bound $1 / \beta$ describes the algorithm’s performance in the worst-case scenario, typically arising from very extreme inputs, under the prediction error being $\infty$. In contrast, our experiments generate travel requests from distributions that closely resemble real-world scenarios, which are unlikely to encounter such extreme situations. Hence, it is likely that the empirical results do not demonstrate the theoretical bound of robustness.

Furthermore, we want to explain that, by our experimental setup, the prediction error $\eta$ is not $\infty$ even when the perturbation probability is $1.0$. Note that the random noise added is sampled from the same distribution used for generating ticket prices. Taking Fig. 29 as an example, when $T = 10$ and the perturbation probability is $1.0$, the expected prediction error $\eta$ is $500$, which is the sum of 10 samples of the noise distribution with a mean of 50 (equal to the ticket price distributions). On the other hand, $\gamma = C / (1 - \beta) = 500$. Let's assume the actual prediction error sampled from distribution is exactly its expectation, i.e., $\eta = 500$. Then, by equation (10), the competitive ratio for the case of perturbation probability = $1.0$ in Fig. 29 is $(4-\beta) / (1+2\beta) = 3.8/1.4 \approx 2.714$, much smaller than $1/\beta = 5$.

In fact, the instance that leads to the theoretical worst-case scenario $1/\beta$ is an arbitrarily dense sequence of requests with small prices (the price of each request $\ll \gamma$). However, the experiments consider a discrete timeline (a widely used approach in numerical experiments), which makes it difficult to construct extreme instances. This is one of the reasons why we rarely observe the worst competitive ratio in the experiments.

Thank you for the clarification. In light of comments from other reviewers and your responses, I am inclined to keep my positive score.