Combinatorial Ski Rental Problem: Robust and Learning-Augmented Algorithms
Authors: Ziwei Li
Bo Sun
Zhiqiu Zhang
Mohammad Hajiesmaili
Binghan Wu
Lin Yang
Yang Gao
Venue: NeurIPS 2025 poster ()
Keywords: combinatorial ski rental problem
competitive analysis
learning-augmented algorithm
online optimization
Primary area: theory

Abstract: We introduce and study the Combinatorial Ski Rental (CSR) problem, which involves multiple items that can be rented or purchased, either individually or in combination. At each time step, a decision-maker must make an irrevocable buy-or-rent decision for items that have not yet been purchased, without knowing the end of the time horizon. We propose a randomized online algorithm,  Sorted Optimal Amortized Cost (SOAC), that achieves the optimal competitive ratio. Moreover, SOAC can be extended to address various well-known ski rental variants, including the multi-slope, multi-shop, multi-commodity ski rental and CSR with upgrading problems. Building on the proposed SOAC algorithm, we further develop a learning-augmented algorithm that leverages machine-learned predictions to improve the performance of CSR. This algorithm is capable of recovering or improving upon existing results of learning-augmented algorithms in both the classic ski rental and multi-shop ski rental problems. Experimental results validate our theoretical analysis and demonstrate the advantages of our algorithms over baseline methods for ski rental problems.

Combinatorial Ski Rental Problem: Robust and Learning-Augmented Algorithms
Ziwei Li
Sun University of Ottawa, Vector Institute bo. www.uuateereooo.c.ommm ca
Nanjing University
ziwei www.:mmmmmm.....mmmm.m nju....ii....................... edu.
Zhiqiu Zhang
Mohammad Hajiesmaili University of Massachusetts, Amherst haj majiismaill li@cs. umass. edu
Nanjing University
2219003996smail. nju. edu. cn
Binghan Wu AsiaInfo Technologies Limited wubh3das iainfo..ia.n............ com
Lin Yang" Nanjing University linyangōnju. edu. cn
Yang Gao Nanjing University gaoyânju edu. cn
Abstract
We introduce and study the Combinatorial Ski Rental (CSR) problem, which in- volves multiple items that can rented or purchased, either individually or combination. At each time step, decision- maker must make an irrevocable buy-or- rent decision for items that have not yet been purchased, without knowing the end of the time horizon. We propose randomized online algorithm, Sorted Optimal Amortized Cost (SDAC), that achieves the optimal competitive ratio. Moreover, SOAC can be extended to address various well-known ski rental variants, including the multi-slope, multi-shop, multi-commodity ski rental and CSR with upgrading problems. Building on the proposed SOAC algorithm, further develop learning- augmented algorithm that leverages machine-learner predictions to improve the performance of CSR. This algorithm is capable of recovering improving upon existing results learning auggineee algorithms both the classic ski rental and multi-shop ski rental problems. Experimental results validate our theoretical analysis and demonstrate the advantages of our algorithms over baseline methods for ski rental problems.
Introduction
Sequential decision-making under uncertainty is ubiquitous yet challenging in the digital transforma- tion society. We study the ski rental problem [7 g) classic online decision-making problem that addresses the rent-or-buy dilemma. In its basic form [9 16] 20), the problem involves repeatedly deciding whether to rent or buy an item without knowing its future usage duration. This paper introduces and studies more general variant, the Combinatorial Ski Rental (CSR) problem, which extends the rent-or-buy decisions from one item to multiple items.
In the CSR problem, player participates in skiing season of unknown duration. Skiing requires multiple essential items, such as skis, boots, helmets, and goggles. Each day, the player must decide whether to buy rent items that have not yet been purchased, with the goal of minimizing the total rent and purchase cost over the entire season. The combinatorics CSR stems from the
Corresponding Author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

purchase cost, which is cheaper when purchasing multiple items as combo compared to buying each item separately. The CSR model is inspired by real-world scenarios involving decisions over
multiple combinations [26
15 24 such as selecting data plan bundles in telecommunications [18].
configuring flexible service packages in cloud computing 4 and subseribing to software suites (e.g..
Microsoft Office) [32]. where users must choose among various combinations of applications.
Traditionally, online algorithms for ski rental problems are designed for worst-case scenarios, with performance measured by the classic competitive ratios 77. While this ensures robustness, it often comes at the cost of poor performance on favorable real-world inputs. To address the pessimism
of classic competitive algorithms. learning- augmented algorithms [21 [7 14 23]. as rapidly emerging field, aim to enhance traditional online algorithms by leveraging predictions from machine learning models. These algorithms are designed to make use of potentially imperfect predictions to achieve two goals: performing near-optinally when the predictions are accurate (i.e., consistency) and retaining worst-case guarantees when predictions are misleading (i.e., robustness) B3 34 In this paper, we aim to design both robust and perning-augmmener algorithms for the CSR problem.
Prior work. Many variants of the ski rental problem have been studied address increas- ingly complex application scenarios. In single- item ski rental problems, two main variants have been explored: (i) multi-shop ski rental[] (25,, where a skier must first choose one from multi- ple shops, and then decide whether to rent or buy one item from the chosen shop; (ii) multi-slope ski rental [19 d) where the skier has access to multiple rental and purchase options, and can adaptively switch among them over time. In multi-item settings, in addition to the rent-or- buy decisions, the skier must also determine the order in which to purchase different items, re- ferred to the purchase path in this paper. Two special cases of the multi-item ski rental problem
CSR with non-upgrading
multi-slope ski rental
CSR with upgrading
classic ski rental
multi multi-com commomyym rental
multi-shop ski reatal
multiple paths single option
single path aultiple options
multiple paths multiple options
Figure I: Relationship between CSR and other ski rental variants
have been studied. [29] considers the multi-commodity ski rental problem, where the rental and purchase costs are additive across items. 32 studies more general model in which both rental and purchase costs are submodular and also frames the model as combinatorial ski rental. However, the problem in [32 assumes that purchases can be upgraded, i.e., the player only needs to pay the price difference to sequentially acquire new items. We can show that under the simplified models in [29] and (32], the optimal order of purchasing items is fixed, i.e., there only one purchase path. As a result, their algorithms focus solely on determining the timing of purchases along this single path, thereby avoiding the challenge of selecting from multiple purchase paths. Algorithmically, both models can be viewed as special cases of the multi-slope ski rental problem for single item. The relationships among the different variants are illustrated in Figure
The CSR problem studied in this work generalizes all the aforementioned models. We consider multiple items with submodular purchase cost and consider that purchases cannot be upgraded, ie., the full price must be paid for each new item. In this setting, the selection of the purchase path becomes crucial and must be determined jointly with the timing of item purchases, making the problem significantly more challenging. The most relevant work (32] has derived an optimal e/(e- -ocooptttie algorithm for the CSR with upgrading. However, the non-upgrading variant remains open, requiring new algorithmic techniques and analysis. We focus on the variant with non-upgrading, and unless otherwise specified, use CSR to refer to the non-upgrading variant.
Contributions. In this work, we first propose an optimal randomized algorithm called Sorted Optimal Amortized Cost (SDAC) for the CSR problem. To the best of our knowledge, this is the first optimal online algorithm for CSR. The SOAC algorithm represents a general framework that can obtain optimal solutions across wide spectrum of ski rental variants, including the multi-slope [9], multi-shop (1. multi-commodity ski rental 22 and CSR with upgrading problems (32).
Subsequently, we propose a Barning-auggmett which provides consistency and robustness guarantees. LA-SOAC can recover and even improve existing ceapstenncy-oouuttteee trade-offss of learning-augmented augmented algorithms for ski rental variants. In particular, we recover the consistency and robustness bounds for the classic ski rental problem
algorithm for the CSR problem, termed LA-SOAC,
2

---

studied in Purohit et al. [2T] For the multi-shop variant, we prove that our algorithm achieves both tighter consistency and robustness bounds than those established in Wang al. (25] Numerical experiments validate our theoretical results and demonstrate the performance advantage of LA-SOAC.
Algorithmic ideas and technical novelty. Technically, the proposed algorithms SOAC and LA-SOAC adopt a novel strategy, OAC, which makes decisions by tracking the cost incurred by the offline optimal solution. At each time step, it allocates daily cost budget proportional to the offline benchmark. This design eliminates the need for intricate mathematical case analysis and can be broadly applied to the family of ski rental problems. Furthermore, to address the challenges from multiple purchase paths, we reformulate the problem as computing an augmented path that encompasses all possible purchase paths. We then prove that the competitive ratio convex function with respect to the probability distribution over these paths, enabling us to efficiently compute the optimal strategy.
2 Problem Statement
2.1 The combinatorial ski rental problem
Consider player who aims to participate in a skiing season with an unknown horizon T E N+ To ski on each day, the player must have a set M := (1.2......m) m) of skiing equipment (referred to as items) that are either rented purchased. At the beginning of each day, the player must choose to either buy or rent items that have not yet been purchased without knowing the horizon T. The goal is to minimize the overall cost of renting and purchasing items during the skiing season.
CSR is a generalization of the classic ski rental problem, considering rent-or-buy decisions for multiple items. For convenience, we refer to each individual item as a base item and any subset of these base items as super item. 2 denotes the set of super items. Let g(S): 2 R and S(S) 2M + RR+ denote the rental rate function and the purchase cost function for a super item S S 2-M, respectively, with ((0) = g(0) = O. In this paper, we focus on setup where the rental rate is additive and the purchase cost is submodular.
Assumption 1 (Additive rental rate). The rental rate of CSR g(S) is additive, i.e., g(S) = Eies ((i)), where g((i)) is the rental rate of base item i. Assumption 2 (Submodular purchase cost). The purchase cost of CSR is submodular, i.e., for any S E M and Z S Z' E 2M, holds that f(S Z') < f(S Z). where f(S Z) == S(SU Z)- f(Z).
We assume that the purchase price is submodular because it reflects the fact that buying multiple items together is cheaper than purchasing them individually. The combinatories of CSR stems from this submodularity. Furthermore, we consider an additive rental rate to simplify our analysis, as our results can be readily extended to scenarios with submodular rental rates, since our algorithm relies only on the buy-to-rent ratio ordering, which remains well-defined under submodular rental rates. Both purchase cost and rental rate functions are known to the decision maker upfront.
Definition 1 (Information Setup I). We define all information known prior the online decision maker of CSR as information setup I == {M. f().()))
2.2 Online formulation
An online deterministic strategy for CSR consists of two layers of decisions; the purchase path a := (S1,S2.... .,....,5p Si), which is an ordered sequence of super items such that U =M; and the associated purchase time t(or ;= {t(S o)) {s) where t(S o)) is the time of purchasing the super item S, given that purchase path a is chosen. For randomized strategies, without loss of generality, we focus on the mixed strategy that is distribution over deterministic strategies. Thus, we denote general randomized algorithm for CSR by A := A(q, p). where q == {q(0)) ) is the probability of choosing purchase path a over all possible purchase paths in Σ and p == (p, ])]neN- JineN-.Sea.eee ee is the purchase probability, i.e., (S o) represents the probability of purchasing super item S on day n. given purchase path a. For notational convenience, we omit the index of super item S; and path length I in purchase path ar. The expected cost of an online algorithm A is
ALG(T; = ΣΣΣ nE dE
((()) f(S.) PS. () + (())- (1- FF,, | ()) 9(S.)), (1)
3

---

( is the cumulative distribution function of buying super item S by day when purchase path a chosen. The first summation term inside the parentheses represents the expected purchase cost. And the second term represents the expected rental cost, where 1 - (S; a)) denotes the probability that S; has not yet been purchased by day n. Additionally, under the purchase path 0, (S σ)
where
O when F (S; () < to enforce the order of purchase in a.
2.3
Offline optimal structure
The goal of this work to design an online algorithm for the CSR such that its expected cost is comparable the optimal offline cost, which is obtained with prior knowledge of the time horizon T. Let (P)(T) represent the optimal offline cost of the CSR for given T. Since the purchase cost is submodular, purchasing items combo is always cheaper than buying them separately. The offline optimal algorithm is to purchase one super item at the beginning and rent remaining items until T. Therefore, OPT(T") be determined by solving the following equation
OPT(T)) min (f(S) + (M 5)}.
(2)
SE2M
The super item purchased in the beginning varies under different time horizons. Let (Si, S2.... ...) denote the sequence of optimal pur- chase sets as T increases. Note that does not repre- sent multiple purchases over time, but rather struc- tural summary of how the purchase decision offline algorithm changes with T. However, in special case when the purchase cost can be upgraded [31], a² can be shown to be the optimal purchase path in an on- the
Cost
==
f(Sk)
1(5
f(5))
f(52)
f(5))
line algorithm, which can be pre-determined beginning and thus simplifies the algorithm design. Thus, OPT(T') is a piece-wise linear function of and we illustrate it using the red curve in Figure 2 Each blue line illustrates the total cost purchasing and renting, given by f(S)) + (M \ 57), which corresponds to the scenario where one super item S purchased the beginning, while the remaining items continuously rented until time T. The y-intercept of the line represents the purchase cost of the super item, and its slope indicates the total rental rate of the remaining items.
f(S)
t1
C2
t3
44
tK
Time
Figure 2: Illustrating the optimal offline cost for the CSR problem.
Given the information setup I, the performance of an online algorithm is evaluated by a competitive ALo(T:A)
ratio CR(A) == SUрT OPT(T)) which is the worst-case ratio over all possible skiing horizon T. In the following, we design optimal robust algorithms that minimize the competitive ratio among all online algorithms Section and learning-and maaninggaugmeeeed algorithms by leveraging machine Icarned predictions in Section
Competitive Algorithms
In this section, we propose SOAC, optimal randomized algorithm to solve the CSR. Recall that a randomized algorithm involves two layers of challenging decisions: the purchase path selection, followed by purchase time decisions for each super item in the path. We first consider purchase path a is fixed, and focus on determining the purchase probability. To address this, we introduce an optimal amortized cost strategy, denoted OAC. Then we design the optimal algorithm SOAC by constructing an augmented purchase path and employing DAC as subroutines for CSR.
3.1 Optimal amortized cost strategy
In the CSR problem, the competitive performance the online algorithm depends on how to balance the immediate purchase cost against the potential rental costs. A straightforward idea is to amortize the daily costs in order balance the two sources of costs. Consequently, we define class of amortized cost strategies, which set the quota of the amortized cost day n AOPT(n), where

---

(n (n) OPT(n - 1) is the increment of offline optimal cost in Eq. and a is the target competitive ratio.
Let AALG(m; A) == (n; A) (L - 1; A) and (DPT(n) = OPT (n) - OPT(1 n - 1) denote the incremental costs of online algorithm A and offline algorithm if the time horizon progresses from 1 to n, where (LG(m; A) is given in Eq. ① for CSR, and (P)( is defined in Eq. (2)
Definition 2 (Amortized Cost Strategy, AC(o; a)), Given purchase path (equivalently the path selection probability q) and a parameter a > AC(ar; determines the purchase probability p of an online algorithm A (q. p) by solving the following system of equations
ALLG(n; A) = a- AOPT(n), when n < TAi
AALG(n; A) S a ΔOPT(n), when n. TA.
(3)
AALC(n: A) = 0, when n > TA-
AALG(n; A) == ALG(n; A) ALC(n - 1; A) is the incremental cost of the online algorithm A, where ALG(n; A) is given in Eq. (I). TA the "completion time" when algorithum A purchases all items and the cost stops growing. It is a variable to be determined by solving the system of equations.
Note that the amortized cost strategy AC a) and the completion time Ta depend on the parameter a. A larger a encourages earlier purchases of items avoid incurring high rental costs, thereby completing the acquisition of all base items at earlier stage, i.e., a smaller TA. We define an optimal amortized cost strategy (OAC) as the AC(o;; a) that sets such that Ta ToPT min arg max OPT(T)}. ToPt N+ is the "critical time" when the optimal offline cost stops growing, i.e., the minimum length of time horizon which the offline algorithm purchases all items in the beginning.
Given purchase path o, Algorithm D fillustrates the algorithm for the optimal amortized cost strategy (DAC(a)) and its competitive ratio is denoted as a(r) := (R(DA((a)) Since T' is non-increasing function of a, Algorithm I employs a dichotomous search find the a such that T' ToPT.
We show how to apply OAC for the classic single-item ski rental problem. In this case, the set of items M contains only one item, i.e., [M| = 1, and the rental rate and purchase price are given by 9((1}) 1 and f({1}) b, respectively. The costs of optimal offline algorithm and the online algorithm can be derived as follows: (PT(n) = min b). ALG(m; A) = Eie(h 1 6)-
Example 1.
({1}) + n Eieti Ps (f1))). Based on Eq. 3
OAC is the solution to the equations:
AALG(n: A) a, n S b; AALG(R: A) O, b.
Solving the above equations yields the optimal competitive ratio a = (1 5-1 and purchasing probability Pa ({1)) = (1-1)²= b-n
6/1 (1-(1-(1/6))) S b, which match the classic results for the single-item ski rental problem in [2
3.2 The SOAC algorithm
In CSR, an online algorithm that follows determinstic purchase path achieves suboptimal perfor- mance due the submodular purchase cost. We next design Sorted Optimal Amortized Cost Algorithum (SDAC, Algorithm 2) that determines the purchase path Σ with probability and the corresponding purchase probability p = {pn (S o)) o))
{g(G)))EE SEo. simultaneously. In the high level, SOAC uses the purchase path probability to construct an ancillary augmentation path n Ea (g)). This augmentation path encompasses all possible optimal outcomes for CSR problems. We show that the competitive ratio of OAC(, (q)) is convex in (see Lemma and thus we derive the optimal purchasing path probability using projected gradient descent method. the following, we show the details of SOAC.
5

---

Algorithm SOAC: Sorted Optimal Amortized Cost
Algorithm 1 OAC: Optimal Amortized Cost
Input: I == (.g,),, E,
Input:Z = (g), 0,
All disjoint partitions: r= {71, 72.......... ( Sort divisions by BR: {or, 02
Initialize: = 1, Olmax f(M). Omin
Construct algorithm A= AC (T;
Calculate (T) and TOPт based on Eq.
Construct 7 (q) based Eq.
while Ommax Omiin do
Initialize: a - f(M), Cnew
I, Da t
Calculate Tд using a according to
q = (((o,))(_ !|| (T7 ( FT))
Eq. (1) and Eq. (3)
while Aa > & do
Ta TOPT then O'max f- a
q q -- 11 V (7
else mmmn f
q f ProjectSimplex (q)
end
Onew f "( (q)), da f- la Onew
Update +- (amax + m2 end while
a f Onew
end while
Let := ((S)/((( denote the buy-to-rent ratio (BR) of super item S. A key observation is that the smaller the BR, the earlier the super item should be bought (See Lemma 33. which can greatly reduce the number of possible purchase paths. Define I {r1 72........ ................................ Mry } as the set of all possible disjoint partitions of . and Σ {or, 02, ... 0rr the corresponding set of purchase paths, where o; is obtained by sorting the super items in 7/s in ascending order of BR values. Let D denote the total number of possible super item including all individual base items well as combinations with bundle discounts. Denote these super items by Stnj- Sp......
sorted ascending order of
BR, i.e., (R) < (R(S S ... S BR(S(p)).
Given set of purchase paths and the path selection probability q, we define an augmented path as
( (T(q Sp)), (( Sp)). T [[ SpD)))
where [qq denotes a new super item that comprises the same base items Stg but has purchase price of q[) {( and a rental rate of d(}] (S( and Í()) = Eee2:S ((r) is the
sum of selection probabilities from paths that contain super item Stj-- The construction of 7.8
equivalently transforms the lath-level probability structure in the CSR problem into item-level decision
information, enabling efficient decision-making under fixed q (See Lemma 4
(())()))())))))))))))))))(())( Recall that competitive ratio of SDAC() (q)) is a(> (q)). Our problem reduces to find the path selection probability minimize the competitive ratio, i.e., q* arg ming (q)) To achieve this, we employ the Projected Grudient Descent (PGD) method. At each iteration, we compute the gradient of the competitive ratio with respect q and update q along the direction of the negative gradient. To ensure that q remains a valid probability distribution (i.e., g(or)) 2 0 and E.I ((a.) 1), we project the updated q onto the probability simplex.
Example 2. We demonstrate the SOAC algorithm with three items, rented daily $0.30. $0.80, and $0.50, and individually purchasable at $149.99 99999 each. Bundled purchases offer discounts: $229.99 ,9 for any pair and $329.99 for all three. The buy-to-rent ratios of all super items can be sorted follows
BR (2, 3)) S BR( ((2)) S BR((1, 2,3)) S BR( (1,2)) S (R((1)3)) - BR (3)) < BR (B( (1)).
We find a total of 5 sorted purchase paths of the set 21, where the super items in each path are arranged ascending order of their buy-to-rent ratios.
Path 1-5: (1)),33), ((1, 2), (3)). (12), (1,3)), ((2, (1)), ((2), (3), (1))-
Let qi for i E {1,2, ...,.,,, 5} denote the probability of selecting the i-th path. These probabilities are used construct augmented purchase path follows:
(g (2.3)) (gs (2)), (q)
(g2, (1, (gss (1.3)). (3)), ((4+ (1))).
In practical applications, D can be much smaller than |2- not combinations eligible for discounts.

---

To determine the optimal probabilities 9t we adopt projected gradient descent to minimize the competi- tive ratio of the augmented purchase path. The re-
Purchase Probability
0.02
[2,3]
50AC
[ m Path 4
Path
Probabilitt
0.015
1,2.3) la Path
Competiive
1.75
P0th
0.01
0.005
broakpeint
1.00
sults show that only two
1.0
1.90
paths have non-zero prob- abilities: Path 1 (1,2,33) with 70.4% and Path 4 ([2,3), (1)) with 29.6%. Using qi. we compute the optimal randomized pur- chase probabilities for each item per path per day, as illustrated in Figure 3(.). The offiin breakpoint in Figure B arises because this point lies exactly transition point of the piecewise linear offline optimal function, where the slope of the function changes. Figure b) compares the competitive ratio of SOAC with baseline that fixes a single path. The results indicate that fixing the path leads to sub-optimal performance. Moreover, the average competitive ratio over varying horizons aligns well with the theoretical expected competitive ratio, demonstrating the accuracy of SOAC.
100
209
300
400
000
Days
Horizon
(a)
(b)
Figure 3: (Example 2) (a) Purchase probabilities along different paths. (b) Theoretical vs. empirical competitive ratios across varying horizons.
3.3 Theoretical Result for Competitive Algorithms
Our first main result is to show the optimality of SOAC for the CSR problem.
Theorem 1. Given setup information I, the SOAC algorithm attains the optimal competitive ratio among all online algorithms for the CSR problem.
The competitive ratio of the CSR problem depends on the setup information, and exhibits no closed form expressions. Notably, the competitive ratio can exceed the well known ratio e/ 1) for the classic ski rental problem as shown in Figure 3 This is inherently due to risk of a fault path selection in the online algorithms, and there is cost to switch across different paths when the purchases cannot be upgraded. This is also the key difference of CSR from other existing variants of ski rental problems. Furthermore, can show that the CSR problem generalizes many well-established variants of the ski rental problems, including the multi-shop ski rental [1, multi-slope ski rental [9)] comoodyy ski rental (29) and CSR with upgrading (32 problems. Therefore, our proposed SOAC algorithm can also achieve optimal ratios for those variants.
Lemma 1. The SOAC algorithm achieves the optimal competitive ratios for multi-shop, multi-slope, multi-conmmdity and CSR with upgrading ski rental problems.
In fact, SOAC not only provides an alternative algorithm to previous variants, but also resolves some open problems. For example, in multi-commodity ski rental problem 22).. prior work only achieves optimal solutions when all items have the same buy-to-rent ratio. The SOAC algorithm provides the first optimal randomized solution for arbitrary price configurations, filling this gap in the literature. A formal discussion related to generality of our model and algorithm is provided in Appendix E We end this section by providing a proof sketch for Theorem [ and its full proof is given in Appendix C
To prove the optimality of SOAC, we first show that for a given purchase path σ, the optimal amortized cost strategy OAC(ar) is optimal.
Proof sketch of Theorem [
Lemma (Optimality of DAC). For the CSR problem with setup information I. given purchase path a, DAC(a) achieves the optimal competitive rutio among all online algorithms.
Next, we show that we can only focus on the purchase paths whose super items are arranged in increasing order of their buy-to-rent ratios. This greatly reduces the possible purchase paths.
Lemma 3 (Optimal purchase order). Given disjoint partition 7 7= (S1,S2.-.. .2,...,,)) of M. (RC() achieves the minimum competitive ratio among all purchase paths with the same super items in where 7 BR (Sp, Sp....... Sqy) such that (R(S)p) S BR(S(2) S.... ... S BR(S)))
Building on Lemma 3 we can further prove that the optimal strategy for CSR, with given set of possible purchase paths and the associated path selection probability q, is equivalent to a CSR with one augmented purchase path Bg)), which is defined in Eq. (4).
7

---

Lemma 4 (Equivalent problem transformation), Given the setup information I for CSR, given purchase path probability q. the CSR problem reduces to determining the optimal purchase probability for the augmented purchase path 7 ('((g)
Given the path selection probability q. SOAC uses OAC(n BR (q)) to determine the purchase probability and obtain the corresponding competitive ratio a(("8((4) (q)). Finally, SOAC obtains the optimal q" using a PGD method. The optimality of q² is ensured by proving the convexity of a() in q.
Lemma 5 (Convexity property). The competitive ratio a(>**(q)) of the optimal amortized cost strategy under the augmented path (8)(4) convex function of the path selection probability 9-
Combining all above results gives the proof Theorem
Remark 1. The proposed algorithm SOAC establishes the first unified theoretical framework for various ski-rental variants, proving both the existence and computability of the optimal solution. Although the worst-case computational complexity of SOAC is exponential due to the exponential number of possible combinations, in practical scenarios only a limited number of combinations are relevant, which reduces the runtime to polynomial time. We provide a detailed runtime analysis in Appendix G.5 Moreover, for existing variants such as the multi- shop ski rental, pulti-slope ski rental, and multi- molli-commodity ski renial problems, the computational complexity of SOAC remains polynomial.
4
Learning-Augmented Algorithms
Based on the optimal robust algorithm SOAC, this section continues to explore how machine-learned predictions can be leveraged to break the pessimistic worst-case bounds. Consider that in the beginning of ski season, we obtain a prediction of the time horizon T. Our goal is to design Borning-auumenner SOAC (LA-SOAC) that can provide the best possible consistency and robustness guarantees. In particular, let Ay;A == (9y:>:Pu Pg:x) denote the algorithm for given prediction and confidence parameter A, where À (0, 1) is a hyperparameter that indicates the confidence in the prediction (the smaller X, the more confidence in the prediction). An algorithm Ay. is μ consistent if ALG(T"; Ay;a) S μ OPT(T) when the prediction is accurate (i.e., y = 'T), and 3-robust AT: Ay:x) S 3- OPT(T") for any actual end times T.
Recall that key design in SOAC is to enforce the completion time TA, at which the algorithm's cost stops to increase, to the critical time of offline optimal TOPT, at which the offline algorithm stops to increase. Our core idea of LA-SOAC is dynamically adjust the completion time To based on the predicted value y. Intuitively, when the prediction y is large, a smaller completion time T, is preferred. However, the original SOAC fails if the completion time is set larger than Turt, since the incremental cost ΔOPT(n) = for n > ToPT, making it infeasible to track DPT(n) introduce
beyond this point. To address this problem. Let t = max(n E N+] ΔOPT(n) 2 (PT(TTpt)/Tarr) ΔÖPT(n) ΔOPT(n) for t", and ADPT(n) = OPT (PT((Tpr)) (FTT)) / for n > t". This modified cost ensures that the incremental cost of DPT(n) is at least OPT (PT(T))))/ (TTTT)/TTPT) ToPT.
augmented cost function (PT(n). The increment of OPT(n) is defined as
In LA-SDAC, we extend SOAC to SOAC, which replaces (PT(n) with (PT(m) and changes the critical time from TOPT to Tm.. Let SOAC(TML.) denote the modified strategy (See Appendix for full description). The LA-SOAC algorithm adjusts Tra based on the prediction y: If 2 Topr, it prioritizes early purchases by setting Ta. [XT where the parameter T S Topr- If y < Topr, it delays purchases by setting Tm,- = [ (]] where r'(2) > ToPr. Using adjusted critical times, LA-SOAC computes purchase probabilities Ay:A The procedure outlined in Algorithm 3
Algorithm LS-SOAC: Learning-Augmenter SOAC
1: Input: Setup information I = (M, f. 9): prediction y: parameters T(l) T(2), X;
2: if' y 2 ToPt then
3: Set Ta + [X and obtain A A1 = (g P 9: = SOAC(TTa);
4: else
5: Set Tm. T//2//1 and obtain (22) (g (2)
g P (2)) SOAC(Th...
6: end if
8

---

Theorem 2. Given parameters T S Topr T 2 Topp and confidence factor X E (0, 1), let ( ye and A A denote purchase probabilities determined in Algorithm Then ALo A22) aLG(T A (PT(T (PT(T
the consistency of Algorithm is max
ʃ and its robustness is
ALO(LATT A oFF OPT([ATT
ALG SPF
/AT A
max
OPT()
Due to the complexity of the expected costs the CSR problem, there are no closed-form expressions for consistency and robustness in general. Theorem 2 states that both consistency and robustness of LA-SDAC are dominated by two extreme ratios. Suppose the prediction accurate, i.e., = T. If
2 TOpt, the cost ratio ALG(T: AT
ALG(T: A
is maximized at T = Topt; if < Topr, the ratio GPT(T)
DPT(2")
is also maximized at T TOPT. Thus, consistency is dominated by the maximum of these two extreme ratios. In contrast, when the prediction may be arbitrarily inaccurate, the cost ratio peaks at OPT if y 2 Topr. and at T [TOPT/A /A] if y < TOPT. Note that ( />]) OPT((Tpr))
T = [ so in the denominator we use T = TOPr for computing (PT( Thus, robustness is governed by the maximum of these two extreme-case ratios.
Parameters T and TOP are set to Topr in general, and can be specifically designed to optimize
consistency and robustness. Specifically, in the classic ski rental problem, we can set TOP: = TOP = TOP,. and LA-SOAS recovers the explicit bounds 2T, as shown in Corollary [] For the multi-shop
ski rental problem, by properly setting ToPT and T!2) LA-SOAC attains improved consistency and robustness bounds compared previous results (25). as shown in Corollary 2
Corollary 1. For the classic ski rental problem with purchase price b and rental price 1, when T(l)] T(2) Topr and X (t, 1}, LA-SOAC is -c-x-sconssteett and 1+1/b 1he-(x-175) -robust.
Corollary 2. For the multi multi-shop ski rental problem with s shops, where the purchase prices satisfy
by > by and the rental prices satisfy 1 = ri < ... < Ts. when T(1)
OPT Topp. Top = b, and
T. 2 1. LA-SDAC guarantees a consistency ratio no worse than I-c Tx and robustness ratio
1/x41/b, }. no worse than b max 11---10--100 1-e-1/X j. which are the bounds established in [25].
by
5 Numerical Results
We empirically evaluate the performances of LA-SOAC Con- sider three items, with item prices b, 80, by 110, and by = 130, and the same rental price of 1. The discount factor for purchasing any two items together set 0.95, and 0.9 for three items. We let the actual number of days, T. be uniformly distributed within the region [1, 47pr]. The predicted number of days, y. is set to T + e, where the simulated error c follows a normal distribution with mean 5 and standard deviation 17. i.e., c ~ N8, n²). Here, 8 con- trols the bias of the prediction, while 77 (referred as the error parameter) characterizes the variability or uncertainty the prediction. For each standard deviation, 10,000 sam- ples are randomly sampled in this study, and their average competitive ratios are calculated, Figure 4 compares the trade-off performance of the LA-SOAC algorithm against strategies that follow only single path. The results demonstrate that LA-SOAC consistently outperforms the others.
1.8
11. 91. (9))
(2) (3))
81. 3). (29)
[A]. [2, 911
Consletency
(0. 3))
8.4
1.3
1.1
3.5
Robustness
Figure 4: Consistency vs. robustness.
Figures 5 a) and b) further illustrate the average competitive ratio under varying levels of pre- diction error 17. Specifically, Figure (5a) presents results with 5 0 for different values of E (0.25, 0.5. 0.75, 1). When À is smaller, the average competitive ratio is lower under accu- rate predictions but higher under inaccurate predictions. Figure evaluates performance across varying error levels 5 E (50, 100, 150, 200). For a fixed X, the results indicate that the optimal choice of bias& 8 depends on the error parameter y, When r is small, smaller bias tends to yield better competitive ratios, as it allows the algorithm more effectively exploit accurate predictions.

---

1.8
1.0
LA-SOAC 0.25
1.7
1.7
1.6
1.8
Compettive
1.5
- 0.5
0.25
Unblased
1.3
0.70
1.3
= 50
100
150
1.2
1.2
1.1
1.1
100
200
300
400
500
600
200
300
400
500
600
Parameter
Error Parameter
(a)
(b)
Figure 5: (a) Average numerical competitive ratio over various error parameters r) and X. (b) Average numerical competitive ratio over varying error parameters and 8.
LA-SOAC
188
14-518804
Shop
1.7
Slop 2
Compeniive Ratio
Slop
Shop
Shop
1.8
1.5
LA-SONC-S11
1.4
LAMISR- 700
1.3
LN-GONC---D6
LAMB5R.005
1.3
1.2
100
200
300
400
500
600
Robustnees
Error Parameter
(a)
(b)
Figure 6: (Multi-shop ski rental) (a) Consistency vs. robustness. (b) Average competitive ratios.
In contrast, when 7j is large, a larger bias å becomes beneficial, as it helps hedge against extreme inaccuracies, thereby improving overall performance.
We compare our LA-SOAC algorithm with the state-of sire--ofthh-attt art seaming--uggment multi-shop ski rental (Algorithm 3 in [25] referred to as LA -MSRR... The evaluation utilizes the dataset
algorithm for
from (25). comprising shops with purchase prices defined by = 100, b2 = 95, by = 90, h4 1.00, 1.05, r3 = 1.10,
85. by = 80, bg 75 and rental prices given by
1.15,,
1.20, rg 1.25. Consistent with [25), the actual number of days modeled as uniformly distributed
within the interval [1, 361]. Figure 6(a) illustrates the performance trade-off of LA-SOAC compared to LA-MSSR (25) and a baseline strategy that follows a single path. The results demonstrate that LA-SOAC achieves superior trade-off compared to 225 Furthermore, Figure (bbb) compares the average competitive ratio, demonstrating that LA- SOAC offers a better trade-off and surpasses the performance of [25] in certain cases. For more numerical experiments about SDAC and LA-SOAC. see Appendix G The source code for reproducing all experiments is available at /ttttts://giiiee
com/ catt/guodongaanninkkee/oooooo
Ski Rental_nnllaeeea R Problems
6 Conclusion
In this paper, we study robust and learning-augmentte algorithms for the CSR problem. We first propose the SOAC algorithm, an optimal randomized algorithm for CSR, which can be extended to address many other variants of the ski rental problem. Building on this, we introduce learning- augmented algorithm that provides both consistency and robustness guarantees, and can recover or improve existing results of learning- augmented algorithms in classic ski rental and multi-shop ski rental problems. Although the computational complexity of the SOAC algorithm can grow exponentially with the number of super items, this is an algorithmic limitation stemming from the combinatorial nature of the problem. practical applications, however, number of combinations often limited, i.e., not all combinations are eligible for discounts. This can significantly reduce the computational complexity of the SOAC algorithm, In future work, we plan apply our algorithms to real-world scenarios to investigate their practical impact.
10

---

Acknowledgments
Lin Yang would like thank the support from NSFC (No. 62306138), JiangsuNSF (No. BK20230784), and the Innovation Program of State Key Laboratory for Novel Software Technology Nanjing University (Nos. ZZKT2024B15, ZZKT2025B25), Mohammad Hajiesmaili would like to thank the support from NSF CAREER (No. 2045641).
References
[1] Lingqing Ai, Xian Wu, Lingxiao Huang. Longbo Huang. Pingzhong Tang, and Jian Li. The multi-shop ski rental problem. In The 2014 ACM international conference Measurement and modeling of computer systems, pages 463-475, 2014.
[2] Keerti Anand, Rong Ge, and Debmalya Panigrahi. Customizing ml predictions for online algorithms. In International Conference on Machine Learning, pages 303-313, PMLR, 2020.
[3] Etienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning augmented algorithms. Advances in Neural Information Processing Systems, 33:20083-20094, 2020.
[4] Asmae Benali and Bouchra EI Asri. Towards rigorous selection and configuration of cloud services: research methodology. arXiv preprint arXiv:2104.00819 2021.
[5] Arghya Bhattacharya and Rathish Das. Machine learning advised ski rental problem with discount. In International Conference and Workshops on Algorithmss and Computation, pages 213-224. Springer, 2022.
[6] Toni Böhnlein, Sapir Erlich, Zvi Lotker, and Dror Rawitz. Randomized strategies for non- additive 3-slope ski rental. International Colloquium on Structural Information and Commu- nication Complexity, pages 62-78. Springer, 2022.
[7] Allan Borodin and Ran Yaniv.. Online computation and competitive analysis. cambridge university press, 2005.
[8] Yucheng Dong, Yinfeng Xu, and Weijun Xu. The on-line rental problem with risk and proba- bilistic forecast. In Frontiers in Algorithmics: First Annual International Workshop, FAW 2007, Lanzhou, China, August 1-3, 2007. Proceedings I, pages 117-123. Springer, 2007.
[9] Björn Feldkord, Christine Markarian, and Friedhelm Meyer Auf der Heide. Price fluctuation in online leasing. In International Conference on Combinatorial Optimization and Applications, pages 17-31. Springer, 2017.
[10] Hiroshi Fujiwara, Takuma Kitano, and Toshihiro Fujito. On the best possible competitive ratio for multislope ski rental. Algorithms and Computation: 22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings 22, pages 544-553. Springer, 2011.
[11] Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or-buy with expert advice. In International Conference on Machine Learning, pages 2319-2327. PMLR, 2019.
[12] Anna R. Karlin, Mark S. Manasse, Lyle A. McGeoch, and Susan Owicki. Competitive random- ized algorithms for nonuniform problems. Algorithmica, 11(6):542-571, 1994.
[13] Ali Khanafer, Murali Kodialam, and Krishna PN Puttaswamy. The constrained ski-rental problem and its application to online cloud cost optimization. In 2013 Proceedings IEEE INFOCOM. pages 1492-1500. IEEE, 2013.
[14] Misha Khodak, Maria-Florinn F Balcan, Ameet Talwalkar, and Sergei Vassilvitskii. Learning predictions for algorithms with predictions. Advances Neural Information Processing Systems, 35:3542-3555 2022.
[15] Gilsoo Lee, Walid Saad, Mehdi Bennis, Abolfazl Mehbodniya, and Fumiyuki Adachi. Online ski rental for on/off scheduling of energy harvesting base stations. IEFE Transactions on Wireless Communications, 16(5):2976-2990, 2017.

---

[16] Russell Lee, Jessica Maghakian, Mohammad Hajiesmaili, Jian Li, Ramesh Sitaraman, and Zhenhua Liu. Online peak-aware energy scheduling with untrusted advice. In Proceedings of the Twelfth ACM International Conference on Future Energy Systems, pages 107-123, 2021.
[17] Amir Levi and Boaz Patt-Shamir. Non-additive two-option ski rental. Theoretical Computer Science, 584:42-52, 2015.
[18) Yi-Bing Lin, Wei Lin, Jo-Ching Wu, and Yung-Ching Wang. An investigation of telecom mobile data billing plans. Journal of Internet Services and Information Security (JISIS), 6(3)1- 26, 2016.
[19] Zvi Lotker, Boaz Patt-Shamir, and Dror Rawitz. Rent, lease, or buy: Randomized algorithms for multislope ski rental. SIAM Journal on Discrete Mathematics, 26(2):718-77 736, 2012.
[20] 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
PMLR, 2023.
[21] Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. Advances in Neural Information Processing Systems, 31, 2018.
[22] Yongho Shin, Changyeol Lee, Gukryeol Lee, and Hyung-Chan An. Improved learning- augmented algorithms for the multi-option ski rental problem via best-possible competitive analysis. In International Conference on Machine Learning, pages 31539-31561. PMLR, 2023.
[23] Bo Sun, Russell Lee, Mohammad Hajiesmaili,, Adam Wierman, and Danny Tsang. Pareto- optimal Bearning-augmenti algorithms for online conversion problems, Advances in Neural Information Processing Systems, 34: 10339-10350, 2021.
[24] Mike Timm and Sabine Storandt. On the multi- bahncard problem. In 20th Symposium on Algorithmic Approuches for Transportation Modelling, Optimization, and Systems, 2020.
[25] Shufan Wang, Jian Li, and Shiqiang Wang. Online algorithms for multi-shop ski rental with machine learned advice. Advances in Neural Information Processing Systems, 33:8150-818 5166, 2020.
[26] Wei Wang, Ben Liang, and Baochun Li. Optimal online multi-instance acquisition in iaas clouds. IEEE Transactions on Parallel and Distributed Systems, 26(12);44073411, 2014.
[27] Alexander Wei and Fred Zhang. Optimal robustness-consiiseen trade-off's for learning- augmented online algorithms. Advances in Neural Information Processing Systems, 33:8042- 8053, 2020.
(28) Binghan Wu, Wei Bao, and Dong Yuan. Competitive analysis for two-level ski-rental problem. In Proceedings of the AAAI conference on artificial intelligence, pages 12034-12041, 2021.
[29] Binghan Wu, Wei Bao, Dong Yuan, and Bing Zhou, Competitive analysis for multi-commodity ski-rental problem. ratio, 10(10): 10, 2022.
[30] Yinfeng Xu, Rongteng Zhi, Feifeng Zheng, and Ming Liu. Competitive algorithm for scheduling of sharing machines with rental discount. Journal of Combinatorial Optimization, 44(1):414- 434, 2022.
[31] Guiqing Zhang, Chung Keung Poon, and Yinfeng Xu. The ski-rental problem with multiple discount options. Information Processing Letters, 111(18):903-90, 2011.
[32] Hanrui Zhang and Vincent Conitzer. Combinatorial ski rental and online bipartite matching. In Proceedings of the 2t ACM Conference on Economics and Computation, pages 879- 179-910.
2020.
[33] Xiaoling Zhou, Ou Wu, and Nan Yang. Adversarial training with anti-adversaries. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024.
[34] Xiaoling Zhou, Wei Ye, Zhemg Lee, Rui Xie, and Shikun Zhang. Boosting model resilience via implicit adversarial data augmentation. In Proceedings of the Thirty-Thirl International Joint Conference Artificial Intelligence, pages 5653-5661, 2024.
12

---

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 reflect the contributions and scope of this paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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 or
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 are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We analyzed the limitations of our work in Section
Guidelines:
The answer NA means that the paper has no 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 a separate "Limitations" section 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 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 on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be 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 images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged 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.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

This paper gives complete assumptions for all theoretical results as well as complete and correct proofs.
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 proofs 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
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All results in the paper are reproducible, and we have provided the source code in the supplementary materials.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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 dataset and/or model, the authors should describe the steps taken 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, it may be necessary 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 one good way accomplish this, but reproducibility can also be provided via detailed 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, or other means that appropriate to the research performed.
While NeurlPS 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 reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is 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).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe 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 possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
14

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
In the supplementary materials, we have provided our source code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a 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
//nips //iiss.cc/pill wttpcccpppppppppeeeeeeeeeeeeeeee httaa//gguuiee//eeeeebiiiisssss /Cc////oddiiisssseeeeeee ssiiiiiisiiiyyyyy for more details.
The authors should provide instructions on 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. If 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 the paper) is recommended, but including URLs to data and code is 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 understand the results?
Answer: [Yes]
Justification: The paper clearly specifies all details of the training and testing processes (See Section Appendix G).
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper 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, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
See Section Al and Appendix G
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, 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 with given experimental conditions).
15

---

The method for calculating the error bars should be explained (closed form formula, call 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 1-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 figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have provided sufficient information to describe the required computing resources (See Appendix Gp.
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 of compute required for each of the individual experimental runs as well as 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 the paper conform, in every respect, with the NeurlPS Code of Ethics htttps:/nneurps... http://wwwwp....ooocccccccccceee
Answer: [Yes]
Justification: Our research complies with the NeurIPS Code of Ethies.
Guidelines:
The answer NA means that the authors have 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- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The CSR problem has no direct societal impact.
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 why the paper does not address societal impact.
16

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies 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 to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional 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 to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe 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)?
Question:
Answer: [NA]
Justification: Our paper does not have such risks.
Guidelines:
The answer NA means that the paper poses no 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 to 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 is 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 (e.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: [Yes]
Justification:
The model we used appropriately credits the original creator.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, 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 are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
17

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if 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:
[NA]
Justification:
We have not released any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include 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: This paper does not involve crowdsourcing 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 in 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 in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or 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 equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on 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.
We 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, not include any information that would break anonymity (if applicable), such the institution conducting the review.
18

---

16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: /ttpp/////euips..... wwwparippsscccoooeeeeeee cc/Conferencess///////e for what should or should be described.
19

---

Appendix
Related work
21
Proof for Lemma
21
B. Proof of Proposition
22
B.2 Proof of Proposition
25
B.3 Proof of Proposition
25
Proof for hhorrmm
26
Proof of Lemma
26
Proof of Lemma
27
Proof of Lemma
27
Optimal algorithm for CSR with upgrading
28
Problem setting
29
D.2
Overview the main results for CSR with upgrading
29
D.3 The optimal purchase path
................................
30
D.4 An ene/(e - 1) upper bound for CSR with upgrading
31
D.5 Proof of Proposition
34
Proof for Lemmall
35
Proof of Proposition
36
Proof of Proposition
36
E.3
Proof of Proposition
37
Supplementary Material for SA-SOAC
37
Supplementary details of LA-SOAC
37
Proof of Theorem 2
38
Proof of Corollary
40
Proof of Corollary
41
Supplementary Numerical Results
41
Supplementary numerical results in Section
42
G.2
Application of SOAC to the multi-shop ski rental problem
42
G.3
Application of SOAC to the multi-slope ski rental problem
44
G.4
Supplementary numerical results of SOAC and LA-SOAC
44
G.5
Runtime Analysis
46
20

---

A Related work
The classic ski rental problem was first introduced by [2], where optimal deterministic and ran- domized algorithms were developed, achieving competitive ratio upper bounds of 2 and e/(e- 1 1), respectively. The rent-or-buy dilemma in ski rental problem [7 g has wide range of applications, including on/off scheduling of small cell base stations for energy saving with intermittent demands [15], request-response caching for cloud services [13,, and bandwidth cost minimization in content delivery networks [20]. Additionally, it applies to purchasing multi-kind Bahncards to reduce ticket prices for future journeys, thereby lowering repeated travel costs 24
Various variants 22 28 9 of the ski rental problem have since been proposed to address more complex application scenarios. The most relevant work [32] proposes randomized algorithm for the CSR that allows for upgrades, achieving a competitive ratio of e/(e 1) using a primal-dual framework. Their work addresses CSR with upgrading as the primal problem and combinatorial online bipartite matching as the dual problem. The multi-slope ski rental problem [19] 6 [0] is a variant that introduces a one-time setup cost and asage-duration-depeedee cost for each option, enabling customers to switch between options. This problem is further divided into two versions: additive and non-additive. The additive version allows buying costs to accumulate, while the non-additive version has arbitrary switching costs for each switch. In [1 an optimal randomized algorithm for the additive version and an e-competitive ratio for the non non-additive version are proposed. [ introduces the multi-sho shop ski rental problem, in which multiple shops offer the required item. Upon arrival at the ski field, customers must select a shop and decide whether rent or purchase the item from that shop [25 The authors derive closed-form solutions for this problem and develop a linear-time algorithm to compute these solutions efficiently.
Another variant is the two-level ski rental problem (28), which involves making decisions on individual or combined purchases of all items. They develop an optimal deterministic online algorithm that uses two fixed thresholds for decision-making when rental costs exceed predefined levels. Further, the authors 29 investigate the multi- coneiiitmmooity ski rental problem, which requires considering multiple purchase combinations without any discounts. They propose an online algorithm and demonstrate its optimality when items have the same rent-to-buy ratio. [3T] study the multi mulli-discount ski rental problem, which involves a single item with multiple rental options 22 30,, each with a rental duration and increasing discounts as the rental duration increases. They propose a 4-competitive ratio algorithm and observe that the competitive ratio increases with the number of available rental options.
In recent years, the integration of learning- based predictions into online algorithms has introduced a new paradigm known as aaniin-- online algorithms. These methods aim to balance two key metries: consistency and robustness 227 23 Consistency measures the algorithm's
performance with perfect predictions, while robustness focuses on the algorithm's 's performance when the prediction is of low quality. Researchers have proposed several
-agnningg-uggeeete algorithms to tackle different variants of the ski rental problem [5] 25 2 For instance, (21] has demonstrated the high robustness of their machine-learning algorithm for the classic ski rental problem. Similarly. (25) has used machine learning algorithms to significantly improve the performance of their algorithm for the multi-shop ski rental problem. 2 have studied strategies for customizing machine learning algorithms by incorporating optimization objectives into the loss function. [1] have developed an algorithm that balances consistency with robustness for the ski rental problem with expert advice and established strict upper and lower bounds for the consistency ratio based on the number of experts.
B Proof for Lemma 2
The Lemma 2 is established by Proposition] I Proposition 2 and Proposition 3 Given purchase path a. we define family of amortized cost strategies (AC(o; ax) J=) parameterized by the target competitive ratio o, and show that any optimal online algorithm belongs to this family (Proposition [ We then establish that the completion time T' of the algorithm A = AC(a; a)., defined as the time at which all purchases are completed, is monotonically non-increasing with respect to (Proposition 2 Furthermore, we prove that no AC(a; a) algorithm can have a completion time T'A exceeding Topr, the completion time of the optimal offline algorithm (Proposition B) Combining these results, we conclude that the minimal competitive ratio among AC(a; a) strategies is attained when the completion time equals TOPT-
21

---

Proposition 1. Given the information setup I of the CSR problem, among all online algorithms that follow the purchase path o, the amortized cost strategies (AC(o; a)}a> include the optimal online algorithm.
Proposition 2. Given information setup I of the CSR problem and a purchase path o, if there exist algorithms A1 = AC(a;; a1) and A2 AC(o;; with a1 Q2 then TA2 S 'TA.
Proposition 3. Given a setup I for the CSR problem, a purchase path o, and the algorithm A =
AC(a; oi;; there does not exist an a such that TA Topr.
B.1 Proof of Proposition 1
We begin by establishing Proposition 4, which demonstrates that for the CSR problem with |M = I, purchasing the item earlier results in a lower cost when the game duration is long.
Proposition 4. For a information setup I = [M, of CSR, where |M| = 1, let k. u E NO and k < Suppose A1 and A2 two online algorithms for the problem satisfy AALG(n; A2) AALG(;; A1) for n. + k u and AALO(;; A2) > ALLO(;; A1) for n = k. Then, we have ( A1) LA A2) > AALG(K; A2) AALO(;; A1).
Proof. Consider the set S = (1), which is an element of M. The cost incurred by the algorithm on day n can be expressed
AALG(T) = (1 (1-Fm-1(5)) ((S) + (f(S) g(S)) (S).
where the first term on the right-hand side represents the expected rental cost, and the second term represents the expected purchase cost. From the above expression, we can derive the purchase probability on day as (S) (TA (1 -0 ( (()))))))))(((()))))))))))())))) g( - g(S)). Applying this formula to algorithms A₁ and A2. we obtain the following observations
(1) When i < or u, we have (S; A1) = pi(S: A2) and F((S; A1) = F.(S; A2).
(2) When i = k, it holds that (S: A1) < (S; A2) and F;(S; A1) < F;(S; A2).
When l: i < u, similarly, p55 A1) < (s(S; A2) and F:(S; A1) < F:(S; A2).
As result, we obtain
Pu A1) (S; A2) > (S; A2) - -P: (S; A1).
and therefore, the following inequality holds
AALG(u; A1) AALG(u; A2)
(Fu- (S; A2) F.. (S: A1)) ((S) + (f(S) (pa(S; A1) -Pa(S; A2)) (S: A1) F A2)) g(S) + (f(S) -(()) (p: A2) (5: A1))
AALG(K; A2) AALG A1).
This concludes the proof of Proposition 4
For a purchase path (S1, ......, Si), if the purchasing process follows the AC (o; (r) strategy, then any super item that lies along the incremental optimal offline cost trajectory satisfies the three properties stated in [emark[2] Therefore, to establish Proposition|[] it suffices to show that the A (a;; a:) strategy includes the optimal strategy for purchasing a single super item, provided that the incremental optimal offline cost associated with this super item satisfies the conditions specified in Remark 2
For a purchase path S2y... St). if the purchasing strategy adheres to AC (a) then any super item that lies along the incremental optimal offline cost function AOPT(T) satisfies the following three properties:
Remark 2.
(1) Non-negativity: APPP() 2 for all T TEW N+
(2) Monotonicity: (TP is non non-increasing for T > 1.
(3) Stability: There exists a time Topr E N+ such that ΔOPT(T) 0 for T = Tops. and SOPT(T) for all T 2 Topr + 1.
22

---

To facilitate the analysis, we assume that the purchase of super item S; begins at time = 1. Since part of the cost optimal offline cost (TP is monotonically non-increasing for n. > 1. To prove Proposition | it
may be attributed to the purchase of a previous super item, the incremental
suffices to establish the following proposition (Proposition 5).
Proposition 5. Consider a super item S with purchase price f(S) and a rental rate g Suppose the optimal offline function for this super item satisfies the conditions outlined in Remark Let the competitive ratio of algorithm A be A1). Then, there exists an algorithm Ag that satisfies the AC(o; a)) strategy and whose competitive ratio satisfies CR( (R(A2) S CR(A1), i.e, algorithm A is not superior algorithm A2-
Proof. If algoorithm A₁ satisfies the AC (o; a)) strategy, the proof is straightforward by taking A A1
However, if algorithm A₁ does not satisfy the AC (0;; o:) strategy, then there must exist day i < TA such that
AALG(K; A1) < CR(AA) AOPT(k).
(5)
Without loss of generality, assume that is the first day for which the above inequality holds. To make the equality in Eq. (5) hold, we consider shifting the purchase probability: increase it day l and decrease it after day k. There are two possible cases when making this adjustment.
Case 1:
Reducing the purchase probability after day i is not sufficient to achieve the equality. This means that even if we increase the purchase probability on day k to the maximum extent (i.e., make the cumulative purchase probability reach by day k), the cost incurred by the algorithm day still does not reach the required budget. Mathematically, this implies the following inequality holds
CR A1) AOPT(k) -1- FR-I (S:Ai)) A1)) .g(5)
1- FS;
(6)
((8)
Eq. (6) can be simplified to (1 (1- P-1(;:: A1)) f(S) < CR(A)) AOPT(A).
Based on this, we can construct new algorithm A2 with modified purchase probabilities as follows
(S: A1),
if n < k if k if k.
(S; A2) = 1 F. 1 A1),
0,
With this construction, algorithm Ag satisfies the AC (o; ai) strategy, and we also ensure that CR(A2) S CR(A)).
Case Suppose possible to make the equality in Eq. hold on day by reducing the purchase probabilities after day k. This implies that
(1 (S; A1) f(S) 2 CR (1) ΔOPT(K).
We then construct modified algorithm A with the following purchase probability allocation
(1) Pn(S: A() = (S: A1), for n < l: or +
(2) PS(S; (()) = 0, for l S < k: -
(3) (S; A()) CR(Ag) ADPT( (R(AA))AOPT(A
(1-F (8; A11),((s) for n = k.
[(8)-((S)
(4) P.. A())
K+T 1 A1) (P: AO) (s; A,)), for n
The integer T is chosen to ensure the feasibility of the probability adjustment, satisfying
(S: A1) ps A ps(S: A1) and Σ
P,(S: A1) 2 Ps(S; A Ps(SS A1)
j=
j=
23

---

Algorithm A is valid since it satisfies the following conditions
Σ Pm:: AC) 1, and 0 S (n: AC)) s 1.
We now proceed to prove that CR(AO) CR(AA) case by case. Subcase (1): for n < k.
According to the construction of algorithm A we have
A A = AALG(n; A1) CR( (R(A ΔOPT(M), for < k.
Therefore, follows that
ALG(n; A = CR(AA) OPP((M), for <.
Subcase (2): for = k.
AALG(K; A = (1 - (k- A (( (s:))) A =
Thus, we obtain ALG(K; A0) < CR(Ai) OPT(K). Subcase (3); for n = k + T.
According to Proposition reallocating costs from later stages to earlier ones results in lower total costs. Therefore, we derive
ALG(K T: A ALG(K T: A1) s CR(At) OPT((K +).
Subcase (4): for k In this case, we have
ALG(n; ( =
AALG(j; 1 = ALG(A: + T A()) +
Σ
AALG(J: A
j=1
j=k+++1
< ALG(K + A1) +
Σ
AALG(j; A1)
j=k+++1
(R( OPT(n),
for k+
Subcase (5); for t < < k + We prove that ALG( A1)) < CR (1) (n) by contradiction.
Assume there exists some with A < < k + such that ALG(m; A() > CR(A1) -PP((n).
Without loss of generality, let be the smallest integer greater than l for which the inequality fails. Therefore, we have
ALG (1)) < CR(A1) OPT(n 1), AALG(n; A()) > CR(Ar) АOPT(n).
According to the construction of A2), we know
AALG(M; (1)) = AALG(n + 1; (4)) ... AALG +
- 11; 14) & AALO + AW)).
By the monotonicity of ΔOPT, it holds that (P 2 AOPT(n 1)2 ... AOPT(k: + 7).
Hence, for all such that < k 7. we have AALG(i; A > CR(Ai) AOPT(i), which leads to ALG(K: + 7; A > CR(Ai) OPT(k +)). This contradicts the conclusion ALG(k: + A(1) < CR(At) OPT(A r). Therefore, it hold that ALG(n; A < CR(Ai) OPT(n), for < k

---

In summary, we have shown that the competitive ratio of algorithm A does not exceed that of A1. i...
CR(A I (R)
By iteratively applying the above procedure, we can construct a sequence of algorithms A A , A(d), where the final algorithm ( satisfies the AC (0;0) strategy. These algo- rithms satisfy the following conditions
CR(A1) 2 CR(A 2 CR(A 2 CR(A(d)).
Let A2 A Then, Ag satisfies AC (α;a) strategy and CR( A2) S CR( (A1) Therefore, Proposition is proved.
Given the result Proposition 0 we now proceed establish Proposition) 2 and Proposition shows that achieving smaller target competitive ratio requires longer duration to complete the purchasing process. Proposition 3 demonstrate that an AC(a:; a)) algorithm with a completion time
exceeding Tor does not exist.
B.2 Proof of Proposition 2
Proof. If algorithm A buys only S. day following purchase path o, then that day, only the super item S; has non-zero purchase probability, while all other super items have a purchase probability of O. Consequently, the cost incurred by algorithm A day given by
AALG(n; A) = f(S.) (S, A) + (1 - (S; A)) g(S:) + Σ ا g(S)).
(7)
If algorithm A is able completely purchase St on day and proceed the next super item, then set (S;; A) = 1 F 1 A) and let
AnLG(m; A) BALG(M; A) (S.) Pm A).
(8)
Since the purchase path is fixed and identical for both algorithms A₁ and A2, it is sufficient to demonstrate the conclusion for |M| The purchase probability on day can be expressed
based on Eq. 7 and Eq. (8) Consider the set {1).
(S) = AALG(T) - Fn Fn-1(S)) g(S)
f(S) g(S)
Since 01 < Or2, it follows that AALG A1) AALG(T; Ag). Consequently, we have p.. (S; A1) (S( A2) for n < TAg Algorithms A₁ and A2 satisfy the following conditions
Σ Ta p: A1) 1; Σ
Taa Ps A2) 1.
Thus, TA2 S TA,
B.3 Proof of Proposition
Proof. Consider the purchase path a = (S1, .2...., ..)........ We use proof by contradiction. Suppose
that the completion time of algorithm A exceeds Topr. In this case, we have Frum (Si; A) < 1. Let
n Tee + 1,
AALG(n: A) = Σ [f(S)) (S; A) + F, s(S.)]
1E1-11
+ f(Si) Pn(S; A) + F, (S; A)) ((.)
Σ [f(S)) (S (1 (S;; g(S))
(E1-1]
+ (f(S)) ((S)) pn (St
Fram (St; A)) g(S))
Term
25

---

Since Term 1 2 0, Term 2 2 0 and Term 3 >> O, we have AALG(n; A) > 0, while ( 0.
This implies An; A) aAOPT(n), which contradicts the oC a strategy. Thus, Proposition holds.
C Proof for Theorem
The proof of Theorem is established through Lemma 2 Lemma 4 and First, Lemma establishes that for a given purchase path σ, the strategy DAC(ar achieves optimality. For given purchase set, Lemma guarantees the optimality of the purchase order. Building on this result, Lemma further demonstrates that the optimal strategy for a CSR with a given purchase probability q equivalent CSR characterized by an augmented purchase path 7 (q). This augmented
path (q) is constructed based on the purchase probability vector and the purchase path set E. Consequently, the strategy DAC(gBR (q)) is guaranteed to be optimal for a CSR with purchase probability q. Moreover, Lemma 5 establishes that the competitive ratio (<)""(g)) is convex
function the purchase probability q. This convexity property allows the efficient computation of the optimal purchase probability q" using numerical optimization methods.
C.1 Proof of Lemma 3
To evaluate the performance of the algorithm under disjoint y, including randomized paths, consider strategies satisfying
( A) = a ΔOPT(n), when n S ToPt.
(9)
AALG n2; A) 0, when TOPT,
which not necessarily constrained to fixed purchase order. Define strategy A such that Diar Pn (S.; A1) 1 and AALG( A1) a a. -AOPT(n)). for any day n N+ and E [[]. Suppose strategy A does not follow an ascending order of the buy-to-rent ratio. That is, there exist times k, u,
and super items S, Sy such that & < f(S.) s(S:) and pk A1) > 0, Pu (Sy; > 0. Let
S(S s(S,)*
S Pu(S;; A1) and 82 f(8,) (()) > Define a strategy Ag such that
((8.)-g(S.)
Pr A1),
for n + k, a and E [4].
(So: A1).
for n = k, a and v E [1] v + i,
(S. A2)
Ps(S; A1) - 61, (S,; A1) + 82,
for = k; for
(u(S A1) + 81, Pa (S5; A1) 82,
Then the strategy A2 is well-defined, i.e., Eie (S; A2) and AALG(K; A2) =ar AOPT(k). we will prove that strategy A2 outperforms strategy AI, i.e. AALG(n; A2) on AAPP(() for any day E N+
i.e.,
(1) For n S is evident that AALG(n; A2) -11 AOPT(n).
(2) For & < n < u.
AALG(n; A1) AALG(n; A2)
(1 =
A (|00:://........--------AAA)AA)- (1 F, (S;; A2)) ($5) - -1 (.- (S;
= -- -111((S)) + 62g(5,)
(f(())-gff - (())) g(S,) -(()) 61.
f(S,) (((,)
Since f(S.) ((S) it follows that f(8:)-9(S;) > 2(S.)
Thus, AALG(n; A1) AALG(n; A2) > 0.
g [
7(8))-9(3,)
g(S,)
implying AALG nn; A2) AALG(n; A1) 01 AOPT(n).
(3) For n u, similar to (2), we derive the following:
AALG(n; A1) AALG(n; A2) (f(S.) g(S.) f(S,) (f(S,) -(05)))))ss))))
8
f(S,) g(S,)
26

---

018
Given that S(S.) ((5)) it follows that (SS)) [(S,)*
1.
By multiplying both numerator and
110g)
denominator by S(S.) [(S;), obtain
( (f(S;) - ((5,)) f(())
>
Thus, AALG(n; A1) AALG(n; A2) > 0, which implies
AALG(M; A2) < AALG(m; A1) = AOPT(n).
(4) For n > it is evident that AALG(n; A2) 01 AOPT(n).
In summary, strategy A2 outperfonms strategy A1. i.e., AALG(m: A2) 01 AOPT(n). for any E N Subsequently, by adjusting strategy A2 to move the purchase sequence forward according to the order of probabilities until AALG(m; A2) 022 AOPT(n), it follows from Proposition 5 that 02 I (1,. By iteratively applying this method, the optimal strategy is obtained by arranging items in ascending order of the values f (S.)) This completes the proof of Lemma
C.2 Proof of Lemma
Given q, the CSR problem of designing the optimal randomized algorithm to minimize the competitive ratio can be formulated according to Eq. ( as follows
min a a21.p
T I
s.t. Σ ΣEX
Σ (S) (S [ (1)+ o.)) ()(())((())))))))))))))))))))()) S a OPT(T), VT E
n=l 1=1 SET
(10)
Since /P (((a,))) r(g). where ((a,); {a((;))) Eq. 10) can be reformulated as
min O S.L. Σ Σ (S(S) (S) + (1 (.)) ((S) S a OPT(T), VTEN (11) a21.p
SEx(g)
where (S) represents the probability of purchasing super item S time n. and Fx
Given a purchase probability q = (a(a)).g((2)) ((.2).......e.......... 1(()) )). Eq. III indicates that the problem
reduces to determining the optimal purchase probability for the set 7(q). According to Lemma 3 the optimal purchase path is the augmented purchase path B8 (q). Thus, DAC(1 "* (q)) is optimal for a given purchase path probability q. proving Lemma
C.3 Proof of Lemma
For all purchase path probability æ,y E [0, where
x( ... ri)
and = (u(01), -(3(01), ((0)) ,( satisfy Σ z(0,) = 1 and Σn v(os)
1. Let algorithm A where (x) = (I( Spj). -1) ............ [ p. Spi) and 7 (v) (1(1)), ( Spa).... ...
(AC() (x)) and algorithm B = DAC(1 (z)).
Evers Ea x(o)
and Di
Evers v(0) is the sum of selection probabilities from paths that contain super item Shy. The competitive ratios are a = a(1 ER (z)) and 02 (v)))
[0, z io + (1 - l) = C DAC(,,BR (z)), where (z) = (T(² Su)) T(pp)) ; ... T [(pp)) Sppi)) and 2 =
=(ar))). Define algorithm
Eoe =()) ) is the sum of selection probabilities from paths that contain super item S.a-
We will prove that (z)) a1 + t)a2.
27

---

Define algorithm 11 purchase probability is 2 = tæ + (1 t and the purchase probability of the 1.2... ... D) on day is, for any 1,2....... D.
super item [ (2p. S(1)
1.1
Pr (T())), Sw)): = t + (1 t) M[]]
Pu ([(])))()))) A)
(1 - t) 014
Pn. (I()) S4)); B)
t 1 + (1 - t) M1
where Pr (T( S(i): Ci) denotes the probability that algorithm buys [(]]] St:) on day n. Consequently, the cumulative distribution function of the super item S(1) on days is, for any i = =11.....,
t t
Fn (I(2)) C1)
Ci) =
Fn (I(4()) Stq): A)
t &Φp + (1 - t) Dn
(1 - t) 0/4
Fn (1(1)) S(a): B).
1.81 (1 1) Dn
[0, 1] and Fr.. (1(2)) Sp1): A) 1, Fr,n (1(0 S/q): B) = 1, we have pn (I(2)). St)): C3) E [0.1] and Fiax(TTa Toy) (1())) Sp;): Ci) 1. Therefore, this definition of algorithm C₁ is reason-
Since Pn (1(11), Sta): A) Pn (1(9)) Sta): B)
able. The daily cost for algorithm C₁ is
AALG(m: Ci)
Σ
Fn((()) St)) Ci)) ((Sn)) + 2ي f(S()) P. (I())) C))
1=1
Σ Lt:g ((1 (T A)) (( + f(5 Pn (T(T)) Sky): A))
+
_ -1-18 t) ((1-F,m Fn Sy): B)) g(Spg) + f(S Pm Pr (1 Spy): B))
Based on the definitions of algorithm A and algorithm B, we have
D
Σ ((1 FT Spy): ()) ((((g) + -ي f(S(g) - Pa Pr Sp):: A)) = on AOPT(n)
1=1
(12)
(11 (T B))ūn) ((S(g) + im f(S pm (T(() B)) 02 AOPP(()
(13)
By multiplying both sides of Eq. (12 by and both sides of Eq. 13 by 1 - t, and then adding the resulting equations, we obtain
AALG(T; C1) = (tar + (1 t)a2) )- AO)T(.).
(14)
Thus, algorithm C1 achieves a competitive ratio of ta + (1 - t)ay with a purchase probability tx + (1 t)y. According to Lemma DAC(y (2))) is the optimal algorithm for the purchase path probability z, resulting in (x)) S fon + (1 - f)a2. Consequently, the competitive ratio a(7BB (q)) is convex function with respect to q.
D Optimal algorithm for CSR with upgrading
In this section, we present results related to CSR with upgrading. Specifically, we demonstrate that the optimal purchase strategy corresponds to DAC (o"), where a² = (ST Sg. Sx represents the purchase path of the optimal offline algorithm. Furthermore, we establish that the upper bound on the algorithm's 's competitive ratio is e/(e 1).
28

---

D.1 Problem setting
In CSR with upgrading, a purchase path is a sequence of super items (S), S2...., Si) with non- decreasing purchase cost, i.e., f(S:) S f(S,) for all i.j (1, and S j. Once the super item Si+1 is purchased, the algorithm replaces the previously purchased super item S with S++1- The expected cost of an online algorithm A is
(L; = ΣEΣ NET
(() ((())))((S-11))) (m: lo)
vE() OF NET
expected purchase cost
(15)
ΣEΣ g(o) -- (L- (g(S)) 91555)))))))
nE(T] iELi
expected rental cost
where (S | 0) ='== (: σ) is the cumulative distribution function of buying super item S by day n when purchase path a is chosen. The first term represents the expected purchase cost, where q())) (f())) f() Pr(S, σ) denotes the expected cost incurred by purchasing S; on day n when the purchase path a is chosen. The cost of purchasing S; is f(;) f(S--1) 1) due to upgrading. The second term represents the expected rental cost, where 1 - (S, a)) denotes the probability that S. has not yet been purchased by day n. Additionally, under the purchase path a, when F,, (S, ()) < 1. The differences in ALG(T; A) between CSR with upgrading and CSR lie in the purchase path Σ and the structure of the purchase cost.
(S σ))
In CSR with upgrading, the player can buy super items with incremental purchase cost over time and still benefit from combined purchase discounts. For example, a player switches from a Microsoft 365 basic plan to a personal plan, they just need to equivalently pay the difference in cost between the two plans. However, in CSR, a player must pay the full price for each additional item purchased. If the player initially buys subset of items and later decides to buy additional unpurchased items, they must pay the full cost without any discount regardless of previous purchase.
Comparison between CSR and CSR with upgrading We use simple example compare CSR and CSR with upgrading. Consider a scenario involving two items. The purchasing decision depends not only the cost and potential discounts associated with bundles but also on the constraints imposed by the online setting. Figure (7a) shows the purchase paths for buying items as one combination (Path 1), buying them separately (Path 2), and the optimal offline path (Path 3) as the skiing season progresses. In the CSR with upgrading setting, players can adopt an adaptive strategy by first purchasing one item and later upgrading the bundle, allowing them to exploit discounts when advantageous. However, in CSR, once an item is purchased, upgrading to the bundle is not feasible without incurring the full bundle price. Consequently, players must commit to either Path or Path 2 at the outset, making it challenging to optimize decisions without prior knowledge of future needs. The CSR problem can result in competitive ratios exceeding e/(e- (1( 1) due the irreversibility of the purchase paths, especially under moderate discount factors, as dacision-making becomes more complex in this case. In contrast, CSR with upgrading consistently maintains competitive ratios below this threshold and
aligns with CSR only in scenarios involving extreme discount rates [ 19 31
D.2 Overview the main results for CSR with upgrading
For the upgrading version, the expected purchase cost of acquiring all base items is fixed, regardless of the order of purchase. As result, the only cost difference between strategies arises from the expected rental cost. At any given moment, the optimal online algorithm will choose to buy the super item that minimizes the current rental cost through upgrading. Since this super item is fixed, the selection process must follow a fixed purchase path rather than being randomized. Based on Lemma 2 the optimal purchase strategy must adhere to the OAC (a) strategy. Furthermore, we show that the optimal purchase path is the same as the purchase sequence by the offline algorithm a² - Si., Sk). which solves the Eq. 2 as the skiing season expands.
Theorem Given information setup I for the CSR with upgrading problem, OAC (a*) is the optimal online algorithm and achieves the optimal competitive ratio a(o").
29

---

Combited Purchase Path iPash 1]
CSR with Non-upgrading
Purchase Path (Path-3)
CSR with Upgrading
f(11) + f(2)
Optimal Purchase Path (Path
Competitive Ratio
1.63
SkI
(((.2))
1.59
((2))
el(e-1)
1.55
Time
0.8 Discount Factor
0.8
(a) Purchase paths
(b) Competitive ratios
Figure 7: (a) The figure illustrates three offline purchase paths: Path I (blue arrow) represents the combined purchase, Path 2 (green arrow) corresponds to purchasing the items separately, and Path 3 (red arrow) denotes the optimal offline path, where item is purchased first, followed by the combination of items 1 and 2. In the CSR with upgrading scenario, all three paths are feasible. However, the CSR scenario, the player is restricted Path Path 2, as upgrading not allowed. (b) The upper bound of the competitive ratio is computed for two items with prices in the range [20, s0), where the combined purchase price is represented as the product of a discount factor and sum of the individual prices.
The optimal offline algorithm determines which items to buy rent at the beginning of the ski season by knowing the number of skiing days in advance. The elements in the set o represent the purchasing strategy that incurs the least cost the skiing time increases. For CSR with upgrading, even though the number of skiing days is not known in advance, the algorithm can reverse previous decisions through upgrades. The optimal online algorithm will continuously upgrade its purchases to ensure that the current cost grows at the slowest possible rate. Therefore, the optimal purchase path should be a². We formally prove this in Appendix [.3
The optimal competitive ratio a<a") ) of OAC (a") depends on the information setup a complicated manner, and it is challenging to obtain closed-fomm solution. However, the following lemma shows that a( ((")) ))* is upper bounded by e/(e - 1), which is the optimal competitive ratio of the classic ski rental problem.
Lemma 6. For any information setup I, OAC (a*) CSR with upgrading achieves competitive ratio upper bounded by e/(e- 1).
Compared to classic ski rental that buys or rents all items in a combination, CSR with upgrading achieves better competitive ratio. This arises because, although both offline and online algo- rithms gain flexibility in fine-grained purchase options to reduce overall cost, the online algorithm experiences a more significant improvement.
D.3 The optimal purchase path
In this section, we demonstrate that for CSR with upgrading, the optimal algorithm follows a fixed purchase path o² (Theorem We prove Proposition [ Proposition 2 and Proposition for CSR with upgrading based on the same principle, with necessary adjustments to the rental rate and purchase price for CSR with upgrading.
For CSR with upgrading, the cost of purchasing all base items is fixed f(M), regardless of the purchase order. The difference in cost among different strategies arises from the rental cost. Intuitively. when the expected purchase cost up time n. is Cn. the optimal purchase strategy should select the super item that minimizes the rental cost while spending Cn on purchases. Consequently, the optimal purchase strategy follows fixed purchase path and adheres to the DAC (a) strategy, as demonstrated in Lemma 2 The next step is to determine the optimal purchase path. An intuitive idea is to follow the order (S), St S7 ......, 5%x in OPT, as OPT will always select the super item that minimizes the current cost. We prove this conclusion stated in Theorem
30

---

Proof of Theorem 3 We define the augmented set of super items is defined as ((g) == {I(q(o), ST) "") where ( ST) represents new super item containing the same base items as S but with a purchase cost of ((a)- f(5)) and a rental rate of q(a) g(S). For simplicity. we refer to S as S. Thus, for CSR with upgrading, all randomized strategies can expressed as fixed purchase path (T(((o)) So). (() S1), T(q(02), S2)..... I(((a)), ( St)), where So = 83 and for all j E {0, 1, 1. ......... with i E j. it holds that g(o.). f(5.) S g(a;) f(S)). Additionally, ((or) = 1 and S {M}.
At this point, the problem transforms into an CSR problem with super items to be se- quentially purchased. where the purchase cost and rental rate of the i-th super item are given by ((0,)= f(S.) ((0-1)) f(S:-1) and q(o,) 9(S,) ((0,-1) g(Si11), re- spectively, for i [1. The purchase order follows the sequence = 1, I....... In other words, the problem reduces to minimizing the CSR problem with the purchase order (I(g(11), St))(r))) So),
S2)/T(((1))) Si...... ( ())/T((()-11))5) S(-))), where (())) = S,= (M), and (t) Si-1) denotes super item with a purchase cost of ( f(S.) g(0,-)) f(S.-1) and a rental cost of q(o;) ((S)) q(o,-1) g(S.1)).
By Lemma the optimal purchase path can be recursively characterized as
[(S.) 1() ((.)) - 9(
f(S.) /(6--)) i= 1,2,,,...
S, arg min S.
(16)
This result can be rigorously established via mathematical induction. When
((11) ((r))) f(So)
81 = arg min S
((01). (f(1)((()))))))))))))()))) > ((oo) f($o)
((o1) ((n))-((53) 9(())) - ((0)) ((S))
(((() ((S1) - g(So)
= arg min Si
f(S,) > f(Su)
where we set (()))
because S the optimal purchase set.
Assume the characterization holds for i - 1 2 1. For i, we have
((o.) ((.)) g(o--1) (((--))
S, = arg min S.
q(a,) ((S.) ((0,-1) s(S,_1) ((a:) ((S)) > a(oi-1) 1(5m-1)
((0,) f(S)) 1($
g(o:) g(o:)- -(()) s(8..))
arg min S.
a(a:))9(33 9(8,_1)
/(S))- - ((S-1)
f(Si) > 5(5--)) 1
arg min S,
g(S.) 9(S,1)
The last equation holds because if both c(o,)) -((!")) > f(S,1)) and g(o.) s(S! > f(S,1) hold, and
s(S f(s(2))
)(S
o(S!2))²
then 5(2) is strictly better than s(1). In other words, the selection of S, is independent of the value of ((a,). Therefore, we set q(a,) 1, as S, represents the optimal choice at this stage. This completes the proof of the claim.
Hence, by induction, the recurrence relation in Eq. (16) holds for all i 2 1. This relation recursively determines the sequence (Sj, S St.,, S;).
D.4 An e/(e - 1) upper bound for CSR with upgrading
To prove the upper bound of e/(e 1) on the competitive ratio for CSR with upgrading (Lemma 6). we show there exists an algorithm for CSR with upgrading that is e/(e - 1) competitive. DAC(a" is the optimal online algorithm for CSR with upgrading and thus a(σ) I <e((e- 1).
31

---

Given setup I
f.9) of CSR with upgrading, we define K classic ski rental problems using
the purchase sequence o² = (Sg. St. Sj...., .i)) derived from the optimal offline cost. Each
information setup is defined as I2 = (Mi: (t) for i E 2, ,...... K), where [M.il 1. The
purchase cost (MM)) = f(S)) (( and the rental cost is (M:) = g(5))= - - ((( The optimal offline cost for setup I, is given by
OPT I,) min { (9(()) 9(S,-1)) .T.() f({;-))
(17)
When the algorithm buys the i-th super item in the OPT purchase sequence, it is referred to as state i. Unlike CSR, which has K + 1 states, the classic ski rental problem has only two states: state 0, when the item is rented for the entire duration, and state 1, when the item is purchased at the beginning of the ski season. We define ( (A, as the probability of being in state i at time n for algorithm A.
Let AZ denote the optimal randomized algorithm for information setup I,, i {1, 2..,.... competitive ratio of this strategy is known to be e/(e-1) for each instance i. For CSR with upgrading, define algorithm A" satisfy the following conditions: among multiple combinations of purchases. only the sets S other combination being zero. The probability of being in each state is given by
... KJ. The
S St
......, Sk are likely to be purchased, with the probability of purchasing any
(A*, = p/o (Ai, (I),
1,2,..., 2f (A", I)) = (A,, Ii) ((0 (A1+): = 1,,, .,,,, K 1, 1,
(A*, II- (A Ix).
Since upgrading is allowed, algorithm A' at time must be in one of these K + 1 states. The cost of algorithm A at time n is
K Σ 1=0
K (A')))
(L: A²,Z)=
p (A',
ΣΣ
gMM)
(18)
where the first term represents the expected purchase cost until day n, and the second term represents the expected rental cost until day n.
We then show that the algorithm A defined above achieves a competitive ratio of ef/(ee1)) 1) (Lemma To establish this result, we prove Proposition 6 7 and [] Proposition deemonttrtees the soundness of algorithm A Proposition 7 states that the sum of the costs of K online algorithms A is equal to the cost of the online algorithm A Proposition g clarifies that the sum of the optimal offline costs for these K instances equals the optimal offline cost for the CSR with upgrading problem.
Proposition 6. For the randomized algorithm A defined above, the following conditions hold
(1) (A IJ) 2 0, i E (0.1,2....,KY
( (2) ΣK Pm (A 1.
Proof. To support the claim (1), we need to show that (1) (A; 2 1 (Ait), I++1) for i = 1,2....,K K - 1. Given that A is the optimal randomized strategy for the classic ski rental problem, Proposition
9 proves ph II) = (1-1/s.) - and indicates that pn (A,,Ix) is monotonically
(1-1/=0)--1
(A: decreasing with respect to 6.. Since t, S t441 for i = 1, ...... K 1, it follows that (1)) ((; II) Z
(1) (A)41) For claim (2), we derive the following
K
K-1
Σ
(i) Pr (A",I) 1) =p (A].I)) + ==0
Σ
1000 (A), - ph (A, I++1) + (AA
1=1
11) + 0/0 (Ai, 1.
Proposition 7. ALG(n; A*,I) = ΣK ALG(n; A, An N
32

---

Proof.
The cost of algorithm A7 at time n is
ALG(n: = - +
Then, have
K
K
K
Am: AT = >
P. (A), +
Σ
(o(s)) - 9(( pp II).
==
Term (1)
Term (2)
For the first term of Eq. (8) we have
Pa (0'
K-1
-// (A1,I)) (A1, ((()) +
Σ
-
- 1h (1 ((S)) + +/ (AK: Ik) (((k)
1=1
K
K
(A1, [(S)) + Σ
Pn
- (AT, (J(5)) ((S)-1)
Σ
p (AJ,Z) (J(S))- ((S)-1)
1=2
1=1
=Term (1).
(1) For the second term of Eq. [8), by utilizing the relationship pa (A, IT) 1 (0) (A,,I, Iz) for we obtain
i E f1.2...., K}.
K
(A (AA.I))((MMM.
t=
K-1
Pj (AI g(M)) (5)++ + Σ (A), -Af g(M) (M\S (;) (Ax, 9(M (7s)
i=1
K-1
p, II) (((k)) + Σ
(p)
10)
PA) g(M) \ \.57)
K
(0) (A, (c)(s)))))))))))) ((S)_1))
Term (2).
i=
Therefore, it can be concluded that the cost of algorithm A" is equal to the sum of the costs of the K algorithms for i E 21,2.....4 K}.
Proposition 8. OPT(n; I)= Σ OPT(n: I,), Vn N
Proof. Let i(n) be the state that optimal is in at time n, where E N+ Then, when i S i(n). OPT(n; I.) = f(S.) f(S,-1); when i > i(n). OPT(m; = (g(5)) - g(S.-1)) n. We can get
that
K Σ
i(n)
K
OPT(n; I,) = Σ (S(S.) ((S:- +
Σ (n(())+1
(g(S)) - g)(: n
i=1
i
= =((S(())) - -(S)) + (g(Sx) ((S((m))) n
=f(S(()) + 9M \ Siim)) n2
=OPT(n: I).
33

---

Proof of Lemma 6
Since each algorithm A; has upper bound on its competitive ratio of e/(e 1), we can derive the following relationship
ALG(m; A²II)
Σ ALG A,, S
OPT(n: I,) OPT(n: Z),
which means that algorithm A has e/(e 1) competitive ratio.
D.5 Proof of Proposition
To prove Proposition 6 we establish Proposition 9 which outlines some properties of the optimal randomized strategy for the classic ski rental problem.
Proposition 9. For a classic ski rental problem I (.,). where M = (1). The rental rate is given by x{{1)) = r and the purchase price is [((1)) = b, with b/r E N+ and bfr > 1. The cumulative distribution function of the optimal randomized algorithm A on day (i S b/r) is given by
E((1); A7) (1 (1-r/b)
(1 (1- (1-r/b)-b/r-
Moreover, Fi({1); A for S b/r monotonically decreasing with respect to b/r.
Proof. The probability that the optimal randomized strategy buys on day is given by
12 for the classic ski rental problem
i i b/r
P (f1): A")
0,
n b/r
When s b/r, this represents geometric series with common ratio of b/ r). Therefore, have
F(L1); A*) P1 ((1); (1- (1-(6/ (1- (D-r/b)-b/r 1
(1 (1-r/b)-i-1
1- 1-(b/b-r))
To demonstrate that F. ((1(1: A*) for S b/r is monotonically decreasing with respect b/r, define the function F(n) as follows
(1 1/n) -
(n/(n 1))²
F(n) = (1 1/ n))
(n/(n 1)) 1 igisnnieN
We just need to demonstrate that the function F(n) is monotonically decreasing with respect to n (n 2 2), establishing the desired property of P.([1;; A*). Define two auxiliary functions: fi fi(n) = (n/(n 1))s, f2(n) (n/(n 1))" Then, we can express F(n) as
F(n) (1n))
f2(n)) -1
Then, compute the derivatives of fi (n) and f2(1t)
(n)
(n) dfz(n) fz(n) In n dn n 1)' dn
1
Using these derivatives, we can express the derivative of F(n) as follows
dF(n) (n)
1 n 1 n 1 1
dn nnn - 1) (fz(n) 1) ff(n)((i
In(1
By applying the inequality In(1 + - 2 -ي 2n- obtain
dF(n). (1))) dn
i(n (nn-()((( ())(()(((()) 1) nen 1)
34

---

Then, we derive the expression for n(n (n),
1
n(n 1(n-1){F((m) = (ff(()(f1(n)) - - - i(n -) -1)
2
uti
= 2 i(n i(n- -1)- 11)
n2
n (n=1)
n1
71
11
- i(n - 1)
n2 n-
2
17
We simplify further
n(n - 13)
n-
11
i(n - 1))
71
i(n 1)
11
2
12-1
2
n-
n i(n 1))
71
in - 1)
11
71
2
n
2
n-1
(6 i(n 1))
n
71
n
1
n
Since - i(n 1) s 0 for 1 sis i E N+ and 2 2, it follows that
n - 1) F (n) (n/(n 1))²
0,
which implies that F'(n) S Therefore, we can conclude that F(n) is monotonically decreasing with respect to n for 2 2.
E Proof for Lemma
The proof of Lemma D can be decomposed into three lemmas, each demonstrating how the CSR
problem is reduced to one of the following problems: multi-shop ski rental M. multi-slope ski
rental [19 and multi-commodity ski rental 29]. For details on CSR with upgrading, see Appendix D Theorem
Proposition 10. The CSR problem be reduced the multi-shop ski rental problem by restricting the purchase path set Σ to single-element paths corresponding to individual shops. Consequently, the SOAC algorithm achieves the optimal competitive ratio for the multi-shop ski rental problem.
The CSR problem can be reduced to the multi-slope ski rental problem by restricting the purchase path a to a single path. Consequently, the SOAC algorithm achieves the optimal competitive ratio for the multi-slope ski rental problem.
Proposition 11.
The CSR problem be reduced to the multi-commodity ski rental problem by assuming that no combination purchases provide a discount. Consequently, the SOAC algorithm achieves the optimal competitive ratio for the mulli-commodity ski rental problem.
Proposition 12.
The online strategy of the CSR is characterized by two fundamental decision dimensions:
Purchase Path (a), .2...-; 71z)): This represents the process of purchasing all required items along multiple distinct paths.
Purchase Time (t(a) == {t(S se)): This defines the specific time t(S) | ()) at which super item purchased along the path a.
Compared to the classical ski rental problem, the CSR introduces two additional layers of complexity:
The decision-making framework expands from a single purchase path to multiple paths.
Path Dimension:
The decision process extends from single-stage to multi-stage decision- making, which requires determining when different super items should be purchased.
Time Dimension:
35

---

E.1 Proof of Proposition 10
Proof. In the multi-shop ski rental problem. a skier must decide how to ski for an unknown duration T. The skier chooses a shop i from set of shops {1, 2....... m) and can only rent or purchase ski equipment from that selected shop. Each shop offers daily rental price r; and a purchase price b, where rı, by > O. It is assumed that ii < ... < I'm and bj > by > ... > bm. ensuring that shops with lower rental prices have higher purchase prices to avoid trivial decisions. The skier's 's goal is to select shop and determine the optimal purchase time to minimize total costs, without changing shops midway.
In the CSR problem, consider a scenario where there is only one item and this item is combined with itself, resulting in different rental and purchase costs. Under these conditions:
The purchase path set E is restricted to single-element paths, where each path corresponds selecting one "super item" S -i}-
Each super item S, has a rental cost Ty and a purchase cost b, directly corresponding to the rental and purchase prices of shop i.
Thus, the purchase path set becomes Σ = ((1), (2)...., (m)). similar to choosing shop in the multi-shop ski rental problem. This demonstrates that the multi-shop ski rental problem is a special case of the CSR problem.
Remark 3 (Analysis of Path Irrevessbillity). In the multi-shop ski rental problem, changing shops midway during the rental period prohibited. If such changes were allowed, the problem would reduce to the classical ski rental problem, where the user would simply rent from the shop with the lowest rental price and purchase from the shop with the lowest purchase price. Similarly, the primary distinction between the CSR and CSR with upgrading problems is that the CSR problem disallows changing purchase paths midway. Allowing such changes would transform the CSR problem into the mllti-slope ski rental problem, as shown in Theorem
F.2 Proof of Proposition
Proof. In the multi-slope ski rental problem, the user needs to utilize resource for unknown duration. The cost of resource usage is determined by multiple states (or slopes) S = {0, 1,...,
......,, k). < by and ro > F1 > ... > Tkk where by = O. For simplicity, we assume that тą = 0. If ry * 0, an additional state can be introduced, defined as bb+1
Fach state has purchase cost b, and a rental rate r,, typically satisfying by < bj <
and 7R+1 = O, to accommodate this case. The user's objective is to determine a set of transition times (t1, .......,).... where t, denotes the time transition from state - 1 to state i. Transitions only allowed in the forward direction i -iit 1, and skipping states is not permitted.
To reduce this problem to the CSR problem, we restrict the purchase path in the CSR problem to single path a = (So, S1, S2 St). This restriction feasible under the assumption that each S; corresponds to base item containing only one element. In this case, there is no discount for any combination of elements, so the only valid path to purchase a. The cost parameters are defined as follows
The purchase cost of super item S is f(S:) b, - bi for E (l,...,k) k} and S(S)) = 0: The rental cost of super item S, is ((S)) = rr-1 - r, for i (1...., k) and g(O)) 0.
In the CSR problem, state i corresponds to the state where super items So, Si,..., S have been purchased. In this state, the purchase cost is Ej=o f(S)), and the rental cost is Σ Σド=+t ((3)) By the definition of the purchase and rental costs for the super items, we have
&
Σ ((S,)= - b.
Σ g(S,) = - J=
Thus, under this special case, the decision path dimension of the CSR problem reduces to a single path, making it equivalent to the multi-slope ski rental problem.
D
36

---

Algorithm 4 OAC: Extended Amortized Cost
1: Input: Information setup = fM. g): purchase path o; stopping criterion E; critical time THL
2: Initialization:
1, Olyax [(M), Otmin
3: Compute (PT(7) and OPT using Eq. (2)
4: Compute (P)( using Eq. (99)
5: Construct algorithm A ()
6: while Ommax Otmin > do
7: Calculate T'A using according to Eq. 11 and Eq. (20)
8: T' THL then
9:
Omax f
else
11:
Otmin f
end
13:
Update 4- (Orax + OEmin)
end while
15:
return O'max AC(a; O'mxx)
E.3 Proof of Proposition 12
Proof. The multi molti-co ski rental problem considers a set of items that must be utilized simultancously. where each item has its own independent rental and purchase prices. By imposing the constraint in the CSR problem that no combinations of items are eligible for discounts, the CSR problem can be simplified and directly reduced to the multi calii-commodity ski rental problem.
Remark 4. Existing research the multi-commodiiy ski rental problem has achieved optimal solutions only in scenarios where all items share the same buy-to auy-to--ent ratio. However, determining the optimal randomized algorithm for arbitrary purchase and rental price configurations remains an open problem. The algorithm proposed in this paper provides the first optimal randomized solution for the general mulli-commodity ski rental problem, thereby addressing this gap in the literature.
F
Supplementary Material for LA-SOAC
F1
Supplementary details of LA-SOAC
This section details the implementation of the LA-SOAC algorithm, presented in Section 4 We begin by outlining the core design principles of the algorithm, and then formally describe the mechanics of the algorithm.
The LA SDAC algorithm aims to optimize purchasing strategies based on machine-learned predictions. It takes hyperparameter À (0, 1) input and generates two diffferent purchasing strategies based on the predicted time y relative the optimal completion time Topr. The strategies are defined as follows
If y 2 ToPt, the algorithm prioritizes early purchases, setting the completion time to The = J.Toer..The This is different from a baseline approach without machine learning, which completes the purchase at ToPr-
If y < ToPT, the algorithm delays the purchase, setting the completion time TM. [T/2)/ /A].
An issue arises because the incremental cost ΑOPT(n) for > Topr. rendering it infeasible to track the optimal cost function (PT(n) beyond this point. To address this, we introduce an augmented cost function, OPT(n), define its increment (OPT(n)
APPT(n), (FT( Twer
n S
AmPT(n) =
(19)
n > t²
As established in Lemma 2 OPT(n) must be concave ensure the validity of prior theoretical results. The definition of (PT(n) satisfies this requirement, enabling feasible cost tracking. We propose
37

---

Algorithm 5 SOAC: Sorted Optimal Amortized Cost Algorithm
1: Input: Information setup I = (M, f.g); stopping criterion s; Learning rate: 7/; critical time Thi.
2: Calculate all disjoint divisions: = (71 12:1722-0 :
3: Sort divisions I' by BR: { 2,..... :
4: Construct 7 based on Eq. (4)
5: Initialization:
6: q = (g(o:)) +
at F(M)
7: for (
do for = ,,. do
8:
9:
Compute Gradient by Finite Difference Method
10: grad, Dq(os) CR (DAC (y (q)))
11: end for
Gradiemt Update
13:
4- grad
Projection to Simplex
15:
+ ProjectSimplex(q)
Onew CR (
17: if aa Onew & then
18:
Break end if
19:
20: a 4- Cleew
21:
end for
algorithm, denoted DAC, which modifies the strategy by substituting OPT(n) with DPT(n) in Algorithm while adhering to the specified conditions. Denote a strategy satisfying Eq. (20) as the AC strategy.
[
AALG(n; Ay; a ADPT(n), n TAy AALG(n; Ay;2) S a AnPT(n), n TAy
(20)
AALG(n; Ay;a) =0
if n. TAy.x
The implementation of the DAC algorithm is detailed in Algorithm The algorithm employs a binary search iteratively refine the parameter a within the interval [Omin Ormax] Initially, a set, and the AC strategy is constructed based on the input purchase path σ. The algorithm then calculates the optimal cost OPT(T) and the augmented cost (PT(T) using Eq. (2) and (19). respectively. Convergence is achieved when the difference between O'max and Ommin falls below the stopping criterion e. Then, by
replacing the subroutine SOAC in algorithm OAC with OAC, we obtain the modified algorithm SOAC.
F.2 Proof of Theorem
Proof. We analyze the performance of the ML-based algorithm case by
Case 1: 2 Topr In this case, the threshold determined by the ML algorithm is given by Tm. EXTRRR According Algorithm the algorithm ensures uniform ratio across decision points up to Thu:
AALG(n; A
Vn < [XT
ΔŪPT(n)
for constant Moreover, AALG(n; A )
0 for |T
When T 2 Top,, the cost of the offline optimal algorithm beyond ToPT remains constant, and the online algorithm incurs no additional cost beyond THL. The worst-case competitive
Consistency:
(LG(TuriA
ratio, therefore, occurs at Topr, yielding OPT(Tor)
which upper bounds the consistency ratio.
Robustness: We consider arbitrary T > 0 and analyze the robustness under two subcases:
Subcase 1.1: [ t"
38

---

In this regime, ADPT (n) (0PT(n) for n S [XT hence the cost ratio remains constant. The worst case again occurs at T = [XT giving a robustness ratio of ALG([ATar (:A) DPT([ATT J)
Subcase 1.2: OPT L*
In this case, the relationship (DPT()) = A)PT(n) still holds for n S t*, Beyond this point, (DPT(n) constant. Due the construction of Algorithm we have:
AALG(n; A A AnLG(n 1; A 2x
while the offline cost decreases, i... ΑDPT(n) 2 (nPT(n + 1). follows that
AALG(n:
A
AALG(n +1; A
ΔOPT(n)
ΑOPT(n +1
and consequently,
ALG(n; 1
EL=1 AALO(I; 1
E AALG(i; A02)
ALG(N + 1; A.2) OPT(n + 1)
OPT(n)
Di ΔOPT(i)
EET ΔOPT(T)
Hence, the worst-case ratio is again achieved at x [XT
Case 2: y TOPT
Let Tm
[ />] According to Algorithm
the following holds:
AALG(n; A
d, Vn S Tw.,
OPT(n)
and AALG(n; ( 0 for Tia.
Consistency: When n 1* the augmented and actual optimal costs match, i.e., ΔOPT(n) AOPT(n), which implies
AALG(m: A
d, Vn tt.
АOРT(n)
For t" < TML, (nPT(n) is constant. We can get that
AALG(n; (
AALG(n +1; (
I
АOPT(n)
AOPT(n +
and consequently,
ALG(M; A ((2)) DPT(n)
ΣE AALG(i; (2)
SI AALG(i; A
ALG(n + 1; (22))
AOPT(i)
Li=1 ΔOPT(i)
OPT(n + 1)
The competitive ratio is non non- -on-eecra,,,ng, with the worst case again occurring at ToPT-
Robustness: Since ΔOPT(n) = 0 for > ToPT, the worst case occurs when T = [T /A], in which the cost ratio of the online algorithm the optimal offline algorithm
ALG([Tr(2) (2)
OPT A1: A A
ALG([T (2) OPT A]: A (2)
OPT ([T))) /A])
OPT(TapT)
max ALG(Tor:: (1) OPT(TwT)
ALC Torr vi
In summary,
Algorithm
exhibits
consistency and
DPT Tam)
(L J:A gch
ALG THE
(A]:A (2) v.A
max
OPT(LATT
OPT
robustness.
39

---

F.3 Proof of Corollary [
Proof. In the classic ski rental problem, the optimal offline cost is given by OPT(T) = min T}. and the critical threshold at which buying becomes optimal is TOPT = b. For a randomized online algorithm A, the expected cost can be written as:
AALG(n; Ag:a)
Eii-1+b) (r((1)) +n- 1 E P(((L))
sc/m]
iE(M)
where P=((1}) denotes the probability of purchasing the item on day i.
Note that (PT(T 1. Therefore, (PT(n) for all n E N+ in this setting. Let h [gb] and
JaPt
I [b/A]. According to Eq. 20), the probability distributions under the proposed algorithm given as follows:
(1) When 2 b (corresponding to the algorithm A y:d
(b-1)
km
if S k otherwise.
(11((1))))
0
The corresponding target competitive ratio is
1- 1-
(2) When < b (corresponding to the algorithm {,))
if S otherwise.
Ph ((1))
0(1-(1-3))
The corresponding target competitive ratio is
1-(1-
Consistency. We first bound the competitive ratio when the predictor correct.
Bound 1: For the algorithm (1) U;
ALG(To A ALG(b; A vi OPT(ToPr)
[bb
[Ab]/A
(1 - (1/b)) 2b
[AN]
c
Bound 2: For the algorithm (2) ALG(TopT; A ALG(b; OPT(ToPT)
D:A*
b
S d
b
11 - (1/6))
1 1 -
1-
where the last inequality follows from Lemma 19 in 3.
Therefore, the consistency bound for both cases is upper bounded by I-e-X X
Robustness, We now consider the case where the prediction is inaccurate, and we evaluate robust- ness to prediction emrors.
Bound 1: According Theorem 2
ALG( ALG([XTOPT]] A ( OPT(TATOPT))
ALG([XTOPF]
OPT
9:d
1
1
Mell S - (A2-1100
[ATorl]
1 1
(1//))(A
1 c
Bound 2:
ALG ALG([Turr) A1; A (2)
y:
[b/1]
1//+1/6
1/A+ + 1/b
1+ 1+
<
<
<
OPT(ToPT)
1- (1
(1/b)) 6/A
1 [W/A]
1
-1-e-X
where we use 1. - [b/A] < b/1+1.
141// Hence, the robustness bound is at most
I-c X-
40

---

F.4 Proof of Corollary 2
Proof. In the multi-shoo ski rental problem. we choose shop n when y 2 TOPT and shop when < ToP,, while keeping all other aspects of Algorithm unchanged. According to Theorem this shop selection strategy yields higher target competitive ratio compared the case where all shops are simultaneously considered. As result, the resulting algorithm serves an upper bound for both the consistency bound and the robustness bound of Algorithm g In the following, we employ this selection strategy to prove the consistency bound and the robustness bound.
Let the optimal offline cost given by (ZT( min T}. and the critical time is ToPt b,- Note that (PT(Tam) Tur
1. Therefore, (PT(n) = 1 for all n E N+ in this setting. Let & = [Xb,] and
I = [b.
When 2 b, the corresponding target competitive ratio is 1-
1 1 8
When y < b, the corresponding target competitive ratio is
Consistency. We first bound the competitive ratio when the predictor is correct.
Bound 1: For the algorithm (1)) B;
(ToPT A 4i OPT (ToT))
ALG(b,; U:A
T5
[bb
1
\b
h
b.
bg
e
Ar,
e
(
Bound For the algorithm
ALG(ToPT; (2)) viA
ALG(boi An)
Ted
OPT(TOPT)
by
-
T-e-x
e-
where the last inequality follows from A S T.
Therefore, the consistency bound for both cases is upper bounded by
r&A
T-m T-e-
Robustness. We now consider the case where the prediction is inaccurate, and we evaluate robust- ness to prediction errors.
Bound 1: According Theorem 2
ALG([ATOPL :; 9:
b1
(PT( ((TTPT)
(2(2 br b
-Ta(A
Bound 2:
ALG ALG (T AA]
A (2)
[b/
1
bj
1/2 1/b1
OPT(TopT)
1-
b
b, 1
where we use 1= [b/ 11
In Hence, the robustness bound is at most
1/A+1/b1
b,
max T- Path
178.77
T-e 17X
G Supplementary Numerical Results
In this section, we conduct numerical experiments to evaluate the performance of the SOAC algorithm and LA-SDAC algorithm. Specifically, we investigate the relationship between path selection complex- ity and the competitive ratio. Additionally, we perform further experiments using the SOAC algorithm to solve multi-shop, multi-slope problems. The experimental platform an AMAX TR40-X -4 server, configured with dual Intel Xeon Gold 6448H processors. The system is equipped with 512 GB of DDR5-4800 ECC memory, two 16 TB hard disk drives, two 960 GB solid-state drives, and four graphics processing units.
41

---

G.1 Supplementary numerical results in Section
Building upon the experimental setup detailed Section 5 we conducted more comprehensive numerical experiments investigate the impact of various parameters the performance of the LA-SDAC algorithm.
1.8
0.23
1.
1.8
1.6
1.5
LA-BON
Corpedtee
Conteetivee
LA-BONG
LA-GOAC
1.4
(1% (2) FM)
15% (2) (T)
1.3
01: 23
011 30 (30)
115, 30
R15.
(80
12
111 30
1.1
11
1.1
150
289
Error
(8)
(b)
(c)
1.5
LA 40AC
Parchose Order 313 (R)
1.5
Parchaso Order: its. 3), PM
1.5
0:25
0.25
1.3
1.1
Eroor Parsmnttr
300
433
100
Erior Parameter
400
588
(d)
(1)
Figure 8: Average competitive ratio across different error parameter 7) with X E {0.25, 0.5, 0.75, 1} and 8 0.
The impact of the hyperparameter Figures iillustrate the average competitive ratio of LA-SDAC under different values of À {0.25, 0.5, 0.75, } and varying error parameters 17. The hyperparameter captures the degree of trust placed in machine learning predictions: a smaller corresponds to higher trust, while larger À reflects greater caution. When predictions are highly accurate, smaller \ enables LA-SDAC to achieve performance close to the offline optimal. However, as the prediction error increases, over-reliance performance degradation. In contrast, with a larger X, the algorithm becomes more conservative, and the competitive ratio rises more slowly 1) increases. These results show the trade-off between consistency and robustness controlled by X, and demonstrate that LA-SOAC consistently performs at least well as algorithms that follow single deterministic path.
inaccurate predictions (i.e., low X) can lead to significant
The impact of biased error 5. Figure 9 illustraaees the average competitive ratio of LA-SOAC under different bias levels 6 E {50, 100, 150, 200} and varying error parameters y,, with fixed values of 0.25 and 0.75. The results reveal how the bias parameter 5 influences the trade-off between exploiting accurate predictions and mitigating the risk of large errors. When the error level is small, smaller bias 8 leads better competitive ratios, as enables the algorithm more aggressively utilize accurate predictions. Conversely, when 7) is large, a larger 5 becomes advantageous by hedging the impact of significant prediction errors, thereby improving overall performance.
G.2 Application of SOAC to the multi-shop ski rental problem
In the multi-shop ski rental problem, skier must decide how to ski for an unknown duration T. The skier chooses a shop from set of shops {1, 2,..., m] and can only rent purchase ski equipment from that selected shop. Each shop i offers daily rental price and purchase price b,, where rs, by > O. assumed that r1 < 12 < ... < rm and by > b2 > > bm. ensuring that shops with lower rental prices have higher purchase prices to avoid trivial decisions. The skier's goal is
to select shop and determine the optimal purchase time to minimize total costs, without changing shops midway.
42

---

LA-50AC 0.25
Purchase Order (11 30, DS 0
Comprtthe Rallo
1.0
Competttee Rallo
1.6
Untexee:
50
1.3
150
< 200
1.1
100
200
300
500
900
100
200
310
400
500
600
Error Paramater
Emror Parameter
(a)
(b)
-
Correettive Raaio
1.8
Competiive
Uvb ased
Untexaed 200
50
200
12-
1.1
100
200
400
008
(c)
(d)
Figure 9: Average competitive ratio across different parameter " and bias 5
(50, 100, 150, 200), with fixed values of = 0.25 and = 0.75.
We consider scenario with three shops, each offering different rental and purchase prices. The rental and purchase prices at these shops 2 with r2 = 1.2 and by = 576, and shop with = 1.3 and by = 560. Based on the calculated probabilities, the likelihood of selecting each shop determined: the probability of choosing shop 1 is 87.9 87.9%, the probability for shop 2 is 0%, and the probability for shop 3 is 12.1%. This indicates that the user only likely choose between shop and shop 3. The daily purchase probabilities for these two shops are illustrated in Figure [0)a). We then compute the probability of choosing each shop for different values of by varying the purchase price 6Y of shop while keeping the prices of the other shops constant, as shown in Figure [0]b). The results indicate that as b₁ increases, the probability of selecting shop decreases, while the probability of selecting shop increases.
follows: shop with T and d₁ 594, shop
Additionally, the competitive ratio rises. This occurs as a higher purchase price for shop 1 increases the risk associated with selecting it, as the potential rental benefit diminishes.
0.812
Slop
Shop
Shop
Shop
1.7288
1.7984
Shop
Shop
Probabilty
0.6
0.4
150
300 500
600
650
700
750
800
(a)
(b)
Figure 10: (a) Probability of purchase for each shop the three-shop ski rental problem. Shop has
purchase price b, 594 and rental price r; 1, shop 2 has purchase price by 576 and
rental price r2 = 1.2, and shop 3 has a purchase price by = 560 and a rental price ra = 1.3. (b) The impact of the competition ratio and the probability of selecting each shop after adjusting the purchase price of shop 1.
43

---

G.3 Application of SOAC to the multi-slope ski rental problem
The multi-slope ski rental problem considers a scenario where a user needs to utilize a resource for an unknown duration. The cost of resource usage is determined by multiple states (or slopes), denoted as S {0. 1.... .... Each state is associated with purchase cost b, and rental rate rs which typically satisfy the conditions bo < bj < ... < by and > ri > transitions are constrained be forward-only, meaning that one cannot move backward or skip states. The objective is to determine the optimal state (or slope) to minimize the cost at given time t.
Tk, with bo = 0. State
randomized profile is defined as the probability vector p(t) (t). Pk (t)), where pr(t) represents the probability of being in state at time f. To illustrate how SOAC can be applied to this problem, consider an example inspired by [9]. Assume there are three states with purchase and rental costs defined as = (bo. bj. b2) and r CSR problem, where a fixed purchase path is given by (Su, S1. S2, Sz). For each state the associated costs are defined as: fSo) = g(S)) = =0, f(S1) = b1 - bo. ((S = ri, f(S²) = For example, consider the following
(1.7). respectively. This corresponds to the
b2 b, (S22) ri r2: (Sa) xc, g(S)) configurations of b and r
Example 1: 00,0.5, 0.9), r= (,0.5,001).
Example 2: b 00,0.5, 0.7). r- (2,0.5, 0.3).
Example 3: - (0,0.5, 0.55), r- 0.,0 0.45).
By applying the SOAC algorithm to these examples, the probabilities of being in each of the three states can be computed, as illustrated in Figure 11 These results are consistent with the experimental results in [19].
Stae State
Stra
Probabiity
0.6
getaatitty
Cntine tepagpor
Oftine braakpo::
0.4
0.2
0.
02
0.4
12
6.4
08
08
Time
(b)
(c)
(a)
Figure 11: Illustrative examples demonstrating the application of the SOAC algorithm to solve
the multi-slope problem. (a) Example 1: b = (0, 0.,, r = 0., 0.1); (b) Example
b = 0...),, (2, 0.5, 0.3); (c) Example 3: 0.5, 0.55), (2, 0.5, 0.45).
G.4 Supplementary numerical results of SOAC and LA-SOAC
Consider scenario in which a company requires specific software to support both its daily operations and long-term growth. However, the duration for which these software applications will be used remains uncertain. The market offers diverse range of software options, which can acquired either through perpetual purchase or on-demand leases. It is important to note that some software applications are interrelated, and bundling multiple products from the same vendor may result in additional discounts. The company's 's business needs may require anywhere from 6 to 16 software applications. For the sake of simplicity, we assume each application is priced at one unit for rental. Furthermore, discounts are available only for certain combinations of the first six software packages. A summary of the purchase prices for these 16 software packages, including the discounted combination prices, is provided in Table I
For applications that do not qualify for combination discounts, Lemma Saanmamesstan eestablishes that the optimal strategy is to purchase them individually. As result, there are eight distinct purchase paths. These paths are summarized in Table 2 which excludes applications 7 through 16. These applications are purchased individually and are incorporated into the table based on the buy-to-rent ratio.
44

---

Table 1: Purchase prices of 16 software applications and corresponding combination purchase prices.
Items
{
{2}
{3)
{4]
{5}
Prices
202
535
960
370
206
Items
{6}
(7)
{8}
{9}
{10}
Prices
171
800
120
714
221
Items
{11)
{12)
{13)
{14)
{15}
Prices
556
314
430
558
187
Items (16)
[1,2]
(2,3, 4]
(4,5)
{5, 6}
Prices
472
663.3
1715.8
524.16
327.99
We computed the probability selecting the optimal purchase path for firms acquiring between and 16 applications. The results indicate that the decision ultimately narrows down to either path I path 2, as shown in Figure a) As the number of applications increases, the probability of choosing path decreases, while the probability of selecting path 2 rises. This shift leads corresponding reduction in the competitive ratio. The underlying reason for this change is that as the path selection process becomes more deterministic, the decisions in the CSR problem are simplified. This reduction in decision uncertainty results in a lower competitive ratio.
1.55
Earra
0.8
1.55
Prob
0.8
1.524
P1ob
0.50
0.2
0.2
1.50
1.0141
1.5
209
400
000
1000
1200
1400
Hortzon
(a)
(b)
(c)
Figure 12: Analysis of path selection probabilities and competitive ratios. Path 1 is defined as (15, (1), (2, 3, 4)), and Path as 6], [1, (4), (3}). The remaining items are purchased independently and assigned to paths based the buy-to-rent ratio. (a) Illustrates the effect of increasing the number of undiscounted items on the path selection probability and the competitive ratio. (b) Illustrates the case where the number of items is fixed 10, and different discounts are applied to the combination {1, 2}. The discount for this combination is defined as the sum of the purchase prices of items and 2, multiplied by the discount factor. (c) Validation theoretical vs. experimental competitive ratios.
Furthermore, we fixed the selection of the first 10 items, modified the price of the combination (1,2), and kept the prices of the remaining items unchanged. We then computed the probabilities of selecting path and path 2 for various discount factors for the combination
(1,2), along with the corresponding competitive ratios, as shown in Figure b2). Similar to the conclusions drawn in Figure [2(a), an increase the discount leads to greater uncertainty in path selection process. This increased uncertainty leads to a more complex decision-making process in the CSR problem, which in turn results in higher competitive ratio.
Based on the same pricing settings as in Figure 12 we further evaluate the theoretical performance of the SOAC algorithm. Specifically, consider scenarios with 8. and 16 items, where purchase decisions are made according to the randomized probabilities computed by Algorithm 2 We then evaluate the empirical performance of the algorithm by computing the empirical average competitive ratio for varying end times of the game. As illustrated in ci) [2]c), the experimental competitive ratios align well with their theoretical counterparts, validating the accuracy the algorithm. Moreover, we observe that the fluctuation in the experimental competitive ratio is more pronounced when the end time shorter. This is because randomized experiments conducted over shorter durations tend to exhibit greater variance. Additionally, the fluctuation decreases the number of items increases.
45

---

Table 2: Purchase paths for multiple software applications, with software 7 through 16 omitted for convenience.
Path 1-4
Path 5-8
(5566) (1),
(1), (6,6), (3)) (6)) (10),65) (10):1455,
(1,0)
(1),
This is attributed to the fact that with more items. the decision paths become more deterministie, thereby reducing the variance, as also reflected in Figure 12
For the learning-augmenter algorithm, we let the actual number of days, T, be uniformly distributed within the region [1, 4Twr) The predicted number of days, y, is to y = T c, where the simulated and a standard deviation 17. For each standard deviation 7,. 10,000 samples are randomly sampled in this study, and their average competitive ratios are calculated. As illustrated in Figure 13 we evaluated the average competitive ratio of the LA-SOAC algorithm for 10 items across varying error parameters. Our analysis focused on how this ratio changes with the parameter X, and we also compared it to the average competitive ratio achieved by selecting a single path. The results indicate that LA SOAC effectively balances consistency and robustness. Specifically, when the algorithm increasingly relies on the predicted values and the prediction error minimal, its average competitive ratio approaches that of the offline optimal solution. Furthermore, LA-SOAC demonstrates superior performance compared to strategies that commit a single path.
error c follows a normal distribution with a mean
1.0.1
Conoertiee Rate
1.0
LA B0AG Poth
8.15
Path
Futh1 3
Peh
1000
2000
3000
4000
1888
6013
5000
2000
5000
4000
5000
4009
1933
2000
3000
4000
5000
6000
Erir Parinettr
Error Parumeter
(6)
(b)
(c)
LA-904C
- 9.75
Compettive Ebtto
Comsectiivnn
25
LA-SOAC
LA-SONC
1.5
Fish
1.4
Psh7
1000
2000
Emro Parsmeter
3000
4000
1580
6933
2000
2000
4000
6803
1000
2000
Enoo Partmeert
3000
4000
5500
6993
(d)
Figure 13: Average competitive ratio across different error parameters v) with 10 items.
G.5 Runtime Analysis
In this subsection, provide detailed runtime evaluation to complement the scalability experiments in Appendix G.4 and to demonstrate the practical feasibility of SOAC. All experiments were conducted on an AMAX TR40-X4 server (detailed specifications in Appendix G using CPU-only computation without CUDA acceleration.
We study runtime as the number of discount combinations increases. All experiments were run with high precision (10-6) and practical precision (10-1). When reducing the precision from 10-6 to 10 10-1, the number of iterations decreases to approximately 7% of the high-precision runs.
46

---

Table 3: Runtime scaling with purchase paths. Entries marked with are extrapolated estimates.
Combos
Purchase Paths
Time/Iter
Iterations
Runtime
High Precision (10
Practical Precision (10 (10-*)
4
10
0.285s
436 2.1 min
10 - 2.85
7
30
2.97s
492 -> 24.3 min
36 - 2.4 min
8
60
11.25s
560 + 1.75 h
35 + 11.1 min
10
120
69.29s
525 + 10.1 h
40 - 48 min
12
240
451.67s
500* + 2.6 d
35" + 4.39
405
1972.02s
500* -> 11.4
35 + 19.2
The per-iteration time complexity is polynomial in the number of purchase paths. A cubic fit of the form
y 0.0000253r 3 0.00180z 0.00746x + 0.334
achieves good fit quality (residual sum of squares (RSS 0.74) ). confirming theoretical polynomial behavior.
The total runtime increases rapidly as the number of discount combinations grows. However, the above experiments based adversarially constructed discount combinations designed maximize overlap and diversity among purchase options, which tend to produce a large number of purchase paths. In practical scenarios, the structure of discount bundles is often more regular and aggregated. For example, practical combinations may include larger bundle sets, which significantly reduce the number of distinct purchase paths and, consequently, the total runtime.
To illustrate this difference, we further compare synthetic adversarial (many small, disjoint combi- nations) and practical realistic (fewer, larger combinations) scenarios. An additional 8-item study is shown Table It can be seen that realistic structures lead to substantially fewer purchase paths and much shorter computation times. Moreover, the computation of purchase probabilities is performed offline during the planning phase, and the resulting online buy-or-rent decisions can be executed instantaneously without any runtime overhead.
Table 4: Runtime comparison under adversarial vs. realistic combination structures.
Setting
Discount Combos
Purchase Paths
Total Time
10
61
7.18 min
20
187
2.2
Adversarial
25
352
30
524
10
11
17.6
20
21
42.2 s
Realistic
25
26
1.05 min
30
32
1.61 min
47


Reviews:
[{"review_id": "4U5VSOSPz0", "reviewer": "Reviewer_gJHT", "summary": "This paper proposes a generalization of the ski rental problem called Combinatorial Ski Rental (CSR). Like the traditional ski rental problem, the proposed problem is an online optimization problem in which ski equipments must be either rented (for a day) or purchased (for good) at the beginning of each day, until the end of the last day which is not known to the algorithm in advance. The difference of CSR from the traditional problem is that the required ski equipments are a set of multiple items. Each day, we may decide to purchase a subset of the items, and those items that haven't been purchased must be rented. After observing that CSR generalizes several ski-rental type of problems that were previously studied, the paper goes on to give a competitive algorithm and a learning-augmented algorithm for CSR.\n\nThe \"output\" or the \"strategy\" of an algorithm can be fully described by a partition of the entire set of items and a (randomized) schedule that specifies on which day each subset will be purchased. As such, the paper starts by giving an algorithm (or a subroutine) called OAC that, given a partition, determines a schedule of the purchases within a finite time horizon. The paper then presents an algorithm called SOAC that uses OAC as a subroutine: the algorithm finds an optimal probability distribution over the partitions, samples a partition from it, and then invokes OAC on that partition. The paper shows that this algorithm gives an \"optimal\" competitive algorithm.\n\nThen, to give a learning-augmented algorithm, the paper presents an algorithm that adjusts the finite time horizon mentioned above according to the given prediction. This adjustment allows us to write the robustness and consistency (bound) of the algorithm indirectly in terms of its performance (or \"competitive ratio\") for a particular choice of the last day.\n\nFinally, the paper evaluates the performance of the proposed algorithms through experiments.", "questions": "- Line 133, \"Additionally, ... to enforce the order of purchase in $\\sigma$.\": Why do we do this? Suppose for example we have two items 1 and 2, and we decided to purchase 1 and then later 2. The following two strategies both respect the order of purchase:\n\na) buy item 1 on day 10 and item 2 on day 20;\n\nb) buy item 1 on day 30 and item 2 on day 40.\n\nSo, choosing a) with probability 1/2 and b) with 1/2 is a perfectly valid strategy, but the condition would rule out this possibility. Why is the constraint \"$p_n(S_{i+1} | \\sigma)=0$ when $F_n(S_i | \\sigma)<1$\" a safe one to impose?\n\n- The paper claims that the algorithm can handle submodular rental rates, too. Then why don't we present that version instead (especially given that the difference is supposed to be minimal)?\n\n- Line 177, \"We define an optimal amortized cost strategy...\": the current phrasing sounds as if OAC is just defined to be that specific strategy, rather than the \"optimal\" one among all possible strategies (independent from Definition 2). The appendix makes it clear that the latter is the intention, but this should be clarified in the main body.\n\n- Line 730, doesn't the inequality need to contain equality to handle ties?\n\n- Does the experiments actually run the algorithm, or analytically calculate the competitive ratios? This was not clear from the experiment description.\n\nLet me write a few minor comments here too:\n\n- On page 2, it is mentioned that CSR generalizes a number of problems. A brief explanation would be nice.\n\n- Don't we need some additional assumption on $f$, like $f(\\emptyset)=0$?\n\n- In Definition 2, it seems that $T_A$ also is a variable (that we need to determine by solving the system of equations), but that was not clear at a glance.", "limitations": "Please see weaknesses above, especially Item 1. While Section 6 does mention running time as a limitation, I believe a more thorough discussion would be desirable. Item 2 in the weaknesses section discusses limitations of the experiments.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 1, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "### Strength\n\n1. The paper gives a unified framework that solves a number of problems, generalized by CSR.\n\n### Weakness\n\n1. In order for the unified framework to have true advantage, the unified algorithm must have a good performance, both in terms of the performance guarantee and running time. For many online optimization problems, it is possible for the algorithm to compute the \"optimal\" strategy when given enough amount of running time. But it is not often considered in the literature because either the running time is prohibitively large or an explicit competitive analysis is difficult. However in this paper,\n\n1-a. The competitive algorithm does not come with an analysis that explicitly gives a competitive ratio.\n\n1-b. It appears that the algorithm may require a significant amount of running time, as each iteration of the gradient descent method would involve solving a large system of equations. But the paper does not give theoretical/experimental analysis of the running time.\n\n1-b'. In Section 6, it is briefly mentioned that the running time is exponential, but I don't see why that is the case. A naive implementation's running time may depend on the number of input bits, possibly doubly exponentially.\n\n1-c. For the learning-augmented algorithm, the unification is somewhat incomplete in that we sometimes hand-pick $T_{OPT}^{(1)}$ and $T_{OPT}^{(2)}$.\n\n2. The experiment seems to be limited.\n\n2-a. It uses a fixed set of three items, which is another reason why the experiment would not properly assess the running time issues explained above.\n\n2-b. It is also not clear why this particular choice of the item costs were used in the experiments.\n\n2-c. The experiment only introduces Gaussian noise to the prediction. I'm not sure if this would be a good evaluation of the algorithm's robustness.", "was_revised": true, "final_justification": "Most of the questions in the Questions section of my original review were adequately answered. Regarding weakness 2, while I do not fully agree with the authors, I also believe that these are matter of choice and should not negatively affect the final rating.\n\nAuthors explained numerous points regarding weakness 1, and I appreciate that. I decided to maintain my rating though, for the following reasons.\n\n- In my original review, I explained my view of questioning the practical relevance of an online algorithm without an explicit guarantee on competitive ratio. The authors raised [19] as an example of a previous study that gave an online algorithm without such guarantee. I respectfully point out that [19] is very different: they did give such an algorithm for the additive version of the problem, but that was in addition to another algorithm for the same problem that is more \"classical\" in that it comes with an explicit guarantee. Since that second algorithm exists, one can use the former (i.e., the optimal algorithm without explicit guarantee) with the confidence that the algorithm is going to perform at least as good as that second algorithm's guarantee.\n\n- Another point that I raised in my original review was about the running time. Again, [19] is a good example that shows the contrast. I'd like to make one clarification first: the algorithm in [19] is indeed efficient. The running time's dependence on $k$ is fine because the input already constains $\\\\Theta(k)$ number of items in the input, namely the description of each slope. On the other hand, this paper's algorithm does not come with such a bound. The authors' comment said that the running time is not polynomial but pseudopolynomial (which already shows that the algorithm is not efficient by definition), but even that is not clear. Note that $T_{\\\\mathnormal{OPT}}$ is not part of the input, and we do not have an immediate bound on $T_{\\\\mathnormal{OPT}}$ that is a polynomial in terms of the number and magnitude of input items.\n\nI acknowledge that the results of the paper may be of interest to some people in the community. On the other hand, I also feel that, with all due respect, the limitations we discussed above are not explicit or sometimes inaccurately presented in the current paper. I believe that the strengths of this paper can be appreciated by the community only if its limitations are properly discussed.\n\nEverything taken into consideration, I'd maintain my slightly negative view in my original review of this paper.", "rebuttal": "We thank reviewer for the constructive comments, We provide our feedbacks as follows.\n\n> **W(1-a):  Competitive ratio analysis.**\n\n**A(1-a):** SOAC provides the strongest possible theoretical guarantee: it computes the *optimal competitive ratio* for any CSR instance via convex optimization (Lemma 5). No online algorithm can achieve better worst-case performance.\n\n**Verification on tractable cases:** SOAC recovers all known optimal ratios:\n\n- Single-item ski rental: competitive ratio $1+\\frac{1}{(1-1/b)^{-b}-1}$ (matches known optimal)\n- Multi-shop ski rental: recovers optimal ratio from [1]\n\n**Why no closed-form?** The piecewise structure of $\\text{OPT}(T)$ with slope changes at breakpoints makes closed-form analysis intractable—this is a fundamental property of CSR. Even simpler variants like multi-slope ski rental [19] lack closed-form competitive ratios despite extensive study.\n\n---\n\n> **W(1-b) W(1-b'): Runtime complexity analysis.**\n\n**A(1-b) and A(1-b'):**  We thank the reviewers for raising concerns about the algorithm’s computational complexity.  While we acknowledge that the worst-case complexity of our algorithm can be super-exponential in theory, **this does not necessarily pose a practical limitation**. Here's why:\n\n### (1) Real-world performance is highly feasible\n\nEmpirical runtime on standard hardware (Intel Core i9-14900HX) shows our algorithm scales well for realistic scenarios:\n\n| Purchase Paths       | Runtime per Iteration |\n| -------------------- | --------------------- |\n| 10 paths             | 0.48s                 |\n| 30 paths             | 4.34s                 |\n| 60 paths             | 22.57s                |\n| 120 paths (10-combo) | 137.0s                |\n| 240 paths (12-combo) | 909.0s                |\n\nWhile we acknowledge that scalability for large item sets remains a concern, these 10-12 combo configurations already capture the complexity range of most real-world discount scenarios.\n\n### (2) Our optimization significantly reduces theoretical worst-case\n\nWhile naive enumeration gives $O(m! B_m)$ paths, where $B_m$ is the Bell number (counting all partitions of $m$ items), **Lemma 3** reduces this to $O(B_m)$ by proving optimal paths always sort super-items by buy-to-rent ratio. This eliminates the factorial term—a substantial theoretical improvement.\n\n### (3) Simpler CSR Structures Lead to Polynomial Complexity\n\nOur framework automatically recovers efficient performance for well-studied variants:\n\n- **Multi-Shop:** $O\\big(m \\cdot (T_{\\text{OPT}} \\log(1/\\varepsilon) + \\log m)\\big)$, where $m$ is the number of shop\n- **Multi-Slope/Multi-Commodity:** $O(T_{\\text{OPT}} \\log(1/\\varepsilon))$\n- **Classic Ski Rental:** $O(T_{\\text{OPT}} \\log(1/\\varepsilon))$\n\nThis confirms that these less general CSR variants are solvable in polynomial time.\n\n### (4) Per-iteration complexity is polynomial\n\nEach iteration runs in $O\\left(K \\cdot \\left(T_{\\text{OPT}} \\log(1/\\varepsilon) + \\log K \\right)\\right)$, which is polynomial in all parameters when the number of purchase paths $K$ is fixed. The exponential worst-case scenario (all combinations discount-eligible) is unrealistic.\n\n---\n\n> **W(1-c): Learning-augmented unification.**\n\n**A(1-c):**  As discussed in Section 4, simply setting  $T_{\\text{OPT}}^{(1)} = T_{\\text{OPT}}^{(2)} = T_{\\text{OPT}}$ already yields strong performance both in theory and practice. More broadly, the algorithm remains well-defined and its theoretical guarantees still hold as long as  $T_{\\text{OPT}}^{(1)} \\leq T_{\\text{OPT}} \\leq T_{\\text{OPT}}^{(2)}.$\n\nWe provide two concrete examples to support this, as formally proved in Corollary 1 and Corollary 2:\n\n- For the **classic ski rental** problem, we use  $T_{\\text{OPT}}^{(1)} = T_{\\text{OPT}}^{(2)} = T_{\\text{OPT}},$ achieving the state-of-the-art consistency-robustness trade-off.\n\n- For the **multi-shop ski rental** problem, we use  $T_{\\text{OPT}}^{(1)} = T_{\\text{OPT}},\\quad T_{\\text{OPT}}^{(2)} = b_1 \\geq T_{\\text{OPT}},$ also matching or exceeding prior best-known trade-offs.\n\nTheorem 2 provides explicit consistency and robustness bounds for *any* setting of $T_{\\text{OPT}}^{(1)}$ and $T_{\\text{OPT}}^{(2)}$, making our algorithm broadly applicable.  \n\n---\n\n> **W(2-a): Experimental scale**\n\n**A(2-a):**  We use a three-item setup in our main experiments to clearly illustrate the theoretical properties of the SOAC algorithm, whose analysis involves complex formulas. This simplified setup enables transparent demonstration of the algorithm’s mechanics.\n\nFor the LA-SOAC algorithm, we intentionally use three items to exhaustively enumerate all purchase paths, allowing precise evaluation of the consistency-robustness trade-off—a core contribution of our work.\n\nImportantly, our method scales well, and we include larger-scale experiments with up to 16 items in Appendix G.4 to demonstrate its practical applicability.\n\n---\n\n> **W(2-b):  Item cost selection.**\n\n**A(2-b):**  We thank the reviewer for the suggestion. In Figures 3 and 4, item costs were randomly sampled from a realistic range—uniformly over [50, 150]—with discounts set to 5% for any two-item bundle and 10% for all three items. These settings mimic common real-world discount practices.\n\nIn Figure 5, we used the public dataset from [25] to ensure a fair and direct comparison with prior work.\n\nCode and data are publicly available to ensure full transparency and reproducibility.\n\n---\n\n> **W(2-c): Prediction noise model.**\n\n**A(2-c):**  Using Gaussian noise to evaluate prediction robustness is a standard and widely accepted practice in the learning-augmented algorithms literature (e.g., references [21, 25]). This allows fair comparison with prior work.\n\n---\n\n> **Q1:  Purchase order.**\n\n**A1:**  We thank the reviewer for this very technical and important question.\n\nThe reason we enforce the purchase order constraint is that, as proven in Lemma 3, given a fixed purchase path, the optimal strategy must respect a restricted purchase order sorted by increasing buy-to-rent ratios.\n\nWe prove in Lemma 3 that for any strategy that does not strictly follow the BR-based order, there exists an alternative strategy with reallocated purchase probabilities that strictly respects the order and achieves no worse competitive ratio. Therefore, we enforce this ordering constraint within each path $\\sigma$ to preserve optimality and simplify the problem structure.\n\nWe acknowledge that this crucial point was not clearly explained in the modeling section, and we will add a detailed explanation in the final version to clarify this important constraint.\n\n---\n\n> **Q2:  Submodular rental rates.**\n\n**A2:**  Our framework *fully supports submodular rental rates*—the additive assumption is solely for computational tractability of the offline benchmark.\n\n### Our algorithm handles submodular rates naturally:\n\nOur approach reduces the problem to optimizing over fixed purchase orders using convex optimization. This reduction works regardless of rental rate structure because:\n\n- Purchase decisions depend on buy-to-rent ratios of items and super-items\n- These ratios are correctly captured in our model for any rental rate function\n- The convex optimization framework applies universally\n\nTherefore, our algorithm can solve the problem optimally for *any* independent rental rate function, including submodular cases, where “independent” refers to rental costs that remain fixed regardless of time or item combinations.\n\n### Why we focus on additive rates in presentation:\n\nThe additive assumption serves a computational benchmark purpose: it keeps the offline optimal computation tractable. Here's the technical distinction:\n\n- **Additive case:** $\\min_{S \\subseteq \\mathcal{M}} \\{f(S) + T \\cdot g(\\mathcal{M} \\setminus S)\\} = \\min_{S \\subseteq \\mathcal{M}} \\{f(S) - T \\cdot g(S)\\} + T \\cdot g(\\mathcal{M})$ remains submodular and efficiently solvable\n- **Submodular case:** When $g$ is submodular, $g(\\mathcal{M} \\setminus S)$ becomes supermodular in $S$, making the objective (submodular + supermodular) NP-hard to optimize\n\n---\n\n> **Q3:  OAC definition clarity.**\n\n**A3:**  Thank you for pointing this out. Yes, the reviewer is correct: *OAC refers to the optimal strategy within the full strategy space (AC)*. We will clarify this key distinction in the main paper to avoid confusion.\n\n---\n\n> **Q4: Inequality handling ties.**\n\n**A4:**   Equality in the inequality is not required. When two items have the same buy-to-rent ratio, their relative purchase order has no impact on the competitive ratio. For example, if both item 1 and item 2 have a buy cost of 10 and a rental cost of 1, any order—or even a randomized mix—results in the same performance. Thus, distinguishing their order is unnecessary and does not affect optimality.\n\n---\n\n> **Q5: Experimental methodology.**\n\n**A5:**  We validate our algorithm both analytically and empirically.\n\nIn Figures 2(b) and 12(c), the black lines show the theoretical competitive ratios computed analytically, while the colored shaded areas represent empirical competitive ratios from simulations based on the algorithm’s randomized purchase probabilities.\n\nThe horizontal axis corresponds to the ski rental horizon, and the vertical axis measures competitive ratios.\n\nThe close match between theory and simulation confirms both the correctness of our analysis and the algorithm’s practical performance.\n\n---\n\n> **Minor Comments**: \n\n**A**:  Thank you for the valuable suggestions.\n\n- **CSR  variants explanation:** We will add a clear, concise explanation on page 2 when introducing CSR to improve readability (detailed proofs remain in Section 3.3 and Appendix E).\n\n- **Assumption clarity:** We will explicitly state $f(\\emptyset) = 0$ for completeness.\n\n- **$T_A$ clarification:** In the revised version, we will clarify in Definition 2 that $T_A$ is a variable.\n\nWe thank the reviewer for the constructive feedback and hope that our detailed responses adequately address the raised concerns."}, {"review_id": "5HKePVrYOK", "reviewer": "Reviewer_fJU6", "summary": "This paper brings and studies CSR problem, which is an online combinatorial optimization problem.\nTo solve this problem, the authors propose Sorted Optimal Amortized Cost (SOAC).\nThis SOAC algorithm has good performance and is capable of solving multiple variants of the CSR problem.\nThe authors also propose a learning-based augmentation for further improvement.\nThey conduct experiments for validation.", "questions": "Q1. The problem seems adopts a lot of settings, could you please introduce the most simple and basic version of the problem?\n\nQ2. Could the author provide some examples or cases to intuitively explain why their algorithm is better?", "limitations": "\"yes", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "S1. The figures are easy to read.\n\nS2. Theoretical analysis are provided.\n\nS3. The paper is conducted on a \n\nW1. The abstract could be improved. In the abstract, the authors introduce the CSR problem, however they do not clarify the optimization goal (ie minimizing rental or purchase cost) of the problem.\n\nW2. The idea is not original enough. Improving average performance instead of worst case performance has long been proposed and studied. [Ref1]\n\nW3. The problem abstraction seems adopt a lot of assumptions, which largely confines the potential of learning-based methods.\n\nW4. The theoretical derivation is largely drawn from spatio temporal research community, which is not original enough. [Ref2] [Ref3]\n\n\n[Ref1] Yongxin Tong, Jieying She, Bolin Ding, Lei Chen, Tianyu Wo, Ke Xu. \"Online Minimum Matching in Real-Time Spatial Data: Experiments and Analysis\" , Proceedings of the VLDB Endowment, 9(12): 1053-1064, 2016.\n\n[Ref2] Dickerson J P, Sankararaman K A, Srinivasan A, et al. Allocation problems in ride-sharing platforms: Online matching with offline reusable resources[J]. ACM Transactions on Economics and Computation (TEAC), 2021, 9(3): 1-17.\n\n[Ref3] Nanda V, Xu P, Sankararaman K A, et al. Balancing the tradeoff between profit and fairness in rideshare platforms during high-demand hours[C]//Proceedings of the AAAI conference on artificial intelligence. 2020, 34(02): 2210-2217.", "was_revised": true, "final_justification": "I have thoroughly read the rebuttals from the reviewers, and part of my concerns have been resolved, and I will keep my score", "rebuttal": "We appreciate your time and great efforts in reviewing.\n\n> **W1: The abstract could be improved. In the abstract, the authors introduce the CSR problem, however they do not clarify the optimization goal (ie minimizing rental or purchase cost) of the problem.**\n\n**A1:** We appreciate the comment.  We will revise the abstract to clarify the optimization objective by changing the current sentence:\n\n\"At each time step, a decision-maker must make an irrevocable buy or rent decision for items that have not yet been purchased, without knowing the end of the time horizon\"\n\n*to*:\n\n\"At each time step, a decision-maker must make an irrevocable buy or rent decision for items that have not yet been purchased, without knowing the end of the time horizon, *to minimize the total rental and purchase cost*.\"\n\nThis revision will make the optimization goal immediately clear to all readers, regardless of their familiarity with online algorithms terminology. \n\n---\n\n> **W2: The idea is not original enough. Improving average performance instead of worst case performance has long been proposed and studied. [Ref1]**\n\n**A2:**  We thank the reviewer for the comment and the opportunity to clarify the novelty of our work. We respectfully believe there may be a misunderstanding of our contributions.\n\nOur goal is not merely to improve the average-case performance of a classical problem, but to introduce and tackle a fundamentally new online optimization setting—the *Combinatorial Ski Rental* (CSR) problem—using novel algorithmic ideas with provable guarantees. In particular:\n\n- **Problem novelty**: The CSR problem is, to our knowledge, studied here for the first time. It captures realistic yet challenging features such as submodular purchase costs and non-upgrading constraints, which are not addressed in prior literature.\n- **Algorithmic innovation**: We propose the first algorithm that achieves the *optimal competitive ratio* for this combinatorial variant. This solves a long-standing open problem and extends the frontier of ski rental-type online decision-making.\n- **Unifying framework**: Our framework  generalizes and subsumes several classical settings (e.g., multi-shop and multi-slope ski rental) as special cases, providing a unified treatment of a broad class of problems.\n\nRegarding the reference provided by the reviewer ([Ref1]), we note that it concerns *online bipartite matching*, a fundamentally different problem class with distinct objectives and constraints. While improving average performance is indeed a broadly studied theme, our contribution lies in the *novel combinatorial structure and competitive analysis* of a new online decision-making problem, not just the idea of performance improvement itself.\n\n---\n\n> **W3: The problem abstraction seems adopt a lot of assumptions, which largely confines the potential of learning-based methods.**\n\n**A3:** We thank the reviewer for raising this point and appreciate the opportunity to clarify our modeling assumptions. We believe there may be a misunderstanding regarding the claim that these assumptions limit the potential of learning-based methods. Our model indeed relies on two key assumptions: additive rental rates and submodular purchase costs. These are reasonable characterizations of the problem’s nature, commonly found in practical scenarios, and provide meaningful structural properties.\n\nUnder these assumptions, our learning-augmented SOAC algorithm not only recovers existing learning-augmented ski rental results but also improves upon them, demonstrating its effectiveness. These assumptions do not exclude the integration of learning techniques.\n\nIn fact, our framework is designed as an optimization platform that can embed prediction or learning modules (as illustrated in Section 4), leveraging demand forecasts to guide purchase decisions, while maintaining theoretical guarantees.\n\nIn future work, we would be happy to explore relaxing these assumptions to address more complex settings, such as dependent rental rates or time-varying purchase prices.  \n\nWe believe the current work provides a solid foundation in the field of online decision-making under uncertainty.\n\n---\n\n> **W4: The theoretical derivation is largely drawn from spatio temporal research community, which is not original enough. [Ref2] [Ref3]**\n\n**A4:** We thank the reviewer for the comment and the opportunity to clarify our theoretical contributions. However, we respectfully believe this comment reflects a misunderstanding of the foundations and novelty of our work.\n\nThe cited works [Ref2, Ref3] focus on *online bipartite matching problems*, which are fundamentally different from our Combinatorial Ski Rental (CSR) problem in both *problem structure* and *algorithmic methodology*:\n\n- **Problem nature**: The cited works study online matching and resource reuse. In contrast, our work addresses rental-versus-purchase decisions under *submodular cost functions* and *non-upgrading constraints*, which form a distinct combinatorial optimization framework.\n- **Algorithmic techniques**: Cited works develop matching algorithms and fairness optimization.  Ours proposes amortized cost tracking and convex optimization over purchase paths.\n\nOur theoretical contributions are original and significant: to the best of our knowledge, this is the *first work* to formalize the CSR problem, derive optimal online strategies under submodular settings, and unify multiple ski rental variants under a single framework.\n\nIt is possible the reviewer associated our work with general themes in the online algorithms literature. While there is a superficial resemblance in high-level setting, the mathematical assumptions, problem definitions, and algorithmic tools used in our work differ substantially from those in [Ref2, Ref3].\n\n---\n\n> **Q1: The problem seems adopts a lot of settings, could you please introduce the most simple and basic version of the problem?**\n\n**A1:** Thank you for the question. The most basic version of the problem is the classic ski rental setting, as described in Section 3, Example 1: there is only one item, and on each day, the algorithm must choose whether to rent it at a daily cost  or buy it at a one-time cost, without knowing in advance how long the item will be needed. The purchase decision is irreversible, and the objective is to minimize the competitive ratio.\n\n---\n\n> **Q2: Could the author provide some examples or cases to intuitively explain why their algorithm is better?**\n\n**A2:** Thank you for the question. Consider a simple but realistic scenario: you're going on a ski trip and need both skis and boots. Renting skis costs 10/day, and boots 4/day. Buying them separately costs 120 and 50, but you can buy the full set for only 150. The challenge is that you don’t know how long the trip will last.\n\nA naive strategy might treat each item separately—perhaps buying skis after a few days while still renting boots—missing the opportunity to use the bundle discount. On the other hand, deciding to buy the full set too early could lead to higher costs if the trip ends up being short. The key difficulty lies in knowing not just what to buy, but also when and in what combination.\n\nOur algorithm, SOAC, solves this by continuously evaluating the amortized cost of renting versus buying combinations. It naturally captures the interaction between items, discounts, and timing. Rather than relying on fixed rules or assumptions, it makes mathematically optimal decisions based on current cost trends, ensuring the best possible performance even in the worst case."}, {"review_id": "ST2tLINLn6", "reviewer": "Reviewer_XvPp", "summary": "This paper introduces the Combinatorial Ski Rental (CSR) problem, a generalization of classic ski rental where multiple items can be rented/purchased individually or in bundles, with submodular purchase costs and additive rental rates. The key contributions include an optimal randomized online algorithm achieving the best possible competitive ratio for CSR (which is called SOAC). The authors also study the learning-augmented setting, leveraging predictions to balance consistency (accuracy with good predictions) and robustness (worst-case guarantees). Finally, the authors also did numerical validation of SOAC/LA-SOAC superiority over baselines.", "questions": "Could you comment on what will happen if the rental rate is also a submodular function? Is the problem becoming much harder? When the rental rate is additive, the offline optimal solution is equivalent to minimizing a non-monotone submodular function. When the rental rate is submodular, as far as I  can see, the offline problem no longer seems in P, but I am not sure how hard both the online and offline versions are.", "limitations": "n/a", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n1. I like the proposed CSR model; it elegantly unifies several ski rental variants and addresses the open non-upgradable case (where prior work assumed upgradable purchases). The submodular cost model captures real-world bundle discounts. I also appreciate that the authors draw Figure 1 to describe the related works, and it is helpful.\n\n2. I usually work on offline approximation algorithms. But, as far as I can see, the algorithm SOAC is novel, using amortized cost tracking against an offline optimal benchmark and convex optimization over purchase paths via an augmented path construction. Thus, I think that the technical contribution is sufficient.\n\n3. The paper is well-written and organized. I enjoy reading the paper.\n\nWeakness:\n\n 1. SOAC’s runtime scales exponentially with the number of super items, which is stated in section 6. While the authors note that real-world discounts are often sparse, scalability for large item sets remains a concern.\n\n2. The additive rental rates and submodular costs are well-justified but may not hold in all applications (e.g., interdependent rental costs).\n\nSummary:\n\nThis is a good paper, and I believe that it should be accepted.", "was_revised": true, "final_justification": "I believe that this paper studies an interesting problem, although the obtained result does not seem plausible. The authors also address my questions during the rebuttal. I decide to keep my score. I also went through other reviewers' comments, and I agreed with some of the weaknesses that I also mentioned in the review. In summary, I am fine with both rejection and acceptance.", "rebuttal": "We thank the reviewer for the encouraging feedback and helpful suggestions.\n\n> **W1: SOAC’s runtime scales exponentially with the number of super items, which is stated in section 6. While the authors note that real-world discounts are often sparse, scalability for large item sets remains a concern.**\n\n**A1:** We thank the reviewer for your positive and insightful comments. We agree that, in the most general case, the computational complexity arising from large item sets remains a limitation of the current paper; however, we would like to emphasize that addressing this limitation is not the focus of this work and does not necessarily pose a practical concern.\n\n### 1. Scope of Contribution: Information-Theoretic Guarantees in Online Decision-Making\n\nOur primary contribution targets the *information-theoretic challenges* of online decision-making, specifically bounding competitive ratios under future input uncertainty. This fundamentally differs from developing efficient approximation algorithms for offline optimization problems. Once purchasing probabilities are computed initially, the online buy-or-rent decisions within CSR execute without computational bottlenecks.\n\n### 2. Algorithmic Complexity Reduction\n\nWe have proactively addressed scalability through several key optimizations:\n\n- **Theoretical breakthrough**: Lemma 3 proves that optimal purchase orders must follow descending buy-to-rent ratios, reducing complexity from $O(m!  B_m)$ to $O(B_m)$, where $B_m$  is the Bell number\n- **Real-world sparsity**: Most practical discount structures are sparse, keeping the number of valid purchase paths manageable\n\n### 3. Per-iteration complexity is polynomial\n\nEach iteration runs in $O\\left(K \\cdot \\left(T_{\\text{OPT}} \\log(1/\\varepsilon) + \\log K \\right)\\right)$, which is polynomial in all parameters when the number of purchase paths $K$ is fixed. The exponential worst-case scenario (all combinations discount-eligible) is unrealistic.\n\n### 4. Simpler CSR Structures Lead to Polynomial Complexity\n\nOur framework automatically recovers efficient performance for well-studied variants:\n\n- **Multi-Shop:** $O\\big(m \\cdot (T_{\\text{OPT}} \\log(1/\\varepsilon) + \\log m)\\big)$\n- **Multi-Slope/Multi-Commodity:** $O(T_{\\text{OPT}} \\log(1/\\varepsilon))$\n- **Classic Ski Rental:** $O(T_{\\text{OPT}} \\log(1/\\varepsilon))$\n\nThis confirms that the computational cost is significantly lower when the structure of the CSR problem is less general.\n\n### 5. Empirical Evidence for Practical-Scale Scalability\n\nOur runtime analysis on a laptop with Intel Core i9-14900HX processor (16 items) shows scalable performance across different path complexities:\n\n- **10 paths**: 0.48s per gradient iteration\n- **30 paths**: 4.34s per gradient iteration\n- **60 paths**: 22.57s per gradient iteration\n- **120 paths (10-combo)**: 136.97s per gradient iteration\n- **240 paths (12-combo)**: 908.96s per gradient iteration\n\nWhile we acknowledge that scalability for large item sets remains a concern, these 10-12 combo configurations already capture the complexity range of most real-world discount scenarios.\n\n### 6. Potential for Further Optimization\n\nA critical observation from our experiments: *only a small subset of candidate paths appear in optimal solutions*. This opens clear avenues for future improvements:\n\n- Early elimination of suboptimal paths\n- Pruning and approximation strategies\n- Avoiding exhaustive candidate enumeration\n\n---\n\n> **W2: The additive rental rates and submodular costs are well-justified but may not hold in all applications (e.g., interdependent rental costs).**\n\n> **Q: Could you comment on what will happen if the rental rate is also a submodular function? Is the problem becoming much harder? When the rental rate is additive, the offline optimal solution is equivalent to minimizing a non-monotone submodular function. When the rental rate is submodular, as far as I can see, the offline problem no longer seems in P, but I am not sure how hard both the online and offline versions are.**\n\n**A2/Q:** Thank you for the insightful question. We analyze the impact of extending from additive to submodular rental rates from both offline and online perspectives. \n\n**Conclusion**: submodular rental rates do not affect our online algorithm's optimality, but do increase offline computational complexity.\n\n### 1. Offline Setting: From Polynomial to NP-Hard\n\n**Additive rental rates (current model):** When rental rates are additive, the offline objective becomes: $\\min_{S \\subseteq \\mathcal{M}} \\{f(S) + T \\cdot g(\\mathcal{M} \\setminus S)\\} = \\min_{S \\subseteq \\mathcal{M}} \\{f(S) - T \\cdot g(S)\\} + T \\cdot g(\\mathcal{M})$\n\nThis reduces to *non-monotone submodular minimization*, for which efficient polynomial-time approximation algorithms exist.\n\n**Submodular rental rates:** When $g$ becomes submodular, $g(\\mathcal{M} \\setminus S)$ becomes supermodular in $S$. As a result, the objective becomes the sum of a submodular and a supermodular function, a problem class that is generally NP-hard. Therefore, the offline problem likely requires exponential time to solve exactly and no longer clearly lies in P.\n\n### 2. Online Setting: Computational Complexity Unchanged\n\nOur online algorithm's structure and optimality *remain completely unaffected* by submodular rental rate assumptions. Here's why:\n\n- Purchase decisions depend on buy-to-rent ratios of items and super-items\n- These ratios are correctly captured in our model for any rental rate function\n- The convex optimization framework applies universally\n\nTherefore, our algorithm can solve the problem optimally for *any* independent rental rate function, including submodular cases, where “*independent*” refers to rental costs that remain fixed regardless of time or item combinations. \n\n**Source of computational complexity:** The primary computational bottleneck lies in the combinatorial explosion of purchase paths, which exists independently of rental rate structure—not in the rental computation itself."}, {"review_id": "OQXNRdvAKS", "reviewer": "Reviewer_BAW1", "summary": "In the combinatorial ski rental problem, the goal is to either rent or buy a set of items, that are necessary to ski, for a complete skiing season with an unknown duration. At each day of the skiing season, we can decide to either rent or buy the necessary items that have not been bought yet, with the goal of minimizing the total cost at the end of the skiing season. The cost function for buying a subset of items is submodular, giving the problem a combinatorial nature. On the other hand, the cost for renting a subset of items is just the sum of the individual renting costs. Algorithms for this problem are analysed against the optimal offline solution, which knows the duration of the skiing season upfront. This problem generalizes multiple variants of ski rental that have been studied in the literature. The closest related problem in the literature is the problem variant with upgrading [32]: In this variant, the cost for buying a set of items $S$ at time $t$ is $f(S \\cup P) - f(P)$ where $P$ is the set of items bought in previous steps, i.e., we only pay the marginal costs. In contrast, in the variant considered in this paper, the cost is just $f(S)$. The difference between these two variants is reflected in the competitive ratio: For the variant with upgrading, [32] shows a (randomized) competitive ratio of e/(e-1). For the variant of this paper, the competitive ratio can get worse depending on the given cost functions.\n\nThe main results of this paper are (1) a randomized algorithm that achieves the optimal competitive ratio for each fixed pair of cost functions and (2) a learning-augmented algorithm that receives a prediction on the length of the skiing season and achieves improved results when this prediction is somewhat accurate, while still giving worst-case guarantees.  The authors first observe that a deterministic strategy can be represented by a \\emph{purchase path} (sequence of item bundles to be bought) and \\emph{purchase times} (points in time at which the purchases of the purchase path should be made). Consequently, a randomized strategy can be interpreted as a distribution over purchase paths and purchase time pairs. To achieve the first main result, the authors first show how to compute the optimal purchase time distribution for a fixed purchase path by tracking how the optimal solution cost evolves with an increasing time horizon and bounding the expected algorithmic cost against this increase . Afterwards, they use the insights from this algorithm to design an algorithm that simultaneously computes the optimal purchase path distribution and purchase time distribution by using a projected gradient descent method. Finally, they show how to integrate predictions into this algorithmic framework and give empirical experiments.", "questions": "* Are there hardness results justifying the need for an exponential running time?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n\n* The presented randomized algorithm unifies several existing results for multiple ski rental variants. In a similar way, the learning-augmented algorithm recovers, and thereby unifies, results for multiple previously studied variants. This seems like a significant step towards a general framework for solving problems of this type. In particular, because the theoretical results give the best-possible competitive ratio \\emph{for each} fixed pair of cost functions, which makes them applicable to special cases without loss. \n* In my opinion, the algorithmic ideas for computing the purchase probabilities for a fixed purchase path (Section 3.1) are very elegant. They use a characterization of the offline optimal solution to track how the optimal cost increases with an increasing time horizon. In order to find $\\alpha$-approximative purchase probability, they locally bound the (expected) increase in the algorithm's cost by $\\alpha$ times the increase in the optimal cost. Tracking how the optimal solution evolves over time in this way, is a very nice idea. Similarly, the insight that the purchase path probabilities can be computed with the projected gradient descent method is nice. In total, the paper seems to bring multiple new ideas to the area of ski rental type problems. \n\nWeaknesses:\n* The running time of the presented algorithm can be exponential in the input size. In the conclusion, the authors state that this is due to the combinatorial nature of the problem. It would be nice to formally underline this statement with hardness results.\n* The instances (item number and cost functions) considered in the empirical part seem a bit arbitrary. They are still useful as a proof of concept. However, it is unclear what the empirical results mean for practical instances.", "was_revised": true, "final_justification": "As outlined win my original review, I think that the paper is a strong contribution.  In my opinion, the main strength of the paper are:\n\n* the unification of existing results on (learning-augmented) ski-rental variants,\n* new results for a generalisation of previously studied ski-rental variants,\n* An algorithm that achieves the best-possible competitive ratio for every instance (characterised by the set of items, the sub modular purchase function, and the rental prices) and, thus, maintains its optimality also for special cases.\n\nMy main concern (also shared by the other reviewers) is  the exponential running time.  The author’s rebuttal addresses these concerns by using the following main arguments:\n\n* For a fixed number of purchase paths, the complexity is (pseudo)-polynomial.\n* For previously studied special cases, a (pseudo)-polynomial running time is achieved.\n* Empirical experiments indicate scalability in practice.\n\nIn my opinion, the first two arguments are sufficient to keep the results strong and interesting from a theoretical point of view.  Therefore, I would like to maintain my original score. However, I hope that the authors add a more extensive discussion of the running time to the final version of the paper.", "rebuttal": "Thanks for your positive comments and helpful suggestions. \n\n> **W1: The running time of the presented algorithm can be exponential in the input size. In the conclusion, the authors state that this is due to the combinatorial nature of the problem. It would be nice to formally underline this statement with hardness results.**\n\n> **Q: Are there hardness results justifying the need for an exponential running time?**\n\n**A1/Q:** Thank you for this important suggestion regarding the computational complexity analysis. The exponential complexity arises from the *combinatorial input space* (number of valid purchase paths), not algorithmic inefficiency. Our algorithm achieves *polynomial-time per-iteration complexity* for a fixed number of purchase paths and *matches existing polynomial bounds* in previously studied special cases.\n\nWe provide a detailed response addressing both theoretical foundations and practical implications.\n\n### 1. Fundamental Algorithm Efficiency\n\nWhen the number of purchase paths $K$ is fixed, the overall complexity of our method is provably polynomial.\n\n- **Single Path (OAC)**:\n   When the purchase path is fixed, the OAC algorithm uses binary search to compare $T_A$ with $T_{\\mathrm{OPT}}$. In each iteration, the search region is halved until the stopping criterion $\\varepsilon$ is satisfied, resulting in a complexity of $O\\left(T_{\\mathrm{OPT}} \\log \\frac{1}{\\varepsilon}\\right).$\n\n- **Multiple Paths (SOAC)**:\n\n  For SOAC, each iteration of projected gradient descent involves:\n\n  - Gradient computation over $K$ purchase paths: $O(K)$\n  - Competitive ratio evaluation for each path via OAC: $O\\left(K \\cdot T_{\\mathrm{OPT}} \\log \\frac{1}{\\varepsilon}\\right)$\n  - Gradient update: $O(K)$\n  - Simplex projection: $O(K \\log K)$\n\nCombining these steps, the per-iteration complexity of SOAC is $O\\left(K \\cdot \\left(T_{\\mathrm{OPT}} \\log \\frac{1}{\\varepsilon} + \\log K\\right)\\right)$, where $K$ is the number of purchase paths.\n\nThe algorithm itself is highly efficient—exponential growth comes from input structure, not computational design.\n\n### 2. Exponential Complexity: Worst-Case Analysis\n\nIn the worst-case scenario where all item combinations have discounts:\n\n- **Naive bound**: $O(m! \\cdot B_m)$ paths (super-exponential)\n- **Our optimization**: Lemma 3 reduces this to $O(B_m)$ by proving optimal purchase orders follow buy-to-rent ratios\n\nMost practical discount structures are sparse, dramatically reducing the number of valid purchase paths from theoretical worst-case scenarios.\n\n### 3. Empirical Validation: Scalability in Practice\n\n**Hardware**: Intel Core i9-14900HX processor, 16 items with bundle discounts\n\n| Purchase Paths        | Runtime per Iteration |\n| --------------------- | --------------------- |\n| 10 paths              | 0.48s                 |\n| 30 paths              | 4.34s                 |\n| 60 paths              | 22.57s                |\n| 120 paths  (10-combo) | 137.0s                |\n| 240 paths  (12-combo) | 909.0s                |\n\nIn our experiment with 16 items and 12 discounted combinations (resulting in 240 purchase paths), each gradient iteration took only 909 seconds, which is sufficient for practical deployment in real-world applications.\n\n### 4. Polynomial-Time Performance for Structured Cases\n\nOur framework *recovers existing polynomial bounds* for well-studied special cases:\n\n- **Multi-Shop**: $O(m \\cdot (T_{\\text{OPT}} \\log(1/\\varepsilon) + \\log m))$, where $m$ is the number of shop\n- **Multi-Slope**: $O(T_{\\text{OPT}} \\log(1/\\varepsilon))$\n- **Multi-Commodity**: $O(T_{\\text{OPT}} \\log(1/\\varepsilon))$\n- **Classic Ski Rental**: $O(T_{\\text{OPT}} \\log(1/\\varepsilon))$\n\nThis confirms that the computational cost is significantly lower when the structure of the CSR problem is less general.\n\n---\n\n> **W2: The instances (item number and cost functions) considered in the empirical part seem a bit arbitrary. They are still useful as a proof of concept. However, it is unclear what the empirical results mean for practical instances.**\n\n**A2:**  Thank you for the insightful question. \n\nIn the main text, we use a three-item setup in our main experiments to clearly illustrate the theoretical properties of the SOAC algorithm, whose analysis involves complex formulas. This simplified setup enables transparent demonstration of the algorithm’s mechanics. For the LA-SOAC algorithm, we intentionally use three items to exhaustively enumerate all purchase paths, allowing precise evaluation of the consistency-robustness trade-off—a core contribution of our work.\n\nOur empirical evaluation also serves to validate the theoretical guarantees. For example, in Figure 2(b) and Figure 12(c), the black lines indicate the theoretical competitive ratios, while the shaded areas depict the empirical performance under randomized decisions. Their close alignment confirms that the algorithm performs in practice as predicted by theory.\n\nAdditionally, larger-scale experiments can be found in Appendix G.4, where we evaluate scenarios with up to 16 software applications using realistic pricing structures that include combination discounts. These experiments show that as the algorithm's decisions become more deterministic, the competitive ratio improves. We also analyze how discount factors affect path selection probabilities and show that the LA-SOAC algorithm effectively balances consistency and robustness across varying prediction errors, consistently outperforming single-path strategies. All supplementary code is included in the submitted materials (folders: `SOAC_sup_material` and `LA-SOAC_material`) to ensure full reproducibility."}]

Author rebuttal:

Meta-review: This paper introduces the problem of combinatorial ski rental. The strength is that optimal algorithms (among online algorithms) are obtained, and that the model is very general which captures essentially all notable variants of ski rental. The major weakness is the scalability of the algorithm, and that there is no concrete new applications suggested (albeit it recovers/dominates known results). 

Various issues are discussed during the rebuttal, and the mentioned major weaknesses are addressed to some extent. It is agreed that these weaknesses cannot be easily overcome within the current framework/scope of the work.

Although this is a borderline paper, I still find it interesting and could general broader impact, which merits the acceptance.
Decision: Accept (poster)