acceptodds
Under review as a conference paper at ICLR 2027

Learning-Augmented Rent-or-Buy with Multiple Predictions

Abstract

We study online algorithms with multiple predictions for two classical rent-or-buy problems: the Bahncard problem and dynamic TCP acknowledgment. In the Bahncard problem, a generalization of ski rental, trips of varying costs arrive online, and the algorithm may purchase a fixed-price card that discounts travel for a fixed duration; the objective is to minimize the total cost of cards and trips. In dynamic TCP acknowledgment, requests arrive online, and the algorithm may send a fixed-cost acknowledgment for all outstanding requests at any time; the objective is to minimize the total acknowledgment cost and request latency. Both problems are well-studied in both the classical online setting and the learning-augmented setting with a single prediction. But, unlike ski rental, they have not been studied when the algorithm has to choose between more than one prediction. In this paper, we address this gap by establishing tight consistency bounds for these problems for both deterministic and randomized algorithms with two predictions. For Bahncard with any discount factor , we show that the optimal deterministic consistency is which interpolates between the golden ratio at and at . In contrast, we show that the optimal deterministic consistency for dynamic TCP acknowledgment is , revealing that the two problems behave differently. We obtain similar tight bounds for randomized algorithms for both problems, and further establish consistency–robustness tradeoffs when predictions may be inaccurate. Finally, we complement our theoretical results with numerical simulations on synthetically generated instances.

Primary area:
learning theory
Keywords:
Learning-Augmented Algorithms, Rent-Or-Buy, Online Algorithms

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_jWX4OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper suggests algorithms for handling the Bahncard problem and dynamic TCP acknowledgment with two predictions. They propose a threshold rule to balance between the two predictions, and they analyze consistency and robustness.

Critical strengths

The notions of consistency and robustness for two predictions used in this paper seem reasonable.

Critical weaknesses

My main concern is that the current analysis is restricted to the case of two predictions. While the two-prediction setting is a reasonable and interesting starting point, I think the scope of the current results is somewhat limited. In my view, extending the analysis to a general number of predictions, including three or more, would substantially strengthen the paper and make its contribution more compelling.

I also think the title suggests a somewhat broader scope than what is currently established in the paper. The title includes “Multiple Predictions,” whereas the technical analysis focuses only on the two-prediction case. This is not merely a matter of title choice, but is also related to my broader concern about the scope of the contribution. I believe that an extension to three or more predictions would be a valuable direction and would help establish the broader significance of the proposed framework.

Questions for authors

If there is a practical scenario where we can obtain only two predictions and cannot obtain three or more predictions, an explanation would be helpful, as it would support the value of investigating the two-prediction setting. Also, if the authors think their two-prediction algorithm can be directly extended to three or more predictions, an explanation would be helpful.

Reviewer_dtxuOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies two relatively classic online rent-or-buy problems (Bahncard and TCP acknowledgement) with predictions. Both of these problems have already been studied with predictions, so the innovation here is to use two predictions. Each prediction is just a complete request sequence, given to use ahead of time offline. With two predictions, the first issue is "consistency": if we are guaranteed that one of the predictions is completely accurate, but what don't know which one, then how well can we do? The main results of this paper are optimal consistency bounds for both problems. The algorithms are more or less what one would expect: as long as the two predictions agree then there is no question what to do, and once they disagree the algorithm chooses what to do via a carefully chosen threshold.

The second issue is consistency vs. robustness: we want to do well if one of the two predictions is accurate, but want to make sure that we don't do too poorly if neither of them is accurate. For both problems they show how to modify their consistency-focused algorithms to get the same optimal consistency but also reasonable robustness.

Overall, while I like the fact that they got the true optimal consistency bounds, I don't think that this paper is quite at the level of ICLR.

Critical strengths
  • These are both natural problems, and it is natural to study them with multiple predictions.
  • Optimal consistency, while still getting nontrivial robustness, is a reasonably strong result.
Critical weaknesses

My main concern with this paper is that, while the quantitative results are strong (see above), I don't think that the results are actually that impressive or interesting in the context of other algorithms with predictions literature.

  • They only study two predictions. There is significant literature, which they cite, on studying algorithms with multiple predictions. But I'm not aware of any previous paper that only studies two, and this seems to me like a significant weakness. The previous work that I know of has usually tried to analyze the performance loss and gain as the number of predictions grows: if we are given kk predictions and want performance comparable to the best of the kk predictions, how much do we pay as kk grows? So 22 predictions does not seem particularly interesting to me.
  • Each individual prediction is quite strong: it is a complete request sequence. Note that this is stronger than assuming that we are given a solution as a prediction, since given an input sequence offline we can of course compute an optimal solution. The authors cite related work for both problems, some of which use a similar prediction (particularly Im et al. for TCP acknowledgement), but some of which allow for much weaker predictions. What's the justification for such a strong prediction? It is not even discussed in the paper.
  • Even if we're OK with this prediction, the style of result is quite weak. In particular, this paper does not provide any guarantee as a function of "prediction error". This kind of guarantee, known sometimes as a "smoothness" guarantee, has become the standard guarantee in the algorithms with predictions literature. The pure consistency guarantee, or the consistency vs. robustness tradeoff, is not very common among strong papers anymore. This is for a few simple reasons, but primarily because "consistency" is a somewhat ridiculous concept: there is basically no reasonable scenario in which it one might actually expect an absolutely perfect prediction. Instead, as in most ML settings, we would usually like to think of having predictions that are "good" in that they have low error, but are not perfect. So we have to define an error metric and analyze our performance as this increases. This completely subsumes the older consistency/robustness framing, since consistency is just when error is 00 and robustness is when the error goes to ∞\infty. The fact that this paper does not give anything for extremely good but not perfectly accurate predictions makes in extremely limited, and in my opinion pretty uninteresting.
Questions for authors
  • Do you actually have any smoothness guarantees?
  • What is the justification for such a strong prediction, particularly if you don't have smoothness guarantees and so really need the prediction to be completely accurate?
Reviewer_F26eOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies learning augmented algorithms for the Bahncard problem and the dynamic TCP acknowledgement problem with multiple predictions. More precisely, the paper focuses on the case where there are 2 predictions, where each prediction is a forecast of the entire future problem input. The predictions are given to the algorithm once at the very beginning.

The metrics used to evaluate the algorithm are robustness and consistency, where robustness is the usual competitive ratio, and consistency is the competitive ratio when one of the predictions is perfect.

The main result of the paper is to give deterministic and randomized algorithms for the Bahncard problem and the dynamic TCP acknowledgement problem that have the optimal value of consistency. The authors also analyze the robustness for these consistency-maximizing algorithms -- the robustness bound is shown to be tight in some cases.

Critical strengths

The Bahncard problem and the dynamic TCP acknowledgement problems are fundamental problems in online algorithms, so I think the problem of studying learning augmented algorithms with multiple predictions for these problems is natural and well motivated.

I also like that the consistency guarantees in the paper are shown to be optimal.

Critical weaknesses

For me, the main weakness of the paper is that it does not analyze the 'smoothness' of the algorithm, which is how the performance of the algorithm changes as a function of the prediction error. I think smoothness is important because in practice the prediction is probably never going to be exactly optimal. Without smoothness, the consistency guarantee only tells us what happens when the prediction is exactly optimal, which is not very meaningful. To me, the combination of robustness + consistency + smoothness is really where much of the appeal of learning augmented algorithms lies.

Another point is that the paper only considers the setting with 2 predictions. Given that the premise of the paper is to consider the case with multiple predictions, it would have been a stronger paper if it had results on the setting with k predictions as well.

Questions for authors

N/A

Comments on the paper

1 comment

Dear reviewers,

please acknowledge the rebuttal and, if possible, check the revised version and decide whether it affects your assessment of the paper and if you want to adapt your score.

AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.