Learning-Augmented Algorithms for the Bahncard Problem
Authors: Hailiang Zhao
Xueyan Tang
Peng Chen
Shuiguang Deng
Venue: NeurIPS 2024 poster (2024)
Keywords: algorithms with predictions
competitive analysis
consistency
robustness
Primary area: optimization
TL;DR: We develop an improved learning-augmented algorithm for the Bahncard problem and derive its competitive ratio under any prediction errors.

Abstract: In this paper, we study learning-augmented algorithms for the Bahncard problem. The Bahncard problem is a generalization of the ski-rental problem, where a traveler needs to irrevocably and repeatedly decide between a cheap short-term solution and an expensive long-term one with an unknown future. Even though the problem is canonical, only a primal-dual-based learning-augmented algorithm was explicitly designed for it. We develop a new learning-augmented algorithm, named PFSUM, that incorporates both history and short-term future to improve online decision making. We derive the competitive ratio of PFSUM as a function of the prediction error and conduct extensive experiments to show that PFSUM outperforms the primal-dual-based algorithm.

Learning-Augmentedd Algorithms for the Bahncard Problem
Hailiang Zhao'
Xueyan Tang² Peng Chen' Shuiguang Deng'
'Zhejiang University NNayyang Technological University
[hl {hliangzhao,
pgccan pgchen, dengsg) Szju. edu. cn asxytangentu. edu.
Abstract
algorithms for the Bahncard problem. The Bahncard problem is generalization of the ski-rental problem, where traveler needs to irrevocably and repeatedly decide between a cheap short-term solution and expensive long-term
this paper, we study
with unknown future. Even though the problem is canonical, only a primal-dual- based designed for it. We develop that incorporates both history and short-term future to improve online decision making. We derive the competitive ratio of PFSUM function of the prediction error and conduct extensive experiments to show that PFSUM outperforms the primal-dual-based algorithm.
algorithm was explicitly algorithm, named PFSUM,
1 Introduction
The Bahncard is a railway pass the German railway company, which provides a discount on all train tickets for fixed time period of pass validity. When travel request arises, traveler buy the train ticket with the regular price, or purchase a Bahncard first and get entitled to a discount on all train tickets within its valid time. The Bahneard problem whose objective is to minimize the overall cost of pass and ticket purchases, without knowledge of future travel requests (1. It reveals recurring renting-or-buyie orbbiing phenomenon, where online algorithm needs to irrevocably and repeatedly decide between cheap short-term solution and an expensive long-term one with an unknown future. The performance of an online algorithm typically measured by the competitive ratio, which is the worst-case ratio across all inputs between the costs of the online algorithm and an optimal offline one 2
online cost minimization problem,
Recently, there has been growing interest in using machine-leammn predictions to improve online algorithms. One seminal work was done by Lykouris and Vassilvtiskii 3 for the caching problem, in which the online algorithms are allowed to leverage predictions of future inputs to make decisions, but they
given any guarantee the prediction accuracy. Since then, the framework of online algorithms with predictions has been extensively studied for a wide range problems including ski-rental (48), scheduling 100, graph optimization (T]] covering [12 data structures [[4] 16), etc. In this framework, the measurements for the online algorithms include consistency and robustness, where the former refers the competitive ratio under perfect predictions while the latter refers to the upper bound of the competitive ratio when the predictions can be arbitrarily bad.
The Bahncard problem with maachine-learnee predictions recently studied by Bamas et al. [12 They designed a primal-dual based algorithm assuming given a prediction of the optimal solution, i..,, optimal collection of times purchase Bahncards such that the total cost is minimized. While Bamas et al. 12 presented an elegant framework for seamlessly integrating the primal-dual method with predicted solution, their approach faces three critical issues. First, their considered scenario is limited, involving slotted time and a fixed ticket price of 1 for any travel request. The discretization is necessary for them formulate an integer program and enable the application of the primal-dual
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

method proposed by Buchbinder et al. [17]. Second, their results of consistency and robustness are weak in that they only hold under the condition that the cost of Bahncard goes towards infinity, in which case the optimal solution is to never buy any Bahncard. Last, their algorithm demands complete solution as input advice, which implies a predicted complete sequence of travel requests over an arbitrarily long timespan, which is impractical for real employment.
In this paper, we study the Bahncard problem with machine-learned predictions, adopting a different technical perspective. We address the general scenario where travel requests may arise at any time with diverse ticket prices. We develop an algorithm, named PFSUM, which takes short-term predictions on future trips as inputs. We derive its competitive ratio under any prediction error that is naturally defined as the difference between the predicted and true values. To present our results, we introduce several notations. The Bahncard problem is instantiated by three parameters and denoted by BP(C, 5, T), meaning that a Bahneard costs C, reduces any (regular) ticket price p to Bp for some 0 S 3 < 1, and is valid for time period of T. When 3 = O and T + 2o, the Bahncard problem reduces to the well-known ski-rental problem. Following the definition in
we take the competitive ratio of baaning-auggentee online algorithm ALG as function CRALG (17) of the prediction error 1j. ALG is ō-consistent (O) = ó, and I-robust if CRALG (1) S for all 1).
At any time l when a travel request arises and there is no a valid Bahncard, prediction on the total (regular) ticket price of all travel requests in the upcoming interval [t. + T) is made. Incorporating this prediction, PFSUM purchases a Bahncard at time t when (i) the total ticket price in the past interval (t- T, t| is least y and (ii) the predicted total ticket price in ft. t T) is also at least 7 where 7 == C/(1 - B). Denoting by the maximum prediction error, we derive that
0 S S 1-00h+n (1+
(2- (++
CRPFSUM(1)) {
11 > %
The result shows that PFSUM is 2/(1 + 3) conssisttt and 1 1/B-robust, and its competitive ratio degrades smoothly as the prediction error increases. We also share our experience in the design of PFSUM with some interesting observations.
2
Related Work
The Bahncard problem. Fleischer was the first to study the Bahncard problem. By extending the optimal 2-competitive break-even algorithm for ski-rental, he proposed an optimal (2 B)- competitive deterministic algorithm named SUM for BP(C, 3, T). He also proposed randomized
algorithm named RAND for BP(C, B, B,C,, oo), and proved that it is e/(e - 1 + 3) comppetiieee He conjectured that RAND keeps the same competitiveness for T < xc. Karlin et al. randomized online algorithm for TCP acknowledgement and applied it to BP B, B) with the conjecture settled positively. In addition, the Bahncard problem was extended to several realistic problems in computer systems such as bandwidth cost minimization [19], cloud instance reservation 200, and data migration
[8] designed
(2I]. Notably, Wang et al. [20] designed algorithms incorporating short-term predictions about the future for reserving virtual machine instances in clouds, which brings inspiration to our algorithm design.
Gearning-augmenter algorithms. Learning- augmented algorithms aim to leverage machine- leamnd predictions to improve the performance in both theory and practice 22 Algorithms using possibly imperfect predictions have found applications in numerous important problems 4 91 27
See httpt:tt/// wwwgaaogthhiie wittt with-predi ctions. gi github. io/ for a comprehensive collection of the literature.
To our knowledge, the only eearning-augmentie algorithms specifically designed for the Bahncard problem were developed by Bamas et al. [12) and Drygala et al. (28). Bamas et al. [12] proposed an
algorithm, named PDLA, which is 1/ 3 XB)- (e)- B)/ ())((e=1)-ccosiii ---cosiistent and (e* () 1)-
robust when C + 20, where X E (0, 1] is a typer-parameter of the algorithm. Their method, as previously discussed, is limited to scenarios with slotted time and uniform ticket prices for all travel requests. Our approach significantly differs from [12]. First, we address the general scenario where travel requests can arise at any time and feature varied ticket prices. Second, our algorithm utilizes short-term predictions provided at the times when travel requests are made, in contrast to their method which requires predicting a complete solution. We experimentally compare our algorithm with that of [2 in Section S Drygala et al. (28 focused on how many predictions are required to gather enough

---

information to output optimal Bahncard purchasing schedule, assuming all predictions are correct. The sharning-uugmene algorithm proposed takes suggested sequence of buying times as input and assumes slotted time setting, thereby sharing similar drawbacks to [12]
Im et al. [26] explored somewhat related TCP acknowledgement problem with machine-learned predictions. They introduced a new prediction error measure designed to assess how much the optimal objective value changes the difference between actual requests and predieted requests varies. A detailed comparison between our work and [26] is provided in Appendix A.I of 22]
3 Preliminaries
We adhere to the notations coined by Fleischer M. BP 3, T) with C 0, 0, and 0 < 3 < 1 is request-answer game between an online algorithm ALG and an adversary (see, e.g., 300 The adversary presents finite sequence of travel requests o = 01 .... .... where each or a tuple Pt)
that contains the travel time t, 0 and the regular ticket price pæ 2 0. The travel requests presented in chronological order: 0 S t1 < t2
ALG needs to react to each travel request o;. If ALG does not have a valid Bahncard, it can opt to buy the ticket with the regular price ps. or first purchase a Bahncard which costs C. and then pay the ticket price with 8 8-discount, i.e., 3p, A Bahncard purchased at time t is valid during the time interval [t, t + T). Note that a travel request arising time + T does not benefit from the Bahneard purchased at time L. We say is reduced request of ALG if ALG has valid Bahncard at time 4, Otherwise, as is a regular request of ALG. We use (LG to denote ALG's cost on oy:
ALG(o,)= = 3p; ALG has a valid Bahncard at t, Pi otherwise.
We denote by ALG(ar) the total cost of ALG for reacting to all the travel requests in a. The competitive ratio of ALG is defined by CRALG == max, ALG
where OPT is an optimal offline algorithm for BP 3, T). We use I to denote the partial cost incurred during time interval I: (LG = xr Extezz ALG(a;), where is the number of Bahncards purchased by ALG in I. Additionally, we use c(o; I) denote the total regular cost in I: c(a: := Ext,er E Pi- Given time length 1, we define the l-recent-cost of a at time I as c(a; (1 - 1, 4). Similarly, we define the I-future-cost of a at time f. as c(ar; [t, 1 + 1)). In our design, we assume that when travel request (t,p) p) arises, a short-term prediction of the total regular cost in the time interval [t, + +T) can be made. To represent prediction errors, we use a(o; [t, + T)) to denote the predicted total regular cost in [t, + T). Sometimes we are concerned about the regular requests of an algorithm ALG in a recent time interval. Thus, we further define the regular (-recent-cost of ALG on at time & as
ALG (a; (t (, =
Pj.
d: is regular request of ALG in (1-1,1)
Without loss of generality, we assume that an online algorithm ALG or an optimal offline algorithm OPT considers purchasing Bahncards the times of regular requests only. The rationale is that the purchase of a Bahncard at any other time can always be delayed to the next regular request without increasing the total cost.
Lemma 3.1. M For any time t, if ((
27: C1110//1111111 3), OPT has at least one reduced request in [t, t + T). The same holds for the time interval (t, + T...
[t,t+
7 is known as the break-even point, i.e., the threshold to purchase a Bahncard at time / for minimizing the cost incurred in the time interval [t, TT
Corollary 3.2. At any time t, if the T T-futurecost c(a; [t, T)) < % OPT does not purchase Bahncard at t.
An optimal deterministic online algorithm for the Bahncard problem is SUM, which is (2 - B)- competitive (.] SUM purchases Bahncard at regular request (t, p) whenever its regular T -ereent- cost at time t is at least 7, i.c., SUM" (or; (t- T, t]) 2 7.
3

---

4 Leanning-Augmented Algorithms for the Bahncard Problem
4.1 Initial Attempt
The SUM algorithm developed in 1 purchases Bahncard based on the cost incurred in the past only. It is likely that there is no further travel request in the valid time of the Bahncard besides the request at the purchasing time. Our initial attempt is adaptation of the A. algorithm proposed in [20]. Aiming to save cost, the A4 algorithm shifts the cost consideration for Bahncard purchasing towards the future with the help of predictions. That is, Bahncard is purchased based on a combination of the actual cost incurred in the past and the predicted cost in the future. We name the adaptation of AN to the Bahncard problem SUM " Specificallly each regular request (t. p). SUM predicts the total regular cost in prediction window (t, t + w| where w (0 < < ')) is the length of the prediction window. SUM. purchases a Bahncard at a regular request (t. p) whenever the sum of the regular (T' - w) re)-tecent-cost at é and the predicted total regular cost in (t, + w] is at least 7, i.e.
SUM", (o; (t w - T, f)) + o(0;; (f, + w|) 2 7
(2)
Note that SUM.. reduces to SUM when w 0.
Unfortunately, SUM... not a good algorithm for using machine-learned predictions. We find that its consistency is at least (3 3) + 33), which is even larger than SUM's competitive ratio of 2 B since 3 < 1. We construct a travel request sequence to show the consistency result in Appendix AA.2 of [29]. Moreover. SUM.. does not have any bounded robustness. Consider another example where only one travel request (t, p) arises with p + O, but the predictor yields ē(;; (t, + w|) 2 y. Then, SUM,. purchases a Bahncard (t. p). Thus, we have SUM.,. (o)) = (C + 3p)/p cc.
SUM,, fails because if a Bahneard is purchased at time L, it is possible that most of the ticket cost in the interval (L + ticket cost is incurred from & onward and can benefit from the Bahncard purchased. As a result, SUM suffers from the same deficiency as SUM. We remark that it is not helpful to set the prediction window length w to T or even larger values, because the travel request arising at (or beyond) time + T (if any) is not covered by the Bahneard purchased at time t.
T, L + w/] is incurred before 1. Consequently, only a small fraction of the
4.2 Second Attempt
What we have learned from SUM,,. is that the Bahncard purchase condition should not be based on the total ticket cost in a past time interval and a future prediction window. Thus, our second algorithm FSUM (Future SUM) is designed to purchase Bahncard at regular request (f,p) whenever the predicted T-future-cost time is at least y, i.e.,
(to: T)) 2%
Note that FSUM + SUM because the Bahncard purchase condition of SUM, is Theorem 4.1. FSUM is 2/(1 + -onnsisttn
2
The proof is given in Appendix A.3 of (29]. FSUM's consistency is generally better than SUM's competitive ratio since 2/(1 + 3) < B always holds for 0 < 1. However, similar to SUM,.. FSUM does not have any bounded robustness. Consider again the example where only one travel request (t, p) arises with p -- 0. but the predictor yields ē(σ; [t, TT) 2 7. Then, FSUM purchases a Bahncard at (t,p) and FSUM())/OP((o) = (C' + 3p)/p p- + oc.
4.3 PFSUM Algorithm
FSUM fails achieve any bounded robustness because it completely ignores the historical infor- mation in the Bahncard purchase condition. Thus, the worst case is that the actual ticket cost in the prediction window close to 0, while the predictor forecasts that it exceeds 7, in which case hardly anything benefits from the Bahncard purchased. On the other hand, we note that SUM achieves decent competitive ratio because a Bahncard is purchased only when the regular T-recent-cost is
'Wang et al. 20 studied a restricted setting where time is slotted into hours and purchases are performed only the beginning of slots because virtual machine instances in clouds are billed in an hourly manner.

---

at least 7, so that the Bahncard cost can be charged to the regular T-recent-cost in the competitive analysis. Motivated by this observation, we introduce a new algorithm PFSUM (Past and Future SUM), in which the Bahncard purchase condition incorporates the ticket costs in both past time in- terval and future prediction window, but uses them separately rather than taking their sum. PFSUM
purchases a Bahncard at regular request (t,p) p) whenever (i) the T Trrecent-cost at is at least 7 i.e., c(o; (t T, t)) 2 7, and (ii) the predicted T ffffuure--oost at é is also at least 7, i.c. ē( [t, Note that the first condition is different from the condition for SUM to purchase a Bahncard: PFSUM considers the T T--recent-cost, but SUM considers only the regular T-recent-cost. The rationale is that by definition, the regular T-recent-cost is not covered by any Bahncard, so requiring it to be least y for Bahncard purchase would make the algorithm less effective in saving cost. Compared with FSUM, though PFSUM has additional condition for purchasing the Bahncard, it is somewhat surprising that PFSUM achieves the same consistency of 2/(1 + (3) as FSUM, as shown below.
T)) > Y
Given a travel request sequence we use μ41 < ... < M'm to denote the times when PFSUM purchases Bahneards. Accordingly, the timespan can be divided into epochs F,- == [1j.//+1)) for 0 j j S. m, where we define μ4 = 0 and 1mm-1 oo. Each epoch E; (except Eo) starts with an phase [1) My + (the valid time of the Bahncard purchased by PFSUM), followed by an off phase (n3 + T, ()++1 (in which there is no valid Bahncard by PFSUM). Epoch Eo has off phase only,
We define 17 as the maximum prediction error among all the predictions used by PFSUM:
|á(a; [t, 2 + T)) - c( ((,++)))
max
(t.p) is a regular request
Then, for any travel request (t, p) in an off phase, we have
- 1 ((o: s <c ((00:14477) +
(5)
The following lemmas will be used frequently in the competitive analysis of PFSUM.
Lemma 4.2. The total regular cost in an on phase is at least ? 1 17.
Proof. If c(a: [u5, + +T) < - 7) for some j. it follows from 5 that ö(a; [uj. M5 + T)) S =7, which means that PFSUM would not purchase a Bahncard
c(a; [Mg My + T))+1) +
at time py. leading to a contradiction. Thus, we must have c(a: 165 By + T)) 2 -1-
L
Lemma 4.3. In an off phuse, the total regular cost in any time interval [t, t + I) of length S T is less than 27 + 17-
Proof. Assume on the contrary that c(o: (t) 2 24 + n. We take the earliest travel request (t', p)
in [1, +)) such that c(a; [t. (')) 2 7. This implies (()) < 7. Then, we have c(a; [L' (+ 1))
co;; [1, l + ()) c(a; (1) > 2 7
++ 1.. Hence, c(o; (L' - T)) 2 c(a; (4, (1) 2 7 and
c(a; [t', + +T)
[t,;; >>)))>>>+
> n. By G.. the latter further leads to ć(o; |t', + +T)) >
c(a; [t','' + T)) n > 7 which means that PFSUM should purchase Bahncard at time t.
contradicting that t' E [t, (,,++ +1++ is in the off phase. Hence, c(a; [t, t + T)) < 27 + 1) must hold. O
Lemma 4.4. Suppose time interval [t, + T) overlaps with an off phase. Among the total regular cost in i + T), let s2, s3 and S4 denote those in the preceding on phase, the off phase, and the
succeeding on phase respectively (see Figure [ If0 < 17 S. 7, 82 S q and 31 S 7, then the total
regular cost in [t, t T) is more than 27 + T7, i.e., 32 + 83 34 < 27 +
on
off
on
time
T
Figure 1: Illustration for Lemma 4.4 The shaded rectangle is the valid time of a Bahncard purchased by OPT.
Proof. Assume on the contrary that 82 + 83 + 84 > 27 + 1j. Then, 83 > and hence there is at least one travel request during the off phase. We take the earliest travel request (!', (L',p) in the off phase, such that c(a; [1, (') 2 y. With a similar analysis to Lemma 4.3 we can derive that PFSUM should purchase Bahncard at time t', contradicting that t' is in the off phase.
5

---

We adopt intervals in which least one of PFSUM and OPT has valid Bahncard, and analyze the cost ratio between PFSUM and OPT in these intervals. Consider maximal contiguous time interval throughout which at least one of PFSUM and OPT has a valid Bahncard. As shown in Figure 2 there are 6 different patterns. If OPT and PFSUM purchase Bahncard at the same time, the time interval is exactly an on phase (Pattern D, and the cost ratio in it is 1 (Proposition 4.5). Otherwise, there are 5 different cases: the time interval does not overlap with any phase (Pattern II); and the time interval overlaps with at least one on phase - it can start at some time in an on or off phase and end at some time in an or off phase, giving rise to four cases (Patterns III to VI). In Patterns II to VI, we assume that none of the involved Bahncards purchased by OPT are bought at the same time as any Bahncards purchased by PFSUM.
approach to analyze PFSUM. Specifically, we focus on the time
Bahncard valid time by PFSUM
Bahncard valid by OPT
concerned interval
Pattern (completely overlap)
Pattern II (off within)
time
time
My T
f
Pattern III (off - off)
Pattern IV (off on)
T + T
time
time
Bi+a My+n + T
Pattern V (on - off)
Pattern VI (on on)
time
time
Titx Tota +
P5t T
Figure 2: All the 6 patterns of concerned time intervals in which either PFSUM or OPT has Bahncard, In Patterns III to VI, x is the number of Bahncards purchased by OPT in an on phase and expiring in the next on phase. can be any non-negative integer.
Proposition 4.5. (Pattern 1) If OPT purchases Bahncard at time T, at the beginning of epoch Egg. i.e., T2 = μj, then
PFSUM(a; o: j4g. + T)) 11
(6)
OPT(a; M4 + +))
Apparently, if the cost ratios between PFSUM and OPT of Patterns II to VI are all capped by the same bound, the competitive ratio of PFSUM is given by this bound. Unfortunately, this is not exactly true. In what follows, we show that the cost ratios of Patterns to V can be capped by the same bound (Propositions (46 and 4.7p. which is the competitive ratio of PFSUM that we would like to prove. For Pattern VI, we show that its cost ratio is capped by the same bound if particular condition holds, where we refer to such Pattern VI augmented Pattern VI (Proposition 4.8 For non-au -uggeneeeted Pattern VI, we show that it must be accompanied by Patterns I to IV in the sense that a time interval of non-augmenter a time interval of Pattern I, II, III or IV. We prove that the cost ratio of non- -ugmentedt Pattern VI combined with such Pattern I, II, III or IV capped by the same aforesaid bound (Propositions 4.9 10). This then concludes that PFSUM's 's competitive ratio is given by this bound.
Pattern VI must be preceded (not necessarily immediately) by
Proposition 4.6. (Pattern II) If OPT purchases a Bahncard at time Tq in the off phase of an epoch Eş and the Bahncardd expires in the same off phase, i.e., P2 + T < T < T. +7 T < Pj41 then
PFSUM(a: +T)
27 +
OPT( a; [T,, Te +T))
(1+ B>y + 37
Proof. Let c(a;; [T,, Ti +T)) Based on the definition of Pattemn II. OPT(a: [T, +T)) C+ BB (OPT buys a card at T.) and PFSUM(a; [Ts, + T)) x (PFSUM does not buy cards during any off phase). Hence, the cost ratio is C43+. which increases with since 3 < 1. By Lemma 4.3
< 2 + v). Thus, the cost ratio is bounded by C+P(2>+0) (133)++(2144) (I+7)++0
2
2
2

---

The proof technique of the following propositions for Patterns III to VI is to divide the time interval concerned into sub-intervals, where each sub-interval starts and ends at the time when OPT or PFSUM purchases a Bahncard or Bahncard purchased expires. Then, for 0 S 7) S and 1j > 7, we respectively derive the upper bound of the cost ratio based on Lemmas (.2 to 4.4 All the bounds
in Propositions 4.7 to 4.8 are tight (achievable). Detailed proofs are given in Appendixes A.4 to A.5
of 229
Proposition 4.7. (Patterns III to V) The cost ratio in the time interval of Patterns III, IV, and V is bounded by
2x+(2-9)n
0 05
(1+0))-99
(8)
13-8)yt
[1+8)y-Ba
1>
We refer to Pattern VI as augmented Pattern VI if the total regular cost in the last on phase involved least y. Proposition 4.8 shows that the cost ratio of augmented Pattern VI capped by the same bound as Patterns III to V.
Proposition 4.8. (Augmented Pattern VI) Denote by bl and pa+a respectively the first and last Bahncards purchased by PFSUM in Puttern VI. If the total regular cost in the phase of Ejaz is at least 7, the cost ratio in the time interval of Pattern VI, i.e. [1jr Mi++ + ) is bounded by (8)
We remark that the cost ratio of general Pattern VI cannot be capped by the same bound as Patterns III to V. This is because in Pattern VI, PFSUM purchases one more Bahncard than OPT and hence has higher cost of card purchases, whereas PFSUM purchases less or equal numbers of Bahncards compared to OPT in patterns III to V. Thus, an additional condition is necessary in Proposition 4.8
Next, we examine non-augmented Pattern VI. Note that the time intervals of Patterns V and VI cannot exist in isolation. By the definition of PFSUM, when Bahneard is purchased at time MMj the total regular cost in the preceding interval (1, - 14] is at least y (referred to as feature o). Consequently, by Lemma 3.1 OPT must purchase Bahncard whose valid time overlaps with (Ny - T, Mi]. To deal with non-augmented Pattern VI that starts at time μ4 for some j. we backtrack from (4j to find out what happens earlier. Our target is to identify all possible patterns that might precede Pattern VI.
m
Rahncard valid time PFSUM
Bahneard valid time by OPT
plase
time
Pattern V/V//VI
Pattem V1
IV
=I
Paltern I/IIIV
Patiem
(a)
Figure 3: Pattern graph.
Note that the time interval (Ny - MT, definitely intersects with the off phase of epoch E,-1 and may also intersect with the on phase of E (if the off phase of E is shorter than T). Therefore, it is possible for all Patterns I to VI to precede Pattern VI (see 3 and (c) for illustrations). If Pattern I, IV or VI precedes Pattern VI, there is an off phase in between, in which neither PFSUM nor OPT holds a valid Bahncard. Figure a) presents a pattern graph to illustrate all possible concatenations of patterns preceding Pattern VI. In this graph, node represents pattern, and an edge from node i node j means pattern can precede pattern j. Since every Pattern or VI must be preceded by some pattern, the backtracking will always encounter a time interval of Pattern I, II, III or IV. We stop backtracking at the first Pattern I, II, III or IV encountered.
We use P1 @ to denote the composite of pattern P1 followed by pattern P2i use Dd to denote a sequence comprising y consecutive instances of pattern p. and use {PI..... Pn] @ pj to represent all possible composite patterns of the form pæ py for each i = I,...,n. n. Then, the patterns encountered the backtracking can be represented by
(I, (V.
(9)
7

---

where y can be any non- non-negative integers. Following the feature o, for each VI in (V, VIJ" of ( the total regular cost the last on phase of Pattern VI and the following off phase is easy to see that the cost ratio between PFSUM and OPT in the time interval of such Pattern VI no larger than that augmented Pattern VI and hence the upper bound given in Proposition 4.8 For each V in (V. VI}a of ( the cost ratio of Pattern V is capped by the same bound based on Proposition 4.7 In the following, we prove that the cost ratio of non-augmented Pattern VI combined with Pattern I, I1, III or IV at the beginning of (9) is also capped by the same bound.
least 7 It
Proposition 4.9. The cost ratio in the combination of time interval of Pattern VI and a time interval of Pattern II or III is bounded by
Proof Sketch. Note that in Patterns II and III, PFSUM purchases one less Bahneard than OPT. Recall that in Pattern VI, PFSUM purchases one more Bahncard than OPT. Hence, when considering Pattern VI with Pattern or together, PFSUM purchases the same number of Bahncards as OPT. Therefore, we can use the same technique as Proposition 4.7 to cap the cost ratio by the same bound. See Appendix of (29) for details.
Proposition 4.10. The cost ratio in the combination of a time interval of Puttern VI and a time interval of Pattern I or IV encountered in backtracking is bounded by (8)
Proof Sketch. Consider Pattern IV. When analyzing the cost ratio of Pattern IV in Proposition 4.7 it assumed that the total regular cost in the last on phase is at least y - 17. In IV of (). following the feature o, the total cost of travel requests in the last on phase of Pattern IV and the following off phase is at least y. Thus, there is an additional cost of at least 1). Therefore, we can "migrate" an additional cost of to the non- non-augmented Pattern VI at the end of (9) and make the latter become an augmented Pattern VI so that the result of Proposition 4.8 can be applied. Meanwhile, the proof of Proposition| 4.7 still applies to the Pattern IV even if the cost 1) is removed from the last on phase. Hence, after migrating the cost of 1), the Patterns IV and VI involved have the same upper bound of cost ratio given in (8) The proof for Pattern I is similar. See Appendix A.7 of [29] for details. O
By the above analysis and Propositions 4.6 to 4.10 we have:
Theorem 4.11. PFSUM has a competitive ratio of
(2-
05
CRPFSUM(())
(1+D)-+0n
(10)
13 +
(1+
17 7
By letting 77 0. easy to see that the consistency of PFSUM is 2/ + 3). Note that the
competitive ratio of (1O) is continuous function of the prediction error y, It increases from 2/ + () (4 8) 2,8) as 7) increases from 0 to y, and further increases from (4 - (113)/1110 + 2,3) towards 1/3 as 17 increases from y towards infinity. Hence, PFSUM is 1/B-robust.
5
Experiments
We conduct extensive experiments to compare PFSUM with SUM M. PDLA 12]. SUM,, (Section
4.1). FSUM (Section 4.2)). and SRL (Ski-Rental-based Learning algorithm), where SRL is adapted from Algorithm proposed in 4 for ski-rental. SRL performs as follows. Let À E (0. 1] be a hyper-parameter. SRL purchases Bahncard a regular request (t.p) if and only if there exists time L' (I T, 1] that satisfies one of the following conditions: (i) the predicted T-future-cost at time I' is no less than 7, and the total regular cost in [L', / is greater than Xry; or (ii) the predicted T-future-cost at time 1' is less than y, and the total regular cost in [[,4] is greater than 7/X.
We test SUM,,, with SRL and PDLA, we discretize time over a sufficiently long timespan. closely approximating a continuous time scenario. The experimental results across diverse input instances demonstrate the superior performance of PFSUM
T/2, and test SRL and PDLA with À set to 0.2, 0.5, and 1. To accommodate
Input instances. Referring to the experimental setup of [3I,, we consider two main types of traveler profiles: commuters, and occasional travelers. We set the timespan at 2000 days, during which commuters travel every day. For occasional travelers, there is time gap between travel requests. We model the inter-request time of occasional travelers using an exponential distribution with mean of 2. We consider only one travel request per day. This is because multiple travel requests occurring
8

---

on the same day can be effectively treated as single request with combined ticket price, since Bahncard's validity either covers an entire day or does not cover any part of the day.
For each request sequence generated, we investigate three types of ticket price distributions: a Normal distribution with mean of 50 and variance of 25, Uniform distribution centered around mean of 50, and a Pareto distribution called the Lomax distribution with shape parameter of 2 and scale parameter of 50. Our choice of the Pareto distribution stems from the observation that prices of travel requests in the real world often exhibit a heavy tail, which suggests that a minority of travel requests typically account for significant portion of total cost. Such heavy-taile distributions are often hypothesized to adhere to some form of Pareto distributions [3 33
Noisy prediction. The predictions the methodology used by Bamas et al. 12] Specifically, we introduce a perturbation probability For each day in given instance, with probability p, the travel request on that day is removed, if it exists. Meanwhile, with probability used for generating ticket prices, to the price of the travel request, or simply add a travel request if no request exists on that day. These two operations are executed independently. We vary the perturbation probability from 0 to 1 in the experiments. Intuitively, the prediction error increases with the perturbation probability. The predictions needed by SRL, SUM FSUM, and PFSUM are derived from the total regular cost over the specified time period in the perturbed instance. For PDLA, the predicted solution is obtained by executing the offline optimal algorithm on the perturbed instance.
generated by adding noise to the original instance, following
we add random noise, sampled from the same distribution
Average cost ra5o
1.125
Average cost ratio
3.10
SUN
RUN
3,100
1.08
5UN
3.08
Average
1.05
POLA2-0
1.04
1.080
3.04
SR.A-11
FOLMA-02
2.02
1.055
1.07
SR-A-13)
0.0
0.2
0.4
3.0
0.0
0.2
0.4
0.5
1.0
0.0
0.2
0.4
0.
0.8
10
Perturbing probability
Perturbing probability
Perturbing probability
(a) Commuters (U)
(b) Commuters (N)
(c) Commuters (P)
Figure 4: The cost ratios for commuters (3 T 1 100). "U", "N" and "P" represent Uniform, Normal and Pareto ticket price distributions respectively.
Average cost rato
1.2
Average cost ratio
1.150
SUM
FSUM
2.15
115
SUN.
RSUU
1.10
Average
1.0
1.075
ROAA-1
105
105
1.050
1.025
1.00
1.000
SPLL 02
0.0
0.6 Perturbing prozebility
0.2
0.
0.0
0.2
0.4
0.8
1.0
0.0
0.2
0.4
0.6
0.8
3.0
Perturbing probability
Perturbing probebility
(a) Occas. travelers (U)
(b) Occas. travelers (N)
(c) Occas. travelers (P)
Figure 5: The cost ratios for occasional travelers (8 = 0 10, == 100). "U", "N" and "p" represent Uniform, Normal and Pareto ticket price distributions respectively.
Results and discussion. For all types of input instances, the algorithms exhibit similar relative performance. We present in Figures to the results obtained for commuters and occasional travelers 10 (or 5). C' = 100, and different ticket price distributions,
when setting 3 = 0.8 (or 0.6). T including the Uniform distribution, the Normal distribution, and the Pareto distribution. Experimental results for other settings are given in Appendix A.8 of 229]. Each curve in the figure represents the average cost ratio between an algorithm and OPT over 100 experiment runs. The shaded area represents the 95% confidence interval of the corresponding curve.
We make the following observations from the experimental results. (1) When predictions are good (perturbation probability is small). PFSUM, FSUM, SUM... and SRL all perform better than SUM. This shows that predictions on the ticket prices of short-term future trips are useful for reducing the total cost. With perfect predictions (perturbation probability 0), in most cases, either PFSUM or

---

Average cost ratio
1.25
125
Average cost ratto
SUH
1.20
1.20
SIM,
FFSU
1:15
POLAH=11
Average
1.30
110
1.30
PO. 21
S01//=3)
105
0.2
0.6
0.6
0.0
0.2
04
0.8
0.8
1.0
0.2
0.6 0.8
Perturbing probability
Perturbing probsbility
Perturbing probability
(a) Commuters (U)
(b) Commuters (N)
(c) Commuters (P)
Figure 6: The cost ratios for commuters (3 0.6, T.6, - 100). "U", "N" and "p" represent Uniform, Normal and Pareto ticket price distributions respectively.
Average rato
1:30
Averrgg Peorago cUsT ratio
1.25
SUM
S.N,
120
HSUN
1.15
Average
115
ROLAI 4.5)
1.10
RULA1-521
1.05
105
0.6
0.2
100
0.4
1.0
Perturbing probability
Perturbing probability
Perturbing probability
(a) Occas. travelers (U)
(b) Occas. travelers (N)
(c) Occas. travelers (P)
Figure 7: The cost ratios for occasional travelers (3 =.6, T. 5, = 100). "U", "N" and "p" represent Uniform, Normal and Pareto ticket price distributions respectively.
FSUM produces the lowest cost ratio among all algorithms. This empirically confirms that PFSUM and FSUM have better consistency than SUM and SUM,.. (2) PFSUM outperforms all the other algorithms for a wide range of perturbation probability, demonstrating that PFSUM makes wise of predictions. In general, PFSUM has the narrowest confidence intervals, indicating that its results are the most stable among all algorithms. (3) For the Pareto distribution, as the prediction error increases, PFSUM demonstrates its robustness through gradual and smooth rise in the cost ratio Even
Even when the perturbation probability is large, PFSUM hardly performs worse than SUM. In contrast, the performance of SUM,,, and FSUM deteriorates rapidly with increasing perturbation probability, showing their poor robustness. (4) The primal- based algorithm PDLA generally has much higher cost ratios than PFSUM and even the conventional online algorithm SUM. This shows that it is important to take ad advantage of the characteristics of the Bahncard (it is valid for a fixed time period only and provides the same discount to all the tickets purchased therein) when designing learning-aus augmeeted algorithms. (5) PFSUM consistently outperforms SRL, particularly in scenarios with significant prediction errors. While the performance of SRL improves with increasing under high prediction errors, as a larger À leads to reduced reliance on the predictions and enhances the algorithm's 's robustness, its overall performance remains inferior to that SUM.
6 Discussions and Conclusions
We have developed new PFSUM makes predictions on the short-term future only, aligning closely with the temporal nature of the Bahncard problem and the practice of real-world ML predictions. We present comprehensive analysis of PFSUM's competitive ratio under arbitrary prediction errors by a divide-and-comm -nd--onqueer approach. Experimental results demonstrate significant performance advantages of PFSUM.
algorithm called PFSUM for the Bahncard problem.
Different from prior works, we do not predict full sequence of requests from the outset, and predict just sum of near-future requests (cost) when needed. In some online problems with temporal aspects, compared with individual requests, the aggregated arrival pattern across a group requests is more predictable (see, e.g., 34 Thus, our approach can enhance the learnability of ML predictions. We believe that our analysis and result will be useful to various applications of the Bahncard problem as well as other problems with recurring renting-or or-buying phenomena.
10

---

Acknowledgments and Disclosure of Funding
This work was supported in part by the Singapore Ministry of Education under Academic Research Fund Tier 2 Award MOE-T2EP20122-0007 the National Natural Science Foundation of China under Grants 62125206 and U20A20173, the National Key Research and Development Program of China under Grant 2022YFB450010 and the Key Research Project of Zhejiang Province under Grant 2022C01 145, Hailiang Zhao's work is supported by Zhejiang University Education Foundation Qizhen Scholar Foundation.
References
[1] Rudolf Fleischer. On the bahncard problem. Theoretical Computer Science, 268(1): 2001.
[2] Allan Borodin and Ran El- Ylniv... Online Computation and Competitive Analysis, volume 53, Cambridge University Press Cambridge, 1998.
[3] Thodoris Lykouris and Sergei Vassilvtiskii. Competitive caching with machine learned advice. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80, 2018.
[4] Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. Advances in Neural Information Processing Systems, 31, 2018.
[5] Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or- buy with expert advice. Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 23277 PMLR, 09-15 Jun 2019.
[6] Alexander Wei and Fred Zhang. Optimal robustness-consiitenne consistenci trade-offs for learning- augmented online algorithms. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 8042-8053. Curran Associates, Inc., 2020.
[7] Shufan Wang, Jian Li, and Shiqiang Wang. Online algorithms for multi-shop ski rental with machine learned advice. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1150-8160 Curran Associates, Inc., 2020.
[8] Yongho Shin, Changyeol Lee, Gukryeol Lee, and Hyung- Chang-Chan An. Improved learning- augmented algorithms for the multi-option ski rental problem via best-possible competitive analysis. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference Ma- chine Learning, volume 202 of Proceedings of Machine Learning Research, pages 31539-31561. PMLR, 23-29 Jul 2023. URL h
mlr .wresppees///eee Sanass/200 v22///22////// shin23c .hmll
[9] Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Non-clairvoyant scheduling with predictions. Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures, pages 285-294, 2021.
[10] Yossi Azar, Stefano Leonardi, and Noam Touitou. Flow time scheduling with uncertain processing time. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, STOC 2021, page 1070-1080, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450380539, doi: 10. 10.1145/34063255335555
[11] Justin Chen, Sandeep Silwal, Ali Vakilian, and Fred Zhang. Faster fundamental graph algorithms via learned predictions. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 3583- 3602. PMLR, 17-23 Jul 2022.
11

---

[12] Etienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning augmented algorithms. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 20083-20094. Curran Associates, Inc., 2020.
[13]
Keerti Anand, Rong Ge, Amit Kumar, and Debmaayy Panigrahi. Online algorithms with multiple predictions. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 582-598.
PMLR, 17-23 Jul 2022.
[14] Paolo Ferragina, Fabrizio Lillo, and Giorgio Vinciguerra. On the performance of learned data structures. Theoretical Computer Science, 871:107-120, 2021. ISSN 0304-3975, doi: 20.2....00..........
[15] Antonio Boffa, Paolo Ferragina, and Giorgio Vinciguerra. A learned approach to design compressed rank/select data structures. ACM Trans. Algorithms, 18(3), oct 2022. ISSN 1549-6325. doi: 10.1 145/3524060.
[16] Honghao Lin, Tian Luo, and David Woodruff. Learning augmented binary search trees. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages (3431-1344) PMLR, 17-23 Jul 2022.
[17] Niv Buchbinder, Kamal Jain, and Joseph Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. In European Symposium on Algorithms, pages 253-264. Springer, 2007.
[18] Anna R. Karlin, Claire Kenyon, and Dana Randall. Dynamic tcp acknowledgement and other stories about e/(e-1). In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, STOC '01, page 502-509, New York, NY, USA, 2001. Association for Computing Machinery. ISBN 1581 133499.
doi: 10. R..114/807522.888844
[19] Micah Adler, Ramesh K. Sitaraman, and Harish Venkataramani. Algorithms for optimizing the bandwidth cost of content delivery. Computer Networks, 55(18)4407-44020, 2011. ISSN 1389- 1286. doi: https://doi.org/ http///ddooorr///// wwtgg/10..io 11116/6.c.mmee.22200 1.07.015. Intereetbaased Content Delivery.
[20] Wei Wang, Baochun Li, and Ben Liang. To reserve or not to reserve: Optimal online multi- instance acquisition in iaas clouds. In 10th International Conference on Autonomic Computing (LICA)) 13), pages 13-22, 2013.
[21] Mingyu Liu, Li Pan, and Shijun Liu. Keep hot or go cold: A randomized online migration algorithm for cost optimization in staas clouds. IEEE Transactions on Network and Service Management, 18(4):4563 4575, 2021. doi:
[22] Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Communications of the ACM, 65(7):33-35, 2022.
[23] Keyuan Zhang, Zhongdong Liu, Nakjung Choi, and Bo Ji. rithm for two-level ski-rental problem. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 20293 -000000000 2024.
online algo-
[24] Keerti Anand, Rong Ge, and Debmalya Panigrahi. Customizing ML predictions for online algorithms. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 303-313, PMLR, 13-18 Jul 2020.
[25] Mozhengfu Liu and Xueyan Tang. Dynamic bin packing with predictions. Proc. ACM Meas. Anal. Comput. Syst., 6(3), Dec 2022. doi: 10.1145/357066
[26] Sungjin Im, Benjamin Moseley, Chenyang Xu, and Ruilong Zhang. Online dynamic acknowl- edgement with learned predictions. arXiv preprint arXiv:2305.18227, 2023.
12

---

[27] Jessica Maghakian, Russell Lee, Mohammad Hajiesmaili, Jian Li, Ramesh Sitaraman, and Zhenhua Liu. Applied online algorithms with heterogeneous predictors. In International Conference Machine Learning, pages 23484-23497. PMLR, 2023.
[28] Marina Drygala, Sai Ganesh Nagarajan, and Ola Svensson. Online algorithms with costly predictions. In International Conference on Artificial Intelligence and Statistics, pages 8078- 8101. PMLR, 2023.
[29] Hailiang Zhao, Xueyan Tang, Peng Chen, and Shuiguang Deng. Learning-augment algorithms for the bahncard problem. arXiv preprint arXiv:2410. 15257, 2024.
[30] Allan Borodin and Ran El- Vaniv.. Online computation and competitive analysis. cambridge university press, 2005.
[31] Mike Timm and Sabine Storandt. On the multi-kind bahncard problem. 2020.
[32] Mark EJ Newman. Power laws, pareto distributions and zipf's law. Contemporary physics, 46 (5):323-355 1213-351,22 2005.
[33] Michael Mitzenmacher. Dynamic models for file sizes and double pareto distributions. Internet mathematics, 1(3), 2004.
[34] Hong Zhang, Yupeng Tang, Anurag Khandelwal, and Ion Stoica. SHEPHERD: Serving DNNs in
the wild. In 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23), pages 787-808, Boston, MA, April 2023, USENIX Association. ISBN 978-1-939133-333 URL https: //www. usenix. org/ http:///errrrceeeeeeeee/e/eeeeae -aang//
13

---

A Appendix
A.1 Detailed Comparison between Our Work and (26)
Im et al. [26] studied a problem somewhat related to the Bahncard problem, focusing on TCP ac- knowledgement enhanced with machine-learned predictions. In the TCP acknowledgment problem, sequence of requests unfolds over time, each requiring acknowledgment, and a single acknowledg- ment can address all pending requests simultaneously. The objective here optimize the combined total of request delay and acknowledgemen cost (strike a balance between minimizing the delays in addressing requests and the costs of acknowledgments). Im et al. [26] introduced a novel prediction error measure that estimates how much the optimal objective value changes when the difference between the actual numbers of requests and the predictions varies. Im al. (6 took into account the temporal aspects of requests, akin to previous work [9. The new error measure enables their algorithm to achieve near-optimal consisteney and robustness simultaneously. Our investigation into the Bahncard problem differs significantly from theirs in terms of techniques employed. The main differences are summarized as follows.
In 126), predictions are made for full sequence of TCP acknowledgment requests. The prediction necessitates a discrete formulation, where time is partitioned into slots of equal length. In contrast, predictions within a future interval of length T. i.e., the length of the valid time period of a Bahncard. In our work, a prediction the short-term future is made only when travel request arises and there is no valid Bahncard, aligning more closely with real-world ML predictions.
approach refrains from discretization and requires only short-term
Im et al. (26] designed an error measure that is built on the change of the optimal objective value when the algorithm input varies from min pr] to max p:), where pt the ac- tual number of requests arising in time slot / and Pt is the predicted number. By contrast, our error measure estimates the quality of predictions directly. Harnessing the novel error mea- sure, Im et al. (26) formulated intricate algorithm, simultancously ensuring near-optimal consistency and robustness, In contrast, we design a simple and easily implementable algo- rithm using short-term predictions and demonstrates its significant performance advantages in experimental evaluations.
A.2 Consistency of SUM is at least (3 - 3) + B)
As shown in Figure 8 consider travel request sequence a of five requests: (41,)), (12, 7 c). (13: 2c). (La, and (15,e), where ( < l2 I l + w < 14 7 < 1 T < 13 < 44 <
t2 + T' < t3 + < is t4 + w. By the algorithm definition, SUM... purchases two Bahncards at times t and 4 respectively. while OPT purchases a Bahncard at time 12. When e + O, we have
SUM OPT(a)
2C' + 3(7 + 2c) + (7 2c)
2C + 87 +7
3 3-5 B
(2 20) 2c
C+ 2,3
1 1+
2c
time
15
Figure 8: An example where the shaded rectangle (resp. bold line) is the valid time of a Bahneard purchased by SUM,.. (resp. OPT). SUM,.. purchases a Bahneard at 4 because L22 < 4 + w and
since la + w < and SUM", (a; (la w T, ta)) + Ō(o: (la, la + w)) = (7 2x) + < 7. SUM, purchases a Bahncard at l4 because ts, ttt, to E (t1 + w T, t4 + w] and the total ticket cost is 7.
é ++ (7 - <) 7. SUM,,, does not purchase Bahncard
A.3 Proof of Theorem 4.1
For analyzing consistency, we have [)) (1,4++1)+))) T)) holds for any regular request
(l, Given a travel request sequence a, we denote by l1) <... < Mm the times when FSUM purchases Bahncards. Then, the timespan can be divided into epochs F, == [My, (1++1) for و S m, where define n4 = 0 and pm+1 co. Due to perfect predictions, each epoch E, (except En)
14

---

starts with an on phase 1p4,,14 H4 + T') in which the total regular cost is at least followed by an off phase [n, + T. (.+1). Epoch Eg has an off phase only. By the definition of FSUM, for any time in an off phase when travel request arises, we have
c(a; [t, + T)) - (( <.
(11)
Note that when both FSUM and OPT do not have a valid Bahncard, they pay the same cost. Thus, we focus on only the time intervals in which at least one of FSUM and OPT has a valid Bahncard. We examine the Bahncards purchased by OPT relative the Bahncards purchased by FSUM. Clearly, OPT purchases at most one Bahncard in any on phase since the length of an on phase is T. and OPT does not purchase any Bahncard in any off phase by (T and Corollary 3.2 For any epoch Ej. if OPT purchases its i-th Bahncard at time T3 E [1g Hj T), there are two cases to consider.
on
off
time
+ T
T
T
M441
Figure 9; Case I. The shaded rectangle is the valid time of Bahncard purchased by OPT.
Case I. The Bahncard expires in the following off phase [uy + T, 19+1). As shown in Figure 9 for ease of notation, we use $1, .i,..., 85 to denote the total regular costs in the time intervals [Ri [ay T/-1+ +T), [ma 1 + T) TT), [Ta: My + -T), [ng +T, +7), and [ra + (1)11) respectively. Here 7:-1 is the time when OPT purchases its (i 1)-th Bahneard. if we define
T;-1 -C. Note that some of the aforesaid intervals be empty that the corresponding total regular cost is O. Since the total regular cost in an on phase is at least 7, we have
$1
$2 + 83 2 7
(12)
By Lemma 3.1 we have $3+ 2 r. no travel request arises during the time interval [T,+ ++)), we have s O. Otherwise, we denote by f' E [n, + T. + +D) the time when the first travel request arises in this interval. Since e' is in an off phase, it follows from (1T) and T3 < t' that
84 = c(a; [ug + T + T)) = c(a; Ut' Ti + T)) S scoo; +T) <7.
(13)
Hence, we always have
84 < 7.
(14)
The cost ratio in epoch Eg is given by
FSUM(o; Ej)
C + B(s) + 83) + + 86
OO: E2))
C + ((1 + 84) + 82 + 85
C + B(s) +
83
14h & B < 1
C + +2 83
C + +2
+ 85
<
82 2 0 <<
<1
C + +2 83
C + (3)
86 2 0
C + +2
C + BY
C
2
C
7 1 1- 3
(15)
1+ 8
Case II. The Bahncard expires in the on phase of the next epoch, i.e., [M5+1s M5++ + T).
Case H-A. OPT does not purchase any Bahncard in [T; + T, M,5+1 + T). As shown in Figure 10
we use 81;...; 87 to denote the total regular costs in the time intervals [mg. max max(/y; T-- + 7})
[max (Mj, T--1 T-- + TT, T.), [Ts, My + T), [Mg + T, 1g44)), [M5+1.7 + T). [T + T, T, + and
15

---

[pt+1 + +T, (442)), respectively. Again 7;-1 is the time when OPT purchases its (i - 1)-th Bahncard. If I, we define Ti-1 -c.. Since the total regular cost in an on phase is least 7, we have
81 82 +
83 2 7:
(16)
35 + 96 2 7
(17)
off
time
T
7 + T
My+1 + T
15
Figure 10: Case II-A The shaded rectangle is the valid time of Bahncard purchased by OPT.
If no travel request arises during the time interval [n, + T, H5+1), we have = 0 S 56. Otherwise, we denote by t' [u + (141) the time when the first travel request arises in this interval. follows from and T; < t' that
84 + 85
; (K T. + 7)) = c(o:: [1' Ti + 7)) S 1' +T) <7.
(18)
Together with
17 we get
Therefore, we always have
84 S $6,
(19)
and
84 < 7..
(20)
The cost ratio in epochs Eg and Ej+1 is given by
FSUM(o; E, U E
2C' ((s] +2
$2
86)
84 87
OPT(a; Bj U Bj+1)
C' +
86) + 82 + 86 +
2C' +
86) + 84
+ 87
<1
C 3(s) +83 +
84
2C' + +2
56)
84 87
<
82 02 <1
C + ((1 + 83 85 86)
+ 84 + 87
2C' + B(s) +
86 56)
84 27
C' 3(81
+ 82 +
83 + 85 56)
2C' + 2
16 & 17
C 28y
C
(21)
1 + 3
1 3
In addition, the cost ratio in epoch Ey is given by
FSUM( Es)
C ((s + 82 + 53) 54
OPT E5)
C + (s1 + 83 + 84)
+ 82
C + (s1 + 82 + 83) 84
<
82 0 <1
C ((1 + 82 + 83 + 84)
$ C By 84
16
C+ + B88
C+
20
& B <
C+ By
2
C
7
(22)
I+
1-
Case HI-B. After time T; +7, OPO purchases another x: Bahncards at times 7i+1 Titz respectively
(x 1) shown in Figure II For each k = 1,... Z, the purchasing time 7 falls in the phase
16

---

M Hitk + T), and the expiry time Tet + T falls in the next on phase [14+k+11 1-:+++1--++++ Py+++1
T). OPT does not purchase any new Bahncard in [Tet= + 1,,++++1 + T). Essentially, the
pattern in epoch E, of Case II-A repeats times, followed by the pattern of Case II-A. By (22)
FSUM((;; F = BJ+k) S ( + +) for each ls = O,..... xt...--1. By (2T) FSUM(a; R5+z
F O/tx+1)/OPT((s Bj U B)+2+1) S 2/(1 + (3). Hence,
FSUM( a; E U U...UUUU Es+z+1) OPT (o; Ei U... U 1j+z+1)
2
(23)
1
off
on
off
time
1+T
H--1 741 Pas +T 15-2 My+++ Taxx + 7' Potx-1 +7
Figure 11: Case II-B. The shaded rectangle is the valid time of Bahncard purchased by OPT.
Case II-C. After time T. T. OPT purchases another x Bahncards at times Ti+1,...,, T4+2 respectively (x 2 1) as shown in Figure 12 For each l: L, ..... 1, the purchasing time T++*: falls in the on phase [ps+k; +T), and the expiry time Ti+ +++ falls in the next on phase [Mz4*+1 M1+k+1+++ +T). The purchasing time Titz falls in the phase [ ++ and the expiry time T++= +T falls in
the following off phase [15+ + (1+x+11. Essentially. the pattern in epoch Ej of Case II-A repeats times, followed by the pattern of Case I. By (22). FSUM( / Ej+&) S 2/(1 () S 2/ + 3). Hence,
for each = O,....2 x 1. By (5). FSUM (o; Bs+x) )/OPT(O:
FSUM(o; (;; E, U... U UBta)
2
<
(24)
OPT(a; Ej U... U Ejta)
1 3
off
off
off
time
M5 7-1 + T
To
Bj + Py11 a +T Tel Po+1 + T 1912 Prie + Taie Pyaz
Ties +
Figure 12: Case HI-C. The shaded rectangle is the valid time of Bahncard purchased by OPT.
If OPT does not purchase any Bahncard in the on phase of Ej. it must have purchased Bahncard in the on phase of Ej-1, and the Bahncard expires in the on phase of E, due to Lemma 3.1 Otherwise, purchasing another Bahncard at the beginning of E, can never increase the total cost, because the total regular cost in the on phase of E, is at least 7. Thus, Ej-1 and E, must fall into Case II-A or be the last two epochs of Case II-B, which have been analyzed above.
The theorem follows from
15p
23 and 24p.
A.4 Proof of Proposition 4.7
A.4.1 Proof for Pattern III
Proposition Restated. If OPT purchases + 2 Bahncards (r: 2 0) in successive on phases starting from E,. where (i) the first Bahneard has its purchase time т; falling expiry time T; + T falling in the on phase of Ej. (ii) for each k = 1,...,., the (k 1)-th Bahncard has its purchase time Titk falling in the on phase of Ez+ and its expiry time Ti+ + T falling in
the off phase of Ej-1 and its
the on phase of Ej+a, and (iii) the (x + 2)-th Bahncard has its purchase time T444+1 falling in the on phase of Ef+z and its expiry time T+++1 + T falling in the off phase of Ezaus then
PFSUM (Ts, Teta+1 + +T)
22 (1+2)++8)
0 0 17 S 7
(25)
OPT (o; (T. Teta-1 + +))
(1+9)++99
(3 13-9
1> 7,
where the upper bound is tight (achievable) when r - 0c.
Proof. As shown in Figure [3 we divide [T,, Tita+1 + TT) into 4x + 5 time intervals, where each time interval starts and ends with the time when OPT or PFSUM purchases a Bahncard or a Bahncard
purchased by OPT or PFSUM expires. Let these intervals be indexed by -1, 0, 1, .... 4x 3, and
17

---

let 8-1, $1, $2, 81z+3 denote the total regular costs in these intervals respectively. By definition, it is easy see that for each k 0, .... I 1, the (4k + 3)-th time interval, i... [Mi+* + T, ((+*++) (which is an off phase), is shorter than 7 since it is within the valid time of a Bahncard purchased by OPT.
off
on
off
off
time
71
Pg
11+1 14
T 15 T2l3
Myta Tiix T' cerri Byix + 12
80
f- 4o8 1i 2-
Skx
Figure 13: Illustration for Pattern III. The shaded rectangle is the valid time of a Bahncard purchased by OPT.
First, we observe that the cost ratio PFSUM [Tr [T, T4z241 /OPT) (T, Tiz++1 + +T) is less than 1/8, as shown below.
PFSUM o; (Ta, Tet++1 + T))
8
OPT [o; (Ti, T+tz+1 + T))
(x (2C + (s-1 s0) + Ek=0 ($8342 + 84R+3 + $1x-1) + ($10+2 + $12+3)
3 OPT (T, T++++1 + T))
Ek=o 84k+1 -B
(xr (x 1)C + Ei= (84k + 84k+1 + 84k+2) + =k==1 84
OPOPT( 0; [Ti, T+tz+1 T))
(x (d-2)C 5t
kk=u 84k + Σ k=o 84k+1 Ek=o S4K+2 3 Σ Ck=-1 84k+3
8. (T: [1i +T))
8(x + +1C +, 3,2 Ex k=o (s4k 84k+1 84k+2) + B 1k==180643 84k43
B OPT (o; (T, Tit++1 +
[(x +2 - B(x + 1)JC B(1 B) EL (sak 848+2) + B2) E $4k+11
B OPT(PT (a; [Ti, Tit+11 + +T)
0. (since 0 3 3 <> 1)
Thus, the following inequality always holds:
PFSUM a: [TH Te4441 + T)) 1
(26)
OPT (o; [T,, T4z++1 + +T) 3
Next, we analyze the upper bound of the cost ratio. There are two cases to consider.
Case I. S 17 7. By Corollary 3.2 for each k: 1, ...,.. x, the T T-future-cost at 7++841 is least i.e.,
+ 2
84k+2 + 84k43 + 84k44 2 y for each O,..., 84x42 84.43 7.
(27)
By Lemma 4.2 for each O.... v, we have
84k + 84k+1 + 84k42 2 17.
(28)
Note that all the travel requests in the (4k: + 2)-th (for k 0 ..., .) and the (4k + 4)-th (for
1...... x - 1) time intervals are reduced requests of both PFSUM and OPT. Thus, to maximize the cost ratio in [Ta, T4+++1 + T),, we should minimize these $4k+2 's and $ If they are greater
18

---

than 7, the cost ratio can be increased by decreasing $1k+2 or $4k+44 to y without violating (27) and Thus, for the purpose of deriving an upper bound on the cost ratio, we can assume that
28
84 S 7
for each 0, 0,... 2, for each
(29)
84 S 7
...9 x 1.
follows from 29 and Lemma 4.4 that
811++ + 54K+4 S 27 +1
for l: -1,
34k42 + 54k+3 + 84k+4 S 27 +1
for each k = Og..., 1, for k: I.
(30)
84k42 + 84k+3 S +1
As result, we have
PFSUM (T: Tez211 + +T)
OPT(a; To Te+a41 +T)
(x + ++++++ E kk= (sak 84k+1 + S4k+2) + Σ -k=-1 8ck+3
(or + 2)C / (A-1 + 80) + Σk= (84R+2 + 846+3 + 84k+4) + (84x+2 + 84r+3) + Eizo 84k+1
(x (x+ [(_1 + so) Ex=o (54R+2 + 946+3 + 848-44 + (94r42 + 81443)
(x + 2 + 3 (8_1 + 80) + Σド (844+2 + 84k+3 $44+4) + (842+2 + 84043) + Lk=o S4R+1
B E S4k+1 B) Ex=o (SAk + S16+2)
2x + 8 (s_ 50) + Σx=0 (54R+2 + 84 + 848+4) ($4042 + 842-3)
+ Ek== 948+1
(o + 1)C (r (27 +)) + + 84k+1 - (1 (3) Ei=o (84k + 84k+2)
(by 26 and 30
(2
k== S1k+1
(o + 1)C + (r -1 8 (1 5) En=o (Stk + S4k+1 + S1R+2)
(++))C+0(2+ + + Eb=o SAK+1
(o + 1)C + (x +))+ - (1- B) + 1)(7-1) (by 28
(x
Σx=0 84k+1
(x + I)C + (r +12+))))))- +++) 3) + - 1)(7-1) (since
84k41 2 0)
k=
x (C + (7 + 2n)) +C (++-+++- B(7 1))
xCC'+ (())
8(4 + 2n))
x22y + - ()) + (3 8)n)
x((1 + 3)n + (m) + ((2 2,)r + 2,3)
27y + (2 - B)n
<
(when x + 00)
(31)
(1 + 8)y + Br)
Case II. 17 > 7. By Lemma 4.3 for each h: = -1,0, the total regular cost in the (4k + 3)-h time interval (which is in an off phase and has length most 7') is less than 27 + ty.
84k43 27 + n
(32)
On the other hand, the total regular cost in any time interval in phase is non-negative. As result, we have
PFSUM (Ts, T4a+11 + -T))
(x (x+
(by 26 and (32
OPT (a; (Ta T4t+11 + T))
( +++)
x(C' ( (2C+ (C (47 + 2n))
+
x B m)) + (2C 8(4 + 27))
19

---

C+ (27+ + 11)
(when + 00)
C+ 3(2 +1)
(3 - (3-8)7++ +1
(33)
+ 8)7 + 87
The result follows from (31 and 33
A tight example is given in Figure
14
where + c0. The upper bound is achieved when 0 v 17 -
for each 1: 1,, ..., T' 1, S1k+3 7 + 2n,, $1x43 + 2n + t7 for each it 0, ..... 2, 81k = = 7.
$4k+1 #4 0, or when 1) for each k = -1, -1,.... 84k+43 = 2y + and for each
k 0,..., Jr, 84k: 84k-1 44 0.
off
off
off
time
72
Mj
7.
711
M141 7ii +
7 15
Mysa Ria + + Tis 1P/1x + Ti +
90 -1
52
81x43
7
21
7 + 20
0
7-
27 +
+
+1
(+>1)
Figure 14: A tight example for Pattern IV. The shaded rectangle is the valid time of a Bahncard purchased by OPT.
A.4.2 Proof for Pattern IV
Proposition Restated. If OPT purchases x + Bahhcards (a 2 0) in successive on phases starting from Ej, where (i) the first Bahncard has its purchase time T; falling in the off phase of E and its expiry time TÜ + T falling in the on phase of Fij, and (ii) for each k = 1, 1.....,, x. the (k + 1)-th Bahncard has its purchase time T++ falling in the on phase of Ej+s-1 and its expiry time T + T falling in the on phase of Ej+k, and (iii) OPT does not purchase any new Bahncard in the on phase of Ej+z, then
PFSUM o; [Te Mi+z + T))
2-+(2-8)a (L+8)++8n
0 S 7
(34)
OPT(a; (a; (Ti, Mi+z +))
(3-d)+tn
(1+8))+8
7
where the upper bound is tight (achievable) for any x.
Proof. As shown in Figure 15 we divide [Ts; fi+z + T) into 4r + 3 time intervals, where each time interval starts and ends with the time when OPT or PFSUM purchases Bahncard Bahncard purchased by OPT or PFSUM expires. Let these intervals be indexed by -1, 1, 2, ..., 4x + 1, and let 1, 80; 81, 82, ... 8 denote the total regular costs in these intervals respectively. By definition, it is easy to see that for each & = 0, .... x - 1, the (4k + 3)-th time interval, i.e., [My+* + T, (y+k+1)
(which is off phase), is shorter than T since it is within the valid time of a Bahncard purchased by OPT.
off
on
off
on
off
on
time
7
T3 T
M4
1o+1
1641
Tosa
Tine T Myta Ste
4 86
Serti
Figure 15: Illustration for Pattern IV. The shaded rectangle is the valid time of a Bahncard purchased by OPT.
First, we observe that the cost ratio PFSUM(a; [T,, Pjtx T)) (P) M34 + T)) is less than 1/3, as shown below.
1 PFSUM(a; [Tis Mj+z + T))
3 OPT (a; (Ta, Mj+a + T))
20

---

(x 10C+ (s-1+ so) + Ex=o (s1++2 + 918+3 s1k+1) + Ek= 81R+1
B O.O Mito T))
( 1JC+ 3
kk=u (8ak + 84k+1 1 84k+2) + (8ar saot1)
=KR=1 84k+3
B 8- 8-OPT σi [Ti Hト+z + T))
(x + +++1+++
K= S4k
Jt xt- K=0 S4k+2
-- k= S4R+3 + = 848+1
B OPT [i [T, Pa+0 + T))
+ 10C+
k== 84k + Σk= 84k+1 + 2k=0 S4k+22
2z-1
+ + 2--1 84k+3
8 OOPT [Ti M5+z +T)
- (1 + 1)C 8(1 101--11 B) > Jr k= SAk + k== $18+2) + (1- B²) Σ k== S1k+1
B OPT (o; [Ti, Hj+z +T)
0. (since < B 1)
Thus, the following incquality always holds:
PFSUM os (T.. Mito + T))
(35)
OPT a; [T, + T))
3
Next, we analyze the upper bound of the cost ratio. There
cases consider.
Case I. 0 S 7 S 7. By Corollary 3.2 for each -1, 1,0, o,.,,...... x, the T-future-cost at 7++6+1 is at least i.e.,
8-1 $-1 50 7
(36)
84R+2 + 84A + 946+4 27 for each k = O,..., 1.
By Lemma
4.2 we have
1ik + S1k+1 + $1k+2 7 17 for each O,..,, 1,
(37)
$4z + S4n+1 27 17.
Note that all the travel requests in the (4k + 2)-th (k O,.... 1) and the (4k + 4)-th (k -1, .... 2 1) time intervals are reduced requests of both PFSUM and OPT. Thus, to maximize the cost ratio in [Ts, Pj+z + T), we should minimize $4k+2 and 84k+44- If they are greater than y, the cost ratio can be increased by decreasing $ak+2 or $4k+44 to y without violating (36) and (37). Thus, for the purpose deriving an upper bound on the cost ratio, we can assume that
81442 S
for each l: = 0, ..., x 1, for each k = I,.... I 1.
(38)
$1k+1 S
It follows from
38 and Lemma 4.4 that
84k+3 + 84844 < 27 +
for k -1,
(39)
84h+2 + 84443 84k44 S 27 + 1
for each & = 0, .e.,..... x 1.
As result, we have
Hot4 T))
(a: + +T)
+ +IC +
Σx=1
(sak + sak+1 + 84x+2) + (SAz + Stu+1)
+ Σ k==1 84k+3
1IC+ 3 (s_1 + su) + Ei= (Su4+42 + Sakt3 $4k+4)
k= S4k+1
(x 1)C - (8_1 + so) + Σx (84842 + 94R43 + 94844) + 3 > 84k+11
(o + 1)C + (s_1 + s0) Σe
(Su442 + 84b43 + m1R+1) + Σ 81k+1
21

---

(1- B) Ek=o (su + S14+2) + 312
(x 1)C + 8 (s-1 + so) + Ek=o ($1R+2 + 51k+3 + $18+1)
+ Ek= 84k+1
+ (x (o + 1) + 11) + Ek=0 (1 (1- k=o (8ak 84k+2) 8AZ
(0 + ()) 11) + 2k= 84k+1
(by 35 and (39)
(x + [)(C + 27 +)) 1)) + Σi= 84k (1 (3) Ex=0 (84k + 84k+1 + 848+2) + (Sar + 84
(++ + 3(x +)) (2 + +1) Ei= $48+1
(x + 1)C +
(1 (1- (1-8)(e (x 1)(7 -1)
(by (37)
(++]]++[[++1())+++++ + Σk= S1k+1
(x + 1)C + +x+ - 3] + 1)(7-n) -) n)
(since
Sak+1 2 0)
+(x++++(+++))) +n)
k=
27 + 22 - BBn
(40)
(1 + ++87 + (m)
Case II. 17 > y. By Lemma 4.3 for each h = -,,0,... x, the total regular cost in the (4k + 3)-th time interval (which is in an off phase and has length most T)) is less than 2y + ry:
$4k+3 2y + 17.
(41)
On the other hand, the total regular cost in any time interval in phase is non-negative. As result, we have
PFSUM (o: 15+2 + T))
(x + 1)C + + +
by 35 and (41
OPT (o: (T, Mj-z + T))
(x+ + + +n)
(3 - Bay +n
(42)
(1 + B)y + Bnj
The result follows from 40 and
42
A tight example is given in Figure 16 where x = 0. The upper bound is achieved when 0 < 1 S
8-1 - 7 + 21,, 80 = 7 - 7. and 81
0, or when 1) > 7 8 8-1 + 27 + 7) and 8o = 81 = 0.
off
time
T:
Py
80
2n
0
(0
+ 2y +
0
(1>1)
Figure 16: A tight example for Pattern IV. The shaded rectangle is the valid time of a Bahncard purchased by OPT.
A.4.3 Proof for Pattern V
Proposition Restated. If (i) there is no Bahncard purchased by OPT expiring in the on phase of
Ej. (ii) OPT purchases x - Bahncards (x 2 0) in successive on phases starting from E,, where (a) for each A- 0, ..., I - I, the (A: + 1)-th Bahncard has its purchase time Ti+k falling in the on phase of Ej+ and its expiry time Ti+k + falling in the on phase of Eft8+1, and (b) the (x+ + 1) Bahncard has its purchase time 7+t falling in the phase of Ej+z and its expiry time Tit +T
falling in the off phase of Ey+z, then
PFSUM (o; [My, Tita + T))
22+(2-8)n
0 S 7
(++
(43)
OPT(a: [ny Tit + +T))
(3-9mtn
(1+0)++9
1 > 7
22

---

where the upper bound is tight (achievable) for any 2.
Proof. As shown in Figure 17 we divide [ز3 T + T) into 4x 3 time intervals, where each time interval starts and ends with the time when OPT or PFSUM purchases a Bahncard or a Bahncard purchased by OPT or PFSUM expires. Let these intervals be indexed by 2,2,... 4x + 3, and let $1, $2, .... 84z+3 denote the total regular costs in these intervals respectively. By definition, it is easy see that for each k O, ..., I 1, the (4k: + 3)-th time interval, i.c., [uj+* + T,, ((++++1) (which is an off phase), is shorter than I' since it is within the valid time of Bahncard purchased by OPT.
Next, analyze the upper bound of the cost ratio. There are two cases consider. off
on off
on
off
on
time
7 p441
12 T
Tit1 Pj+1
Pita T + Tite + Tota +
T
Saaf Stst 4811+2-
8AX-3
Figure 17: Illustration for Pattern V. The shaded rectangle the valid time of a Bahncard purchased by OPT.
First, we observe that the cost ratio PFSUM(a; T4x T+tz + ()) Tito + T)) is less than 1/9, as shown below.
1 PFSUM o: lug, T+t + T))
B OPT(a: [:: (Ky, Totx + T))
(x + 3 Ex=o (84x+2 + 84843 + 84844) + (84242 + 84443) + Et- 84R+1
B 9POP (a; [Mg, Tit + T))
8 8(0r 11C +3 ER=o (s4t+1 + 844+2 846+1) ($Lot1 81x42)
+ +E Sak+3
B OPOPT(22 [i: [ug, T+t + TT)
(x + 1)C+++++ 3
Ek=o 84k+2 + Ek=o Sik+3 Σx=0 Sak+4
+ =k= Sak+1
B OPT (z; [Mj Tetz + T))
8(x + 1)C 32
2k= 84k+1 + 1k=o 84k+2 + 2k=0
848-44
+ B Ei= 84K+3
3.OTT(P 0: [155 Titx +T))
(1 -3)(x 1)C + (11 1 () Σx 2k= 84k+4 + Σi- 84k44) + (1 - (1-32) 1--2)// Ek S4h+1
B OPT (r; [Mi Tota + T))
00 (since 0 8 < L)
Thus, the following inequality always holds:
PFSUM [my. Ttt + +T)
1
<
(44)
OPT oo; [Ma T:zz + T))
3
Case 1. 1.05m 1) S 7. By Corollary 3.2 for each O,..., x, the T-future-cost at Ti4k is at least 7.
i.e.,
84R42 84h-3 + 84644 2 7 for each k O,... 1, 84z+2 + 84x43 2 7.
(45)
By Lemma 4.2 we have
81 32 27 2 77
(46)
84k + 8ak+1 + 84k+2 2 7 -n n
for each 1: = 1,..., T.
23

---

Note that all the travel requests in the (4k + 2)-th (for k = O.....)) and the (4k + 4)-th (for k O,..., 2 1) time intervals are reduced requests of both PFSUM and OPT. Thus, maximize the cost ratio in [ıg, Ti+= + 7), we should minimize these *4*+2 s and 94s+4's.. If they are greater than y the cost ratio can increased by decreasing 84k+22 or +4 to 7 without violating (45) and (46.. Thus, for the purpose of deriving an upper bound on the cost ratio, we can assume that
8 S
for each k = 0, ...... for each k 0, ..., I 1.
(47)
84k S
It follows from 47 and Lemma 4.4 that
+ 84k+22 + 84k+3 84 S 27
for each k = 0,..., for k x.
(48)
94h+2 + S1443 S 27 +1
As result, we have
PFSUM o; (M Teto Teta T))
OPT(a: Muj Titz + +T)
(x 1)C
k==
(54x+1 84k42 + sak+a) + (s4z+1 + S1xt2)
5
k== 84k+3
(x ( ++1) + 3
Ck (S4N+2 34843 + S4R+4) + (51242 + 84x+3)
> k= 54k+1
(x 1)C + Σx
(SIx+2 + 84k+3 84444) + 81z+2 + 812+3) + B33 Σ k=0 81k+1
1+C +
Ek=D
(S4K-42
84k43 + 844+4) + (84242 + 84m+3)
=x= 84k+1
(1- 3) Σ (s1++2 + S1k+1) + S1x+2
(o + 1)C + kk=0
(548+2 + 84k+3 84k+44 + (84r+2 + 84x+3)
+ E 84k+1
+ (1C (r 1) +1) + 81++1 (1 B) k== (91R42 + Sak+a) + S1x+2
+ 17) + Ekzo $ak+1
(by
and
(x + ++++ (x + 1)) + 2k=0 (x + 1)C + B( B 1) + 11) + 2k=o S4R+1
3) (8) + 82) + Ek=1 (84K + 848+1 + 848+2)
(x + 1)C + (r 1)(2 1)) 81k41 (1 B) + 1)(7 -1)
(by (46)
(x+1)C+3(2+1)2)
+ ΣE= S14+1
(xr + 1)C + (1+ () + 1)(7)))))))) -1)
-1
(since
Σ
84k+1 2 0)
+n)
k==0
+ (2 (2-81 B)n
(49)
(1 + +-30 Bm)
Case II. 17 7. By Lemma 4.3 for each k 0, ..., x, the total regular cost in the (4k + 3) time interval (which is in off phase and has length at most 7') is less than 2 7/:
34k43 < 27 + 77.
(50)
On the other hand, the total regular cost in any time interval in phase is non-negative. As result, we have
FSUM (o: [uy, T+tx + T))
(x+ 1)C (2
by and (50p
OPT [ Myy Ti-x T))
(x+ + +(x 1)
(3- 13-8)7+1
(51)
(1+ + B)r Bn
The result follows from 449 and 51
tight example is given in Figure 18 where x = 0. The upper bound achieved when 0 S 1) S 7,
81 0, 82 =y 7 17. and 83 + 21, when 7, $2 0, and 53 + 2 17.
24

---

off
time
71
T
T, +
Py+1
-2
7 20
0
27
1
(1> n)
Figure 18: A tight example for Pattern V. The shaded rectangle is the valid time of a Bahneard purchased by OPT.
A.5 Proof of Proposition 4.8 (For Augmented Pattern VI)
Proposition Restated. If (i) there is no Bahncard purchased by OPT expiring in the on phase of E.-- (ii) OPT purchases x Bahncards (x 2 1) successive on phases starting from Fj, where for each -, 1, the (A: + 1)-th Bahncard has its purchase time Ti4* falling in the phase of EJ+R and its expiry time Ti+l + T falling in the on phase of Ej+R+1, 1s and (iii) OPT does not purchase any new Bahncard in the on phase of Ejja. and (iv) the total regular cost in the on phase of Ej+z is at least y, then
PFSUM(a: (ng 1D+z + T))
2-+ [1
0 0.
Bl
(52)
(oT (aj,
Pj+z + T))
8-
By
1 7
where the upper bound is tight (achievable) for any x.
Proof. As shown in Figure 19 we divide [K] ffga + T") into 4x + 1 time intervals, where each time interval starts and ends with the time when OPT or PFSUM purchases a Bahncard Bahncard purchased by OPT or PFSUM expires. Let these intervals be indexed by 1, .... 4r + 1, and let $1, $2, ...: S4x+1 denote the total regular costs these intervals respectively. By definition, it is easy to see that for each & = O.... I - 1, the (4k + 3)-th time interval, i.e., [Ut+& + +T, (5+++1) (which is an off phase), is shorter than T since it is within the valid time of Bahncard purchased by OPT.
on
off
on
off
off
on
time
H4
By
Mit1 n3 THEs 1911
2y42 P
Mitz 7 + T Pive
84
96
Sae-1 Sur 4 84x+1 4
Figure 19: Illustration for Proposition 4.8 purchased by OPT.
The shaded rectangle is the valid time of a Bahncard
First, we observe that the cost ratio PFSUM (1g. + +T))) Myt + T)) < 1/3. as shown below:
1 PFSUM(a; [Ug Mi+t + T))
3
OPT( a; jujs Mitz + TT)
xC' + 3 Ex=
(s + S1k+3 + $1R+1) + +Er Sik+1
B.
OPT [Mgs T))
8 ( +1++++++ + 8 Σx=b (sak+1 + 84k42 + Sak+4) 1) + Saxt1
+ Ee 8ak+3
8. OPT [Mg M5+z + +T))
1--8xC 3C 8(1 3) Exz 84h+2 + 3(1 3) Ex-1
8th+4 + (1-93 Σ h= 84k+1
8. OPT(o: (o: [M3. Mitz + T))
11 -1 -)- - 3C + 3(1 3) Σ 244+2 + Ex 948+44
8. OPT (m/, Myyx + T))
25

---

(1 (1-B8 B²) - 84k+1 + 3(1 - (542 + 84x41)
+
(since <{<1))
3 OPT o: 1y- TT)
1--)x0C- - BC + 8(1 - -3)( Eizo 84k+2 + ER=o 84R+4)
8. OPT [1g M9+a + T))
(1 82) 1=
k= 84k+1 + B(1 - B)y
(since 8ax 842+1 2
8. OPT( (o; [1j Uj+0 + T))
- -)-C - B(1 - 3) 2 km0 84k+2 + Ex z-- 84k+4) + (1-1 -B2) 2x 84k+1
B. OPT(a; [ag, M8++ + 77)
>
(53)
Thus, the following inequality always holds:
PFSUM [ug M5+2 + +T) 1 OPT a:: (i5. T))
(54)
There are two cases to consider.
Case I. 0 < S y. By Corollary 3.2 for each k = O...., I 1, the T T-future-cost at T++ is at least 7, i.e.,
84k+2 + 84k+3 + 84k+4 2 7.
(55)
On the other hand, by Lemma 4.2 and the (iv)-th condition of the proposition, we have
$1 82 2 7 7/
94k + $ + 84k+2 2 7 - for each 1,.., x 1,
(56)
84m $42+1 2 7.
Note that for each h: = 0.... - 1, all the travel requests in the (4k + 2)-th and the (4k + 4)-th time intervals are reduced requests of both PFSUM and OPT. Thus. maximize the cost ratio in [pg My++ + T), we should minimize S1k+2 and 544+4 If they are greater than ?, the cost ratio can be increased by decreasing 84k+2 or $3k441 to 7 without violating (55) and (56) (except for $42). For 84z, it is greater than y, the cost ratio can be increased by decreasing it to without violating (55) and (56). Thus, for the purpose of deriving an upper bound on the cost ratio, we can assume that
84h 2
for each k = 0, O...., I 1, 84k S for each = 0,... & 1.
(57)
It follows from
57 and Lemma 4.4 that, for each k 0,..., 2.
84k42 84R43 + 54k+4 < 2 13. For x 1, we still have
(58)
848+2 + 84k43 + 84k S 27 +
(59)
Otherwise, there must exist time t in the off phase of Es+2-1 such that PFSUM purchases Bahncard, leading to a contradiction.
As result,
PFSUM ( (pj, Mjtt + T))
OPT(a: [Uj.115t + T))
(x + 1)C + 3
5-- k=0
(sak+1 + 84842 + saR+a) + 812+1 + Ex=1 84R+3
s0 +
(88842 + 84443 + = + Ex=0 816+1
26

---

(x 1++1)C++ + 1-88888 3E 84 + >k=0 (842-4 + 54R43 + 84844)
(1 - Ex=
(84R42 + 848444
xC + + Ek=0 (84k+42 + 84643 + 84k+44
+ =k== 84k+1
(x 1)C Ek=o +1 + k== (84k+22 + 84k+3 + 848+4)
xC +
Ex=O (ak-22 + 84k+3 + sak+a) + Ek= 84k+1
(1-
EX (S4R+1 + 84 + 84x+44
+ 84m+1
xC + 3
Ei=0 (Sak+2 + S1k+3 +
S s1x+1)
+ Ei= Sak+1
(x + 1)C
Ek= S4k+1 + ER=O (sab+2 + $4k+3 + $4k+4)
xC + + Ex=o (51k-2 S1k+3 + Sak+1)
+ + S4K+1
(1 - () (81 + 82) + ΣE= (84k + s4k+1 + 84x+2) + (Sar + 841+1)
xC + 3 Ek=D (S4K+2 + Sak+3 +4
Ek=u 94k++1
(x + 1)C' + Σx O= S1R+1 + Σ k== S51++ + S1k43 + s1k+1) - (1- [2) 11) +
(by (56)
x0 + B Σ k=0 85k++ -4 +3-331110 + 84 + Ei=z $4k+1
(x + 1)C E (S4k+2 846+43 + S4k+4) - (1 () [x(7 11) + +
(since Σ
84R+1 2 0)
xC + 3 > (44R42 + 842+3 + 84x++4)
k=0
(x + I)C + <27 + 1) - (1 3) |x(7 11) +7
(by 54 58 and 559
xC + (x + 17)
(x + 1)(1 B)y + x: (2 + 11) (1 3) [x(( 1) 7
(since C = - 8)))
xx1 - 8)7 - Bx + 1)
27 12-22-))) 23)m
(60)
(1+ (31]
Case II. 17 7. In this case, the total regular cost in any time interval in an phase can be zero (except for the on phase of Ej+z):
81 82 2 0,
84k + 846+1
+ 84 2 0
for each l: = 1,..., 2 1,
(61)
84 + 840+1 2 7-
On the other hand, by Lemma 4.3 for each k = 0,..., 2, the total regular cost in the (4k + 3) time interval (which is in an off phase and has length at most 7)) is less than 2y + ry.
84k+3 < 2 + n
(62)
For = x 1, we have
81z-1 7 +
(63)
Otherwise, there must exist a time in the off phase of Ejtz-1 such that PFSUM purchases Bahncard, leading to contradiction.
As result,
PFSUM (o; [Mj + TT)
(x (0+1))C 1)C (x= 1x
+ 1) + + 11 + By
OPT a [Pj, T))
xC (2 + 17)
(by 61. 62 and 63
(3-8)7 1
(64)
(1 B)n + Bq
The result follows from (60 and 64
A tight example for Proposition 4.8 is given in Figure 20 where = 1. The upper bound is achieved
when < 17 S 7, 81 = 85 0, 82 7 7,, 83 + 21/, and 84 = 7, or when 17 > 7/ 81 = 82 = 85
33 + 7 + 7. and 7.
27

---

on
off
time
My
T
Mo+1
+ T
1541 + +
-2
84
86
2g
7
(0 1 7)
0
+
7
(n > 7)
Figure 20: A tight example for Proposition purchased by OPT.
4.8 The shaded rectangle is the valid time of a Bahncard
A.6 Proof of Proposition 4.9
A.6.1 Non-Augmented Pattern VI Combined with Pattern II
Proposition Restated. If (i) OPT purchases a Bahncard at time ты in the off phase of some epoch Ep which expires in the same off phase, (ii) there is no Bahncard purchased by OPT expiring in the on phase of E, (j > 1). (iii) OPT purchases Bahncards (xr 2 1) in successive on phases starting from Ej. where for each
O, ...,"' x 1, the (k + 1)-th Bahncard has its purchasing time T++& falling in the on phase of E5+ and its expiry time T + T falling in the on phase of Ezt4+1, and (iv) OPT
does not purchase any new Bahncard in the on phase of Es then
PFSUM (o; [TH, Th + T) 155 + +))
2y+(2-8)m
0 05 S %
(1+91++Pg
(65)
(a: [Tk, Th + T) U (P), Py+x + T))
[1+0)++0p
(3-8)-+9
11 1> 7:
where the upper bound is tight (achievable) for any 2.
Proof. As shown in Figure 21 we divide [Tk. Th + T) U 11g. fi++ + T) into 4z + 2 time intervals, where each time interval starts and ends with the time when OPT or PFSUM purchases a Bahncard or Bahncard purchased by OPT or PFSUM expires. Let these intervals be indexed by -1, ..... 4r+
and let 8-1; ...: 84r+1 denote the total regular costs in these intervals respectively. By definition, is easy see that for each k = O.... I 1, the (4h + 3)-th time interval, i.e., [Wy+k + T, ((+*++1)
(which is an off phase), is shorter than 7 since it is within the valid time of a Bahncard purchased by OPT.
VI
on
on
Pj
Tas P5+1
T TF34 Ps
Bios Tor-1
time
Figure 21: Illustration for Appendix A.6.I The shaded rectangle is the valid time of a Bahncard purchased by OPT.
First, we observe that the cost ratio PFSUM [Tw, Th + T) U (1y (Mj:Mtta Ma+a + /OPT [Tk, Th T) U Wy5, + T)) is less than 1/8, as shown below:
1 PFSUM Ø; [TE, Tk + T) U [My, Mýtz + T))
3
OPT Tkk Tk + 7) [Mj Mitz + T))
(x+1)C + 8 8-1 + Σ k=0 $1 + S1443 + s1N+1) + Et=o 8AR+1
B 9POPT(P oi (Kk Tk + T) [1y Myto + T))
3 (r + ++111++ + 2 (8AR+1 + 84k+2 + 84K+44 + 84x+1 +8- + Exe 84k+3
B. OPOPP ai Th. T) Mijj:Hjt +T))
(xx + +1)C + + 3)
+ a + (1 - (B2) Σ S1k+1
8 OPT oi [Tk, Th + + [4 Mi+a + +())
28

---

> O. (since 0 S < 1)
Thus, the following inequality always holds:
PFSUM TK, Th T) U (Mgs My+x + +T)
1
(66)
OPT (o; [Tk, Tk + T) (ag, Mitt T))
3
Next, we analyze the upper bound the cost ratio. Note that by Lemma 4.3
we have
< 27 +
(67)
There two cases consider.
Case I. S 7 S y. By Corollary 3.2 for each k -O..., x the T-future-cost at Ti+ least 7, i.e.,
S4k+2 + S4k+3 + 84644 2 7.
(68)
By Lemma 4.2 we have
$1 + 32 7 1},
S4k + $4k+1 + 54k+2 27-11 for each I,... x 1,
(69)
S4x 84z+1 2 7 1).
Note that for each k 0..., 1. all the travel requests in the (4k + 2)-th and the (4k + 4)-th time intervals are reduced requests of both PFSUM and OPT. Thus. to maximize the cost ratio in [Tk, Tk + TT) U (uj.Hütz + +"), we should minimize $4k+2 and 844444 If they are greater than the cost ratio can be increased by decreasing 84k+2 or 84k+4 to y without violating (68) and 69 Thus, for the purpose of deriving an upper bound on the cost ratio, we can assume that
S4k+2 S 7:
(70)
84k+4 $ 7-
(71)
It follows from 70 and Lemma 4.4 that, for each i O,..., 1,
S S4k+2 + 81k43 + Sak+1 S 27 +
(72)
As result, we have
PFSUM o; [Tk, Th + T) U Mug U8+z T))
OPT (a: [TN, + T) U Mbi My+z + T))
(x + 1)C Σx k= (s1k+1 S48+2 + s1x+1) + 812+1 + + Ex=D 81843
(x 1)C + 3 8-1 + Ex (51442 +
S16+3 + $14+1) + Ex k== 81k+1
(x + +)C (27 +n) + 3 Σe=1 ($44+1+ S + -48+4) + S48411
Et= 84k+3
(by (67)
(x+1)C + 3 2g +1 + Ex=0 ($1422 84k+3 + s44+1) + Ei= S18+1
(x + 1)C'+ (27 +n) D. 81k+1 + Σズ
(41442 + S1k+3 + $16+1)
-(1-3)
x-1 (S1R+2 + s1k+1)
(x 1)C + 3 27 + + --
+ + S4H+44
+ + 844+1
(x + 1)C ΣE
K 84k+1 (x (1 Σ R=0 (Sak+2 84k+4)
(by (66) and 72
(x
Σx= $4k+1
(x+ (w+1)) 1)C + El 84441 + +x+ 3) Σm
(84k41 + 84842 + 84 + 848+1
(++ 30 1) + 17) + Σ 81k+1
(x [C+1JC+ Et 84k
(r 12 1))
(x + +1C + (( (2 + 77) + Σk $4k+1
29

---

(1- 3) (11 82) +2)
- S14+1 S14+ 514+2) + (ste S12+1)
(x+ + _ k= $4k+1
( + 1)0 + Ei= (0t - -1 (1- 111--100 () () 11)
(by (69
(xr [+1]C+
= 84k+1
(o + D)C + (x+ (1+1 + 1)(7-)))
(since
Σ
84k+1 2 0)
(++ 0 12)
k=
C (2 + 1)) - (7
C ((27 + n)
2y + (2-
(73)
(1 + 11 B1)
Case II. 17 >>7 7.. By Lemma 4.3 for each k = O,.... x - 1, the total regular cost in the (4k + 3) time interval (which is in an off phase and has length most T) is less than 2y + ny:
34k+3 2 + 1)-
(74)
On the other hand, the total regular cost in any time interval in an on phase is non-negative. As result, we have
PFSUM o;; [Tk, Th
Jug Mi+o + T))
+ 1)C (x 1)(2g 7)
OPT(a: [Th, + 72) U Jajs Mj+z + +))
x + 1)C' 3(x 1) +1)
(by (66). 67 and (74)
(3 3)7 +
(75)
(1 B) 311
The result follows from 73 and 75
A.6.2 Non-Augmented Pattern VI Combined with Pattern III
Proposition Restated. If OPT purchases x + 2 Bahncards (z 2 0) starting from the off phase of Et-1, where (i) the first Bahncard has its purchase time ты falling in the off phase of E;-1 and its expiry time Tk + T falling in the on phase of E,, (ii) for each p 1, ..... x. the (p + 1) Bahncard has its purchase time Tk-p falling in the on phase of Eitp-1 and its expiry time Tk+z + T falling in the phase of El+p. (iii) the (x + 2) Bahncard has its purchase time Tk+a+1 falling in the on phase of Ei and its expiry time + + T falling in the off phase of E142. and for some j 2 I and i > k, OPT purchases y Bahneards (y > 0) in successive on phases starting from Ef+z+1, where for each p = 0,....y - 1, the (p + 1)-th Bahncard has its purchasing time Ti+x+p+2 falling in the on phase of F-z+2-p+1 and its expiry time Ti++tpt2 T falling in the phase of Ee+ztp+2. and (v) OPT does not purchase any new Bahncard in the on phase of +j+2+v+1, then
PFSUM (o; [Ts, Tktz+1 + +7) (pssttt + +T))
2y+(2-0)
0 1 S 7
[1+
OPT (a: [Tk, Tktat1 + T) U (ytttt T))
[1+9)++9
(3 13-81xin
1 7
(76)
Proof. As shown in Figure 22 we divide [Tk, T T)
into 4(z+t)++ +6
time intervals, where each time intervals starts and ends with the time when OPT or PFSUM purchases a Bahncard or a Bahncard purchased by OPT or PFSUM expires. The first 4x + 5 time intervals, from time т; to T++++1 1 + T, are concerned time duration of Pattern III. The total regular costs in these intervals are denoted by 8-1, 80, 81, 84z+3, respectively.
MMj++++ + T) the concerned interval of Pattern VI, which divided into 4y + time intervals. The total regular costs in these intervals are denoted by Q1 ..., 44y+1, respectively.
For ease of notation, introduce 02 := 54k42 + 541+3 + 54844, and dR = 04R+2 + 44843 9ac++4- First, we observe that the cost ratio PFSUM(a; [Tk, Te+z+1 + T) U [W5+241. Pj+a+v+1
T)) /PP((a: (Tk, Tk-a+1 T)) U [ms+æ41, My40+2+1 + T)) is less than 1/8, as shown below:
30

---

off
08
off
off
o0
off
08
off
00
off
08
off
on
time
Pt
1212 Pa
Th
Tob++y- Pymreyel
8-1
9az-3
04x+1
Figure 22: Illustration for Appendix A.6.2 purchased by OPT.
The shaded rectangle is the valid time of a Bahncard
1 PFSUM (i; Tke Tk+r++1 T) CUu0U1gttain [1tttth + 7))
OPT(a;
+ 7) TT:t
T1+z++
[1j+z+1; Mjta +7)
(x 22C + 8-1 + + 842+2 + 84 + Σx=o 0g
3 OPT σi [Tk: Th+o+1 F) [1y+++1111100 1 #5+z+u++ + T)
2 Lk n 84k+1 + +4 +CC > 83 + >ソ 0 44h+1
OPPT 0; Th. + + T) 11++++1 My+o+y+++++ + T)
(x 1)C + ビ k= Sak + Sck+1 S42+2) + -k= S4K+3 + Stm+4
B
OPOPT( σi Tk: Tktr+1 + T) M1tt++++ M1 ++++++ + +T)
(u + +1C + 3 Σx=0 (148.1 + 948+2 + 944+44 + 14y+ + Ek-1 948+3
B
B OPOPT 0 [Tky T 7) [1tt+
+ +T)
(1 (1-3)(x + 2) + 3(1 B) xi 814-2 + En San) + (1 - 32) Ek= 94K+1
OPT 0: [ki Thtz+1
|1+++11 Mytot +T)
8(1 - 3) k=0 91k+2 + Σk= (sk+1) (1 - B2) Ex 4oh+1
+
3. OPO 0 (Tk Th+
- () + y + 2)C
(since 0 0,B<1 0)
3 OPT [Tk, Tkta+1 + T) U |1ttot1 Mitzzu+1 +T)
0.
Thus, the following inequality always holds:
PFSUM(a: [Te, Th+ T) (BD00[a+++Hii [f + +T))
1
(77)
OPT (o; [Tk: Tk+a+1 + T) U [1j4a+1 #j+z4y41 T))
3
Case 1.0 1 7. By Corollary 3.2 the T-future-cost Tep least 7, i.e.
2 7 $_5 8-4 8_4
8-2 + 8-1 2
(78)
848+2 + 84k 84k44 2 7
for each ...,, 1, for each 0, ...; 1.
44642 + 44843 + 446+4 2 7
By Lemma 4.2
we have
84k + 84k+1 2 7 -1 for each ks 0, 1,..,,
@1 + 7 - 17
(79)
01g + 41++1 ? 17
+ 91k+1 + 94k+2 27 for each k = 1, 1.., 1.
Note that for Pattern III, all the travel requests in the (4k 2)-th (for & = 0. .......)) ar) and the (4k+ 4) (for l: -1 1,..., x - 1) time intervals are reduced requests both PFSUM and OPT, similar for Pattern VI. Thus, to maximize the cost ratio in [Tk. Th+a+1 + T) U [Mo+a+1 Mstotot1 + T'),
31

---

should minimize these $1k+2's, 's, $ak+4's, 's, 94k+2's, s, and qak+1's. If they are greater than 7, the cost ratio can be increased by decreasing $ak+2 or $4k++4 to y without violating (78) and (79). Thus, for the purpose of deriving an upper bound on the cost ratio, we can assume that
84k+2 S 7
for each k = 0 0,.,, 3
S1k+4 S Y
for each k
...y I 1,
(80)
dik+2 S
for each k = 0, 0..,, 1,
91k+41 S 7
for each k 0 0.... y L.
follows from and Lemma 4.4 that,
8 + 50 5 27 + 7)
Sar+2 542+3 S 2y + 13
(81)
+ 0% = Sak+2 + $46+3 + Sck+1 S 2
for each k: = 0, ..... 20 1, for each & 0..,, y 1.
6% 9ak+2 91b43 + q1k+1 2 +
As result, we have
PFSUM (o; [T: Tktz+1 + 7) U W5ttzi;1/y=attt + TT)
(PT [T, Tk+z+1 +T) U |1 +T)
(x + I)C + 8-1 + 80 + 84x-2 + 84r+3
k=0 0k + > 8ck+1 - (1- (54h + 84k+1 + 84k+2)
22C + 3 8-1 50 84242 + 4. 2k= 0z + = + yC 1 8x Ex 946+1
( + + + Ex= 91k+11 Σx 8k (1 3)
91 + 92
+ +ig + 9iy+1 + Σk=l + 91u+1 + 910-22)
(x 2]C + 8
8-1 50 $1x+2 + $12+3 Σk=0
0z: + + k= S1k+1 yC 8 3 8x + Σ 91k+1
(x + 1)(1 - B)m + 8-1 + 80 847+2 + 84 + Ek= 84k+1 + Ek 0z.
(o 22C 8
8-1 + s0 + 81x+2 $1m+3 + k== S4R+1
k= 02
+ yy + B >
òr + Σ 91k+1
(u + 3)n +
6x + Σ Ik=n l1k+1
+ 22C + 8
8-1 50 + S + 51z+3
2k=0 S4k+1
k== 0k
+yC + 3 >5 8R + KK= PAR+1
(by 779
(x + 1)(1 + 81z+2 + Sto+3 +
Ek= Og (y +1((1 B)n + Σ 2k= òR
- s0 S12+2 + Sto43
Ik=o
0k) + +C + + >k=0 6R
(since
Σ
84k+1 2 0, Σ
g4h+1 2 0)
k=U
k=
(x+++2))1-0)) (8-1 + 81442 + 81 + 8-
0g) + Σ
k=
(x ( Stm+2 + 81z-3 k= (=+==)]l--))+(=t++++2 +7) (by
02 + BB Σ Σx 8z.
and 81
(1 27
C C+ +))
27 + (2- B)n
(82)
(1 + 8)y + Bn
Case II. n - .r) time interval (whichip is in an off phase and has length at most T) is less than 2 + similar for Pattern VI. Thus have
y. By Lemma 4.3 for Pattern III. the total regular cost in the (4k 3) (for
84k+3 < 27 + n
for each & - ..... I, for each k = 0, 1,.... y 1.
(83)
4ak+3 < 27 +
32

---

On the other hand, the total regular cost in any time interval in an on phase is non-negative, so it can be minimized to zero. As result, we have
PFSUM σ; [Tk Th+2+1 + T) - +))
OPT σ3 The Tk+x+1 + +) U (pjtstt + T))
(x + 1)C + Σ 848+3 (y 1)C + Σk 94K+3
+ 8 8- + ( 8443 + + > Q4k-3
(x (=+)) y(27 + 1)
(by 77 and
20+2 By(2 +n)
(z +
(3 +1
(84)
(1 + B)7 + 3m
The result follows from
82 and
84
A.7 Proof of Proposition 4.10
A.7.1 Non-Augmented Pattern VI Combined with Pattern
Proposition Restated. If (i) OPT purchases Bahncard at time at the beginning of Er, i.e.,
The = μ4, (ii) there is no Bahncard purchased by OPT expiring in the on phase of E, (1 j), (iii) OPT purchases Bahncards (x: 1) in successive on phases starting from Ej. where for each k= 0..,, 2 1, the (A: + 1)-th Bahncard has purchasing time Ti+& falling the on phase of E and its expiry time T + T falling in the phase of Ef+x+1, and (iv) OPT does not purchase any new Bahncard in the on phase of Es+a. then
PFSUM (a: Th + T) U (8, + +T) (PT [Te, Tk + 7)) U (Py, My+0 + T))
(2-
05 7
<
(1+D)++0n
(3-8)-+0
(85)
[1+3)++8n
1> 7:
where the upper bound is irrelevant with x.
Proof. As shown in Figure 23 we divide [Tx. Tk + T) [u Mito + T)) into 4z + 2 time intervals, where each time interval starts and ends with the time when OPT or PFSUM purchases a Bahncard or Bahncard purchased by OPT PFSUM expires. Let these intervals be indexed by 1, 1, 4x++,
and let 8 8-1; -1...., Sts+1 denote the total regular costs these intervals respectively. By definition, is easy see that for each k 0, ..., I 1, the (4k + 3)-th time interval, i.c., [My+* + T' ((+k+1)
(which is an off phase), is shorter than 7 since it is within the valid time of a Bahncard purchased by OPT.
VI
off
off
off
off
time
7((m)
T
15
T1
B1
P 13
P/+1
P1422 Bi-a-1
+ Psta Tia--
Psta
Figure 23: Illustration for Appendix A.7.1 The shaded rectangle is the valid time of a Bahncard purchased by OPT.
First, we observe that the cost ratio PFSUM [Tk, Th + U [py T) U fyt, + T)) is less than 1/3, as shown below:
My+x (yj: T)) /OPT [Tk, Th
1 PFSUM (o; [TK, Th + +T) (u4s [4js + 7))
8 OPT ai [Th. Fk + U [uy Mita + T))
33

---

+ 1)C 8-1 2k=0 S18+2 + 81k+3 91++1) + =Ez= 81k+1
OPT [hk + T) (1 Mi+t T)))
8 (xx [x++)C 8-1 Ek= 84k+11 + 84k+2 +4k+4) ) 84x+1
k== 84
B. S.OPT [T. + M3: T)))
(z=8)(z++ + 1)C BC 8(1 8) 8-1 Σ k= ($4N+2 + s48++)
+ + E 84k+1
OPT 0i Th, Th + 7) U [ugi Hijo +)))
- (1-8)(x + 1)C + (1 - B3 Σ (84x+2 + s4x+a) + (1 - 82 Ek=o 84k+1
(since 8-1 ?)
8 OPT [Tx, Th + (pr + +))) (since s 1)
Thus, the following inequality always holds:
PFSUM (o: [Te, Th + +T) [1g Mj+z + +T))
1
(86)
OPT
(o; [Tk Tk + +) U [pgs Pita T)) 3
There are two cases to consider.
Case I. < S y. By Corollary 3.2 for each k = -...., xt 1, the T-future-cost at Tit. is at least
7, i.e.,
84k+2 + 84k-3 84k+4 7-
(87)
By Lemma 4.2 we have
8-1 2
51 + $2 2 7 1),
(88)
54 + 84 + 94k+2 2Y 84z 84r+1 2 7 17.
for each k = I,..., 1,
Note that for each = 0, ...,. 1, all the travel requests in the (4k + 2)-th and the (4k + 4)-th time intervals are reduced requests of both PFSUM and OPT. Thus, maximize the cost ratio in [Tk, Th + T U [uy, Mj+z + 2"), we should minimize 54k42 and 84k444. If they are greater than 7, the cost ratio can be increased by decreasing $ak+2 84444 y without violating (87) and (8 Thus, for the purpose of deriving an upper bound on the cost ratio, we can assume that
81k+2 S ?
(89)
84k+4 S 7.
(90)
follows from
89
990 and Lemma 4.4 that, for each = 0,.... x 1,
$4k42 + 81k43 + S1R+1 S 27 +
(91)
As result, have
PFSUM(a: (T; Tu T) 14 T))
(PT(a: [TK, + 7) U Mjt + T))
(x (2
+ k=0 (84241 + 848+2 + 844-44 + s4nt1
Σx=o 84643
(x+ I)C + 3 8-1 + Σr (848 + 84843 8 + 84414) + > 84K+1
(x 2)C + 8 r Σx= (S + san+a) + $
+ k= S4R+3
x--1
(by 88
( + 1)C
(80842 8144 + s1k+1)
+ Ex=o 81k+1
34

---

(x (x+ + By + L 84k + >B 884242 + 842+33 + 844 1) (1 - (1-8) Ex= (841-42 + 8444444
(x+ + 3 ( Σk=o (84R-42 + 84k++3 + 84k+4)
+ Ek= 84k+11
(1 (++2)C++ + By + B k== 84h + -1 3) Σ k=u (848+22 + 84k+4)
(by (66) and (91)
(x + I)C + 3 x
k== $4R+1
(x + +)) + By + Ek 14++1 + x2) (1 3) Ex (s48+1 + 34R42 + SAK+4) + S48+1
+ ( (
k= S4k+1
2) + Σ 84k + 22 +n)
(o 1)C + B x22 1)) k== S4k+1
(1- 3) [3)3 82) E (akk S1k+1 S1k+1+
+ S s1k+2) + (SLE S14+1)
(x+ 1)C + + 1)) Ek= k=0 84k+1
(x + 2)C + 87 + " S4++1 + - (x + 1)(7 -1)
(by 88
(x +
+ -k= 84k+11
(x + 2)C + By + (2)+ () + 1)(x - (n) (since Σ
84k+1 2 0)
+ 7))
k=
(27 + (2 B))) + (7 + (1 (1-8)m 9)n)
x((1 + B) + 3n) +7
2ry + (2 - -B)n
(since a 2 1)
(92)
(1 + B)y + Bm)
Case II. 77 > y. By Lemma 4.3 for each h: = o,..., - 1, the total regular cost in the (41: + 3)-th time interval (which is in an off phase and has length at most 7') is less than 2y + Ty:
84k+3 < 2 + +
(93)
On the other hand, the total regular cost in any time interval in an on phase is non-negative, except for 8-1, which is at least 7:
8-1 277
(94)
As result, we have
PFSUM((; [TK, Tk + +T) (Kg-Ptt + T))
(x + 22+ By+ x(27 + 7) (x (IC + (7 + x(27 + 7))
OPT(a; (TA, + T) U Juy Mij/ T)))
(by (86) 933 and 94
x xCC 2y + n) + (C
z(C + (2g +)) +y
(3 (3-8)7++ +
(since x 2 1)
(95)
(1 + B)y + 8n
The result follows from 92 and 95
A.7.2 Non-Augmented Pattern VI Combined with Pattern IV
Proposition Restated. If OPT purchases x + Bahncards (z 2 0) starting from the off phase of Ei-1, where (i) the first Bahneard has its purchase time тę falling in the off phase of E and its expiry time тı + T falling in the on phase of E,, (ii) for each p 1..... the (p 1)-th Bahncard has its purchase time Tk+p falling the on phase of Extp-1 and its expiry time Tk+p + T falling the
on phase of Expp. and for some 2 1 and > k, OPT purchases y Bahncards (y 2 0) in successive on phases starting from Ef+z+1, where for each p = 0, ..., y - 1, the (p + 1)-th Bahncard has its purchasing time T++atp+1 falling in the on phase of Ef+z-p+1 and its expiry time T4+++p11 + T
35

---

falling in the on phase of Ej+x+p+2, and (v) OPT does not purchase any new Bahncard in the on phase of +j+++ then
PFSUM o:; [Tk; (++++1) || +T)) 7))
2x+
0 ns
(1+0)y+3
(96)
OPT( /4+2 + 7) U |Httat + 7))
[1+8)7+38
13-99)9t
17 1/?
where the upper bound is tight (achievable) for any 2.
Proof. As shown in Figure 24 divide [Tk, M+++++) U [1t+++11 /5 + T) into 4(x + y) + +5 time intervals, where each time intervals starts and ends with the time when OPT or PFSUM purchases Bahncard or Bahncard purchased by OPT PFSUM expires. The first 4x + time intervals, from time Ti to Mj+z + ', are concerned time duration of Pattern IV. The (4x + 4)-th interval is the off phase jut+ +T, ). The total regular costs in these time intervals are denoted by 8-1, So. $1...., $1z-1, $1=+2, respectively. [15+=+1+ M++x+y+1 + T) is the concerned interval of Pattern VI, which is divided into 4y time intervals. The total regular costs in these intervals are denoted by Q1, ... 91 respectively.
IV
VI
off
on
off
on
off
on
on
off
on
off
on
on
time
Miei
prazel
Mges- 1eee M144+22 Trea-2
Py
Six 8kz
Tap
Figure 24: Illustration for Appendix A.7.2 purchased by OPT.
The shaded rectangle is the valid time of a Bahncard
According Proposition 4.10 In IV of (9) the total cost of travel requests in the last phase of Pattern IV and the following off phase is at least y. Thus we have
c(;; [u+z: #1+z+1) 8Ax + S1x+1 + S1x+2 27
(97)
First, we observe that the cost ratio PFSUM a;; [The M1+++1) U [ Pj+++u+1 /PPT [Tk, M4+++1) (ijtott + T)) is less than 1/3, as shown below:
1 PFSUM (o; (T, M 1=++11 ( + T")
3
OPT((: [Te M1+++1) M Mo T))
(x + 1)C + B 8-1 + 80 + k= 848 84843 - 648+4) + Ex-n 848+1 + 84x42
B. OPT (Tx,
1++++1) [1itot1, + T))
VC + Σ (444+2 + 44 + 948++4) Ek 94k+1
+
3. OPT (a; (Te, M++++1) U | T))
(x+ 1)C'+ + Ek Sst + S4N+1 84842) (s1z + s10+1) -k=-1
S1R+3 + S1x+2
8
B. OPT [Ts, U ( (ittoti, yt1 + +T))]
(v+ I)C + 3 Ex= (gax+1 + 04k42 + gAR+4) + g4y+1 + Σk-1 94K+3
8.
8 |PTT (Th, (1+2+1))) U [Mitott, + +T))
(x + (x+1)(1 -3 + (1
() 84k+2 Etzo 84k) B2)
Ek=u 84k+1 (1 - -3)sa442
3. OPT (o; [Th (14441) U (15+z+11 15 + +T))
y Blx -(++1) 3(1 3)
+ 906+1) + (1- B2) EVe Psk+1 + (1 8)812+2
8. OPT (o; (The M4++1) U (1542+11 Matztut + +T))
36

---

xx y1 8) 3)+ (1 23) C (01-:(111110 8)51z (1 ( sto+1 (1 B)5
8. SPTPP (o: [Tk, M+++11 (+xx11)11 [1++++1 | + +T)
(x v) B) (1- 220 C B(1 (542 84x+1 84x+2)
(since 0 S 8 < 1)
8 OPT (o; [T: [Tx. [ +2))
(1 v)(1 B) + (1 23) C 3(1 B)y
(by (97)
8 OPT((: oo; [Tk. 11+2+11 ( +T) (s + m) (1
8. (PT oo: [Tk | T))
0. (since B 1,
Thus, the following inequality always holds:
PFSUM or; [Tk, (142-12211 (aspsss)))(((attt11e1 (p542t1 + +7)
1
(98)
OPT a;; [Th, #1+x+1) U (M My40+++1 T))
Case I. 1 $ 7. By Corollary 3.2 the T-future-cost T444+1 at least 7/ i.c..
8-1 + 80 2 Y
S4k+2 + Sak+3 + $4k+4 27 for each k = 0,..., 1,
(99)
lak+2 + 9ak+3 + 91k+4 2
for each 0, ...
By Lemma 4.2 2
have
Sik 81k+1 + S1k+2 27 for each i: 0,.., 1.
Siz + S1++1 27 -17-
@ (2 2 17;
(100)
(ak + 44k+1 + 44k+2 27
for each h = 1,...,... 1,
Q4y 44y+1 27 17-
Note that for Pattern IV, all the travel requests in the 24tth) and the (4k++4)-thh (for k: .... x- 1) time intervals are reduced requests of both PFSUM and OPT, similar for Pattern VI. Thus, to maximize the cost ratio [Tx Pt+z 7') U Mo T'), we should minimize these 84842's 's and 44444's s. If they are greater than the cost ratio can be increased by decreasing 84 or 84k44 to y without violating (99) and (T0)). Thus, for the purpose of deriving upper bound on the cost ratio, we can assume that
S1k+2 S Y
for each 0, ..., T,
$Ak+1 S
for each k = - 1,
1,
(101)
44k+2 S 7
for each 0...., !) 1, for each i = -..... 1.
44k++4 S ?
follows from
101 and Lemma 4.4 that,
8-1 8p 27 + ?)
84k42 + 84R43 + 84K-4 < 2y + +n
for each A: = 0, ..... x 1 for each & 0, ..., y
(102)
44k+2 + 44k43 44k44 5 2- + 1)
As result, we have
37

---

PFSUM M | U| + +T))
OPT Mc+++) Ho
(x + +) + 2 0x + B > S4k+1 + 84242 - (1 (3) (3) 2x (S4x + (44-22 + 84
(x+ 3(s_1 s0 2k=0 0k) + Σk= Stk+1 + S1z+2 + yC + 3 Σk= Oz - Σx= Pok++1
+++1)++++ 1 + yリ1 0g - (1 - 3) E (04h +4 + 94M+44 + 94y++
(IC + ((- 50 + Σ k=0 0x) + Σ k=0 1 + yC + B Σ k= 62 + Σ P4k+11
+++1)+((--111 + Σ 02 + + Σ 84 (1 - 3) Σ ($4R + 842+2) + 842
(x (x+ 3(--1 90 Ex 0x) + Ek= 84k+1 + yC + 3 Ex=0 6% + Ek=o 44k+1
(++1)C++ -++10+E*= 71k+1 + Ek=o 0g - (1 (3) E (0+++1 + 01R+2 + (AR+1) + 91++1
(++ + ((- + 5o + Ex=0 0%) + Σ k=0 Sck+1 + +C + B Σx 6% + Σ Pak+1
(since 84242 2 0)
+ ( - (1 - 3) Ek=0 (ssk + S + S1K-2) + ($12 + (1ut1)
(x+ 1jC 0 1) + A= S4k+1 + yC + By + 11) Σk= 9sk+1
(1+1)C Ex=0 94 + y + (1 3) 91 + 92 + Σ (94k + 94k++1 + g4k+2) 94y + 94y+1
( + 3(r 1) Ex k= 84R+1 + yC + By + 11) + >x 448+1
(by (88 and T02)
84k+1 (1 B) x0(7 [x(7 - 1) +7
8y (
(x + 1)C 12)
+
84841
yC +CC
11 + Σ Ex=o 91k+1
ox +) $4-0 yc + By(27 + +n) + +K 9ak+1
(1 () + +1)(7 7)
[I++
(by
and 100)
a 2 (x
(1 - 8) (I + y 2)n - (x + y 1im
( (xx + (2 + m)
y 84k+1 0,
(since
44k+1 0)
k=
k=
2(x +y 1)7 + (x + y 1)(2 B)n
(++ 1) (1 + B3n + Bm)
2-y + Bm
(103)
(1 + 3)y + 3m
Case II. n 7. By Lemma 4.3 for Pattern IV, the total regular cost in the (4k + 3)-th (for = .... x) time interval (which is in an off phase and has length at most T) is less than 27 + n, similar for Pattern VI. Thus we have
{
84k+3 < 27 + n 04k+3 < 2 + 7
for each i -1,..,, x 1, for each i = 0,..., y 1.
(104)
On the other hand, the total regular cost in any time interval in an on phase is non-negative, so can be minimized to zero, except the last on phase of Pattern IV. As result, we have
38

---

PFSUM a; Tk. 11=2+1) ( ( +T)
OPT oz; [kss M+++++1) (btta
( + 7))
(x 1JC + -k= 84k+3 84--1 884r + (y + 1)C - 44k++3
84x) - yC + Σ 44k++
(x (=- Bg
(by 97 and 104
(x (++==3(+(2++++)))++++++ (8 1)7
(+++++)](++((++++++]+)+++++++++
(x (=++=+)](+++++=++)))))))
- +
(105)
(1 8)7 Sr..
The result follows from 103 and 1055
A.8 More Experimental Results and Discussions
For commuters, Figures 25 to 30 demonstrate the performance of various algorithms under different settings of B, C, and T. Additionally, with the practical significance of these parameters mind, we increase C' decrease T' when / is reduced. In Figure 26 where C is exceptionally high, PFSUM, SUM and SUM all tend towards not purchasing Bahncards. However, in this scenario, FSUM's competitive ratio escalates due to its complete reliance on predictions with large errors.
Additional results for occasional travelers are presented in Figures 28 to 30 These figures exhibit consistent pattern, with PFSUM demonstrating its consistency in scenarios of small prediction error. Furthermore, PFSUM proves its robustness in cases of extremely large prediction errors, particularly evident in Figure 30 Here, while all other prediction-incororaaa algorithms have competitive ratios
of approximately 1.2 higher, PFSUM consistently maintains competitive ratio of less than 1.1.
1.25
Average cost ratio
1.25
Average cost ratio
1,20
1.15
1.15
1.33
Average
3.10
1.30
(1
1.05
1.08
1.00
0.0
0.2
0.6
0.8
Perturbing probability
Perturbing probability
Perturbing probability
(a) Commuters (U)
(b) Commuters (N)
(c) Commuters (P)
Figure 25: The cost ratios for commuters (3 0.6, T 10, C 200). "U", "N" and "P" represents Uniform, Normal and Pareto ticket price distributions respectively.
39

---

Average cost rabi
1.04
Averagee cosl rabo
1.03
FSUM
SUM
SLM,
1.02
1.02
FFSUM
POLAji-11
1.00
Average
POLAj--0.3)
0.98
PELAS-0
0.96
SRL--021
Perturbing probability
Perturbiing probability
Perturbing probability
(a) Commuters (U)
(b) Commuters (N)
(c) Commuters (P)
Figure 26: The cost ratios for commuters (3 0.6, T 10, 2000). "U", "N" and "P" represents
Uniform, Normal and Pareto ticket price distributions respectively.
1.8
SUM
ratio
1.5
Average cost ratio
ISUM
1.4
PF3UM
SUM.
Average
1.3
FOLA21003)
P0144-002)
FOLA01-11
111
SRL
Perturbing probability
Perturbing probability
Perturbing probability
(a) Commuters (U)
(b) Commuters (N)
(c) Commuters (P)
Figure The cost ratios for commuters (B 0.2, 7= 10, C= 400). "U", "N" and "p" represents Uniform, Normal and Pareto ticket price distributions respectively.
1.4
Average cost ratio
1.30
FSUM
1.3
1.25
SUM.
12
3.2
Average cost
1.20
FFBUM
POLAG111
10LA)1-05)
Average
POLAG-022
501)1-22)
1.00
Perturbing probability
Perturbing probability
Perturbing probability
(a) Occas. travelers (U) (b) Occas. travelers (N)
(c) Occas, travelers (P)
Figure 28: The cost ratios for occasional travelers (3 0.6, = 10, 200). "U", "N" and "p" represents Uniform, Normal and Pareto ticket price distributions respectively.
Average cost rabo
1.04-
Averate tost ralo
FSUM
SUM
1.02
1.00
FFUUM
SLM,
1.00
1.03
PCLA--11
0.58
Average
1.02
SALD=11
PSI (1-
0.96
SHLU-0.1
Perturbing probability
Perturbing probability
Perturbing probability
(a) Occas. travelers (U)
(b) Occas. travelers (N)
(c) Occas, travelers (P)
Figure 29: The cost ratios for occasional travelers (3 = 0.6, 7 10, C 2000). "U", "N" and "p" represents Uniform, Normal and Pareto ticket price distributions respectively.
40

---

1.8
Average cost ratio
FSUM
2.6
Averege
1.4
Average
POL44-02)
POLA/-035)
1.2
5185--11
SRL3-05)
1.0
S(())=02)
0.0
0.2
0.4
08
0.5
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.0
1.0
Perturbing probability
Perturbing probability
Perturbing probsbility
Occas. travelers (U)
(b) Occas. travelers (N)
(c) Occas. travelers (P)
Figure 30: The cost ratios for occasional travelers (3 = 0.2, 7 = 10, = 400). "U", "N" and "p" represents Uniform, Normal and Pareto ticket price distributions respectively.
41

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly state the contributions made, matching both theoretical and experimental results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [No]
Justification: This paper provides both theoretical and experimental contributions for PF- SUM. The theoretical results are derived without strong assumptions, but the experimental results are conducted, although extensively, only on synthesized dataset. Different travel request patterns may influence the advantage of PFSUM over the other algorithms.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
42

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
All the propositions, lemmas. theorems and formulas in the paper are numbered, cross-referenced, and proved. The proof sketches are provided in the main content while the detailed proof' are given in the appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We have released the code and data for reproducibility. With our instructions, others can easily reproduce experimental results that are consistent with the results in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
43

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: The code and data be openly accessed. We provide the instructions reproduce all the experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ mtipss.c/publlic//
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The experimental settings are presented in the experiment section and the details are provided with the code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The statistical significance involved in our experiments is divided into two parts: data generation and confidence intervals for the results. For data generation, we have given their distributions well as parameters, and specific methods of generation in the
44

---

paper. Additionally, for the results, we have given 95% confidence intervals for all results of 100 experiments through the shaded area the figures.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide sufficient information on the computer resources for the experi- ments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: We have reviewed the NeurlPS Code of Ethics, and we confirm that the research conducted conforms with the NeurlPS Code of Ethics in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- cration due to laws or regulations their jurisdiction).
10. Broader Impacts
45

---

Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: This paper presents work to design, analyze and evaluate
algorithms for the Bahncard problem. There are some positive potential societal conse- quences of our work. For example, saving the cost of travelers. But none of them feel must be specifically highlighted.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologics that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e-g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
46

---

Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We have provided details of the code in anonymized manner.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
47

---

Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
48


Reviews:
[{"review_id": "XZuvEtokQh", "reviewer": "Reviewer_m14s", "summary": "In this paper, the authors provide a learning-augmented approach for solving the Bahncard problem, which is a generalization of the ski-rental problem. The authors provide theoretical guarantees for the consistency and robustness of the proposed algorithm PFSUM, which measures the performance of the proposed method compared to an optimal offline method for different levels of prediction error in learning augmentation. The paper also provides empirical results of the proposed method and a comparison with existing methods, which validate the proposed method.", "questions": "Please see the Weaknesses.", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper proposes learning augmentation for the Bahncard problem with theoretical guarantees, which seems novel in the related literature.\n* The proposed method is introduced in a methodical way which helps understand the motivation and intuition behind the method.\n* The paper provides convincing theoretical and empirical results that validate the proposed method.", "weaknesses": "* There seems to be a gap between the theoretical result for robustness and the empirical results in the paper. Specifically, when $\\beta$ is very small (i.e. when the discount is larger), the bound for competitive ratio tends to be very large. However, the empirical results show that the cost ratio is close to 1 ( as shown in Figure 29, for example). Is there an intuitive reason for this gap?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer m14s, we are immensely grateful for your positive comments! Below is our response to the weakness.\n\n### **Weakness**\nWe 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.\n* **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).\n* **Competitive ratio:** the **worst-case** cost ratio across **all possible** inputs, comparing an online algorithm with the offline optimum.\n* **Robustness:** an upper bound of the competitive ratio across **all possible** prediction errors.\n**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.\n\nFurthermore, 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$. \n\nIn 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZQkABDBkii", "reviewer": "Reviewer_AGsA", "summary": "In this paper, the authors investigate the Bahncard problem in the learning-augmented context. The Bahncard problem is a generalization of ski rental, originating from the railway pass of the German railway company of the same name, where an algorithm must choose between a cheap short-term solution (purchaing railway fare at full price) or an expensive long-term solution (purchasing a Bahncard to receive a discount on all future fares for a set period). Previous works have studied the Bahncard problem extensively in the non-learning-augmented setting, and in the learning-augmented setting by formulating the Bahncard problem as a linear program and applying the primal-dual framework for approximately solving LPs. The authors contribute by proposing an algorithm using the problem structure of the Bahncard problem, independent of the primal-dual framework, that can handle fractional and non-uniform inputs, and utilizes short-term predictions as opposed to an advice on the entire sequence of travels.\n\nFormally, the authors consider problem instances where a series of travel requests arrive at time $t_i$ with ticket price $p_i$. An algorithm can either choose to buy the ticket in full price, or purchase a Bahncard with price $C$, that is valid for a time period of length $T$, and discounts all purchase while valid by a multiplicative factor of $0 \\leq \\beta \\leq 1$. The author's proposed algorithm, PFSUM, is $2/(1+\\beta)$-consistent (the competitive ratio when the prediction is accurate) and $1/\\beta$-robust (the competitive ratio upper bound with arbitrarily inaccurate prediction).\n\nPFSUM is a very intuitively simple algorithm, that builds upon previous ideas. On a high level, the algorithm examines both the requests that arrived in the past $T$ time period, as well as the predicted requests that will arrive in the next $T$ time period. If the total cost of both the past and the future time period is larger than a certain parameter, the algorithm purchases a Bahncard. The proof strategy divides the algorithm's execution into phases, and bounds the ratio between PFSUM's solution cost and the optimal solution cost for each phase, depending on how the Bahncard purchases overlap between the two solutions.", "questions": "As stated above, I would like to understand the logic behind Proposition 4.6 in more detail, which I believe is important yet non-trivial enough to be explicitly shown in the main corpus.\n\nA few minor questions/suggestions/comments:\n- Line 169-172, Section 4.3: The argument behind SUM's success might be more suitable in an earlier section, to help the readers understand both Section 4.1 and 4.2 better.\n- Line 188: The definition of the prediction error only concerns the sum of the cost of requests. Is it possible to obtain better bounds and results using a more \"fine-grained\" error function? This might be an interesting future direction if feasible.\n- Line 203, Lemma 4.4: The statement and the figure together slightly confuses me - what if the time interval $[t, t+T)$ does not intersect on phases on both sides? Intuitively the same result should hold with $s_2 = s_4 = 0$, but it is not made explicit by either the lemma statement or the figure.\n- Line 221-222, text of Figure 2: \"...$x$ can be any non-negative **integers**.\" It should be **integer**?\n- Line 252, Proposition 4.8: The definitions seem to suggest that there should be no regular requests during an on phase, so what is the logic behind the proposition statement? Are the regular cost and the on phase referencing different algorithms?", "limitations": "The authors discuss their limitations properly in the introduction and the conclusion sections. No ethical concerns are applicable.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Overall the paper is very well-written and addresses a theoretically and practically interesting problem in the context of learning-augmented algorithms, improving on previous solutions. The results yield significant improvements over prior works on the same problem, by specializing and utilizing the problem structure, and the model (advice, performance) chosen by the author are natural and reasonably practical. The algorithms and high-level ideas presented are simple and intuitive, and while the detailed proofs are quite involved, they are presented in a fashion that is easy to follow and understand, which I believe is an important characteristic of a good paper, especially for a widely attended conference such as NeurIPS.\n\nIn particular, I appreciate the author's explanation of various initial attempts based on prior works in Section 4: I can easily follow the development of their algorithm from simple preliminary ideas inspired by existing literature, and understand why these naive algorithms does not provide satisfactory bounds, and what led the authors to make improvements and modifications to derive the eventual PFSUM algorithm. Apart from this, the theorems and technical claims are also introduced in sufficient context for me to understand what role does each claim play in the overall structure of proofs and logic. The various figures used by the authors to illustrate definitions and ideas are also much appreciated.", "weaknesses": "I do not have much major complaints about the paper. One particular issue is that I am not certain how the conclusion of Proposition 4.6 on page 6 is trivial: while I agree the numerator is upper bounded by Lemma 4.3, I do not see an obvious lower bound on the cost of the optimal solution in the denominator, for which Lemma 4.3 only implies an upper bound. A quick delve into the appendices seems to provide traces of arguments supporting $OPT(*) \\geq (1+\\beta) \\gamma + \\beta \\eta$, so I am inclined to trust the soundness of the author's claims, but I believe that this is important enough an argument to be made explicit in the main corpus.\n\nI am recommending a weak accept as an initial score, but can be convinced by clarifications from the authors to raise the score to accept.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n### **Weakness**\nWe 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.\n\n*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}$.\n\n### **Question 1**\nThank you for your extensive review. We will follow your suggestion to add more description to Section 4.1 to help readers to understand.\n\n### **Question 2**\nWe 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.\n\n### **Question 3**\nYour 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.\n\n### **Question 4**\nThanks for pointing out this. You are right, we made a typo here. $x$ should be an integer.\n\n### **Question 5**\nThanks 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "q6RmAol6xD", "reviewer": "Reviewer_ZK3p", "summary": "This work studies the Bahncard Problem and proposes a new learning-augmented algorithm, PFSUM. The writing of the paper is clear and easy to follow. The work also provides detailed mathematical proofs for six patterns followed by the experiments validate the theoretical findings.", "questions": "1. What are the specific contributions of your work compared to other studies on the same problem, including those not cited in this paper?\n\n2. Have you explored the effects of varying the length of the prediction interval on the performance of PFSUM? Could you provide insights into the trade-off between consistency and robustness in your algorithm?\n\n3. Could you explain why your experimental validation relies on only two benchmarks? What are the reasons behind this choice, and do you believe that including more performance benchmarks could address potential limitations in demonstrating the algorithm's effectiveness?", "limitations": "There is no negative societal impact of this work.", "rating": 3, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "This paper presents several interesting elements, particularly in its approach to a more generalized version of the Bahncard Problem. The consistency of the proposed algorithm, with its bounded promises, is a noteworthy feature. Unlike traditional approaches, this algorithm does not require predicting the entire future input, which simplifies the decision-making process. Additionally, the paper provides a detailed analysis of the cost-effectiveness across six different travel patterns, offering valuable insights into the performance of the algorithm.", "weaknesses": "The contributions of this paper are relatively narrow and ambiguous. One significant issue is that the robustness of the PFSUM algorithm remains unbounded when β converges to 0. This limitation undermines the reliability of the algorithm in scenarios where β is very small. Additionally, the parameter T is critical as it defines the boundaries of both the time interval and the prediction interval. However, the paper does not provide a clear analysis of how variations in T impact the competitive ratio, leaving an essential aspect of the algorithm's performance unexplored.\n\nThe related work section fails to engage with recent literature that could provide context for this study's contributions. While [12] is a milestone work from 2020, recent publications exploring different facets of the same problem are omitted. These could include the works like \"Online algorithms with costly predictions (2023)\", \"Learning-Augmented Online Algorithm for Two-Level Ski-Rental Problem (2024)\" and others. Including these works would offer a more comprehensive view of the field's current state. The authors could also indicate the principle and mechanism differences, rather than contextual disparities, between their work and [25]. \n\nThe experimental validation is insufficient, relying on only two benchmarks, which inadequately demonstrates the generalizability and robustness of the proposed algorithm. While the paper claims to measure online algorithm performance using competitive ratios, the experiments primarily employ cost ratios. This discrepancy between theoretical claims and experimental measures undermines the impact of the findings and may lead to misinterpretation of the PFSUM's actual performance improvements.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### **Weakness 1 & Question 1**\nOur 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$.\n\n### **Weakness 2**\nThank 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.\n\n### **Weakness 3 & Question 3**\nThank 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**.\n\nRobustness 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.** \n\nFor 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. \n\n### **Question 2**\nWe 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.**", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper presents a novel, well-explained method with strong theoretical backing and empirical validation, offering significant improvements over previous work. The algorithms and ideas are presented clearly and intuitively, and the paper is well-written overall.  A key strength is that the algorithm simplifies decision-making by not requiring prediction of the entire future input.    

Some reviewers deemed the experimental validation insufficient, relying on too few benchmarks. Additionally, the unbounded robustness of the PFSUM algorithm when β approaches 0 and the lack of analysis on the impact of T were highlighted as weaknesses.

Overall, we recommend acceptance as a poster.

To authors: please make sure to address the remaining concerns in the final version.
Decision: Accept (poster)