Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problems
Authors: Mohammadreza Daneshvaramoli
Helia Karisani
Adam Lechowicz
Bo Sun
Cameron N Musco
Mohammad Hajiesmaili
Venue: ICML 2025 poster (2025)
Keywords: Learning Augmented
Succinct Predictions
Primary area: theory->online_learning_and_bandits

Abstract: This paper introduces a family of learning-augmented algorithms for online knapsack problems that achieve near Pareto-optimal consistency-robustness trade-offs through a simple combination of trusted learning-augmented and worst-case algorithms. Our approach relies on succinct, practical predictions—single values or intervals estimating the minimum value of any item in an offline solution. Additionally, we propose a novel fractional-to-integral conversion procedure, offering new insights for online algorithm design.

Near-Optimal Consisteney- Trade-Offs for Gearning-Augmentt Online Knapsack Problems
Mohammadreza Daneshvaramoli
Helia Karisani
Adam Lechowicz' Mohammad Hajiesmaili
Bo Sun 2 Cameron Musco
Abstract
In the online knapsack problem (OKP), the goal is to pack a finite number of sequentially arriving items with different values and weights into a knapsack with limited capacity, so that the total value of admitted items is maximized. In the online setting, the decision maker must immediately and irrevocably admit or reject item upon its arrival without knowing future items. OKP captures a broad range of re- source allocation problems with applications to online adver- tising (Zhou et al., 2008), resource allocation (Zhang et al., 2017; Buchbinder & Naor, 2009), dynamic pricing (Bo- standoost et al., 2023). supply chain (Ma et al., 2019), and beyond. Historically, work on OKP variants has focused developing algorithms under the framework of compet- itive analysis (Borodin et al., 1992). It is well known that no online algorithm can achieve bounded competitive ra- tio for the basic version of OKP (Marchetti- Spaceammla & Vercellis, 1995; Böckenhauer et al., 2014b) without mak- ing additional assumptions on the input, e.g., assuming that value-to-weight ratios are bounded (Zhou et al., 2008; Sun et al., 2021a; Yang al., 2021). In this work, go be- yond competitive analysis, to study OKP through the lens of leaming--augmented design.
This paper introduces family of learning- augmented algorithms for online knapsack prob- lems that achieve near Pareto-optimal consistency- robustness trade-offs through a simple combina- tion of trusted algorithms. Our approach relies on succinet, prac- tical predictions-
and worst-case
values or intervals es- timating the minimum value of any item in an offline solution. Additionally, we propose novel fractional-to -o-tterral conversion procedure, offer- ing new insights for online algorithm design.
1. Introduction
Learning-augnann design (Lykouris & Vassilvtiskii, 2018; Purohit et al., 2018) is a successful framework whose goal to systematically go beyond competitive analysis in on- line problems by leveraging ML predictions to improve algorithm performance without sacrificing worst-case guar- antees. In this framework, online algorithms are evaluated using the concepts of consistency and robustness, which characterize the competitive ratio (see $ 2.1) when the pre- diction is accurate or arbitrarily wrong, respectively. An overarching design goal is to achieve a Pareto-optimal result that captures the best achievable trade-off between consis- tency and robustness. Toward this goal, algorithms have been proposed that achieve optimal consistency- robbusteesss trade-offs for several problems such as ski rental (Bamas et al., 2020; Wei & Zhang, 2020), online search (Sun et al., 2021a), and bin packing (A (Angelopoulos et al., 2024). How- ever, Pareto-optimal results remain open for several other online problems, including the online knapsack problem.
Prior results. There has been substantial work on learning- augmented algorithms for OKP. We classify them into three categories: (i) OKP with frequency predictions (Im et al., 2021), (ii) advice complexity of OKP (Böckenhauer et al., 2014b), and (iii) Parcto-optimal algorithms for simplified OKP variants (Sun et al., 2021 Lee et al., 2022; Balseiro et al., 2023). See $ A.1 for a complete literature review. In the following, we focus on closely related prior work.
In the first category, Im et al. (2021) study learning- augmented OKP using frequency predictions, i.e., predic- tions of the total weights of items for each possible unit value in an instance. The authors provide upper bounds on the consistency and robustness of their SENTINEL algorithm, but do not provide lower bound on the best achievable consistency
MManiing College of Information and Computer Sciences, University of Massachusetts Amherst, Amherst, MA, USA *Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, Canada. Correspondence Mohammadreza Daneshvaramoli mddansshaarm @ww.ss.uuuuu.........mm Helia Karisani <hkarisani @ @umass.cu>>.
trade-off under the frequency predic- tion model, leaving the question of optimality open. Further, the frequency prediction model requires the algorithm to be given large number of predictions (one for each possi- ble unit value). Due to this complexity, accurate frequency predictions may be difficult to obtain in practice.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Near-Optimal Setnssteny--obustteee Trade-Offs for Learning-Augmentes Online Knapsack Problems
Table 1. Summary of contributions.
Prediction Model
Algorithm
Upper Bound
Lower Bound
Point Prediction
PP-b, PF-a
2. 1 + min (1, [) (Theorems 3.2, 3.3)
1 + min (1, [. (Theorem 3.1)
Interval Prediction
IPA
2 2 In(%/e) (Theorem 3.4)
2 2+ In("/e) (Theorem 3.6)
Consistency-
MIX
3/x 4/x-consistent (A E (0. (0)1))
?/a-consistent (A E (0.1))
robustness
]n(U/2) -robust robbust (Theorem 4.1)*
22
[m((//2)11 -robust (Theorem 4.2)*
[1-X)
(1-X)
present our results context of online fractional knapsack (OFKP); Theorem we give a generic conversion the integral case, showing the results extend with small loss to this setting under standard assumptions. Our lower bounds in the fractional case also hold the integral case by nature of the relaxation; see 5.5. A w is the total weight of items with critical value 8 (see Def 2.2). > and are lower and upper bound predictions on hyperparameter passed to learning augmented algorishan that leverages untrusted predictions. indicates that we consider the setting where item values are bounded in [L, U..
the critical value (see Def. 2.3). > (0, 1)
In the second category, Böckenhauer et al. (2014b) study the advice complexity of OKP, giving an online algorithm with competitive ratio 1 + for any constant e >> O using (log n) bits of advice (Böckenhauer et al., 2014b, The- orems 13 and 17), where is the number of items. To achieve this result, their algorithm requires strong advice about the offline optimal solution (including the number of items, multiple critical item values, and the indices of certain admitted items). With such strong advice, the algo- rithm itself is simple: it reserves the capacity for items from advice and greedily admits other items. However, acquiring the required advice from an ML model in practice is likely difficult, c.g., admitted item index advice becomes invalid if instances are shuffled. Further, Böckenhauer et al. (2014b) focus only on the setting where the advice is assumed to be accurate. It is unclear how to extend their analysis to give consistency-robusteess trade-offs.
impractical predictions. Motivated by these limitations, the main goal of this paper is to answer the following question: Can we design near Pareto-optimal learning-aun aaggentedd al- gorithms for OKE using practical & succcintt predictions?
Contributions. We present OKP algorithms that achieve near Pareto-optimal trade-offs between consistency and ro- bustness, using succinct predictions of a critical value i, i.e. the minimum value of any item admitted by an offline opti- mal solution (see Table 1). Our work introduces novel algo- rithmic frameworks, and technical contributions to knapsack problems under both trusted and untrusted predictions.
For trusted point predictions of the critical value é, we prove the optimal competitive ratio is 1 + min (1,)), where w is the total weight of items with value é (Theorem 3.1). Our algorithm PP-a achieves this bound using a novel sneeve-wwille-reede
approach (Theorem 3.3). Existing OKP algorithms are mainly based on a threshold-based al- gorithm, which is a reserve-then -eree-eedg--redyyyy strategy that pre- allocates capacity for high-value items and greedily admits others (Lee et al., 2022; Sun al., 2022). Instead of relying on fixed reservation, PP-a dynamically adjusts its reserved capacity based on observations of high-value items, improv- ing the competitive ratio from 2 (achieved by a reserve-then- greedy algorithm PP-b) to + min muin[1,0],
In the third category. prior works have developed algorithms with Pareto-optimal consistency-robusten various simplified versions of OKP. For example, using sim- ilar frequency predictions to (Im et al., 2021), Balseiro et al. (2023) develop Pareto-optimal algorithms for the single-leg revenue management problem, which can be interpreted as an OKP variant with unit weight items that take values from discrete and finite set. However, the algorithms and their Pareto-optimality guarantees do not extend to the case of continuous valued items. Pareto-optimal algorithms using succinet single-valued predictions have also been given for online conversion problems (Sun et al., 2021a; Lee et al., 2022). These problems can be seen as fractional variants of OKP with item weights equal to the capacity, where the opti- mal offline solution simply fills the knapsack with the single most valuable item. The consistency robbuttesy trade-offs derived in these settings do not extend to general OKP- in online conversion and search, an accurate prediction of the highest item value is sufficient to obtain a 1 1-competitive algorithm. This is not the case for OKP, since the most valu- able items may be small, forcing the offline optimal solution to admit less valuable items to fill the knapsack capacity.
trade-offs for
For trusted interval predictions E < 0 S u. our IPA algo- rithm achieves a competitive ratio of 2 + In("/e), matching a derived lower bound (Theorem 3.4, 3.6). Interval pre- dictions also model point predictions with bounded error, enabling robust solutions under uncertainty.
For untrusted predictions, we propose an algorithm, MTX that combines trusted algorithms with a robust baseline. As- suming unit values lie within [L, we show MIX achieves e/ e/ccoonsit and In(e/L)+1 -oobssttsssssssss (Thcorem 4.1,, 1-X where e is the competitive ratio of the trusted prediction algorithm. This trade-off is near-optimal (Theorem 4.2).
We then introduce a fractional pactional-to-integra tt--integral conversion algo- rithm that adapts any OFKP solution for use in OIKP under small item weights (Zhou et al., 2008; Im et al., 2021). This conversion facilitates near-optimal consistency-rrbuuiness trade-offs for integral settings (Theorem 5.2).
In summary, prior work on learning- augmented algorithms for OKP fails to achieve Pareto-optimal trade-offss in all but few significantly simplified variants of the problem. Further, existing algorithms often leverage complex and potentially
Finally, in $ 6, we evaluate our algorithms on synthetic and real data from Bitcoin and Google workload traces. Our algorithms significantly outperform baselines without
2

---

Near-Optimal Consistency-Robusttoes Trade-Offs for Learning-Augmented Online Knapsack Problems
predictions, even with noisy inputs. Compared to algorithms relying on complex frequency predictions (Im al., 2021), our succinct prediction-based approaches exhibit superior performance and degrade gracefully with prediction errors.
for OFKP with trusted predictions ($ 3) do not require the bounded value assumption. However, in the untrusted pre- diction setting ($ 4), this assumption ensures bounded ro- bustness by using the worst-case optimal algorithm (Zhou et al., 2008) as a subroutine. The conversion algorithm link- ing OFKP and CIKP ($ 5) also leverages this assumption. Additionally, Theorem A.2 shows that the bounded value assumption necessary to achieve a bounded competitive ratio, even with trusted prediction.
2. Problem Formulation and Preliminaries
In this section, we define the online knapsack problem (OKP), introduce the prediction models used, and review existing algorithms and results.
Adversary model. Throughout this work, we adopt the standard adaptive adversary model for online algo- rithms (Borodin & El-Yaniv, 1998). In this model, the adversary can generate the input sequence adaptively and change based on the algorithm's 's past decisions. This setting captures worst-case scenarios where item arrivals are influenced by the algorithm's m's behavior, and it is widely used in the analysis of online problems, including online knapsack (Zhou et al., 2008; Sun et al., 2022). All our lower bounds and robustness results assume the adaptive adversary model.
Throughout the paper, we occasionally use the term value to refer to the unit value (i.e., value-to-weight ratio) of an item, especially in early sections for simplicity. This shorthand common in the literature on
knap- sack (Im et al., 2021; Sun et al., 2022), and we clarify the meaning when ambiguity might arise.
Online knapsack problem. Consider knapsack with capacity 1 (w...o.g.). Items arrive online, each with unit value Uj and weight wi: Upon arrival, an algorithm decides I; E Xr the acceptance of item i, without future knowledge. Here X3 denotes feasible decisions for item i. Each deci- sion x; yields profit F aiming to maximize total profit under capacity constraints. When X; {0, w;), the algo- rithm decides to pack reject the entire item (OIKP). For
2.1. Preliminaries
Competitive ratio. OXP has been historically studied using competitive analysis, where the goal is to design an online algorithm that achieves a large fraction of the offline opti- mum profit on all inputs (Borodin et al., 1992). We denote by OP (I the offline optimum for input I, and by ALC (I) the profit obtained by online algorithm. The competitive ratio is then defined as == maxzen CFT(Z)/aza(II, where Ω denotes the set of all possible inputs, and ALG is said to be C- c-competitive. If ALG is randomized, we analogously define the competitive ratio as c = maxten (2)(2)/B ALa(Z))
X = [0, w;], fractional packing is allowed (OFKP). We use OKP for both problems unless otherwise specified, An OKP instance I = {(V,, w;) wa) in] has the offline formulation:
Σn i=1 WiVi, s.t. Σn 24 S 1, E : Vi E [n). (1)
max (#:)
The offline solution for OFKP sorts items by unit value and fills the knapsack in that order. The critical value is the smallest value of items (possibly fractionally) packed. Items with higher values are all packed. This algorithm also applies approximately to OIKP when w, < 1, Vi E [n]. In the online setting, OFKP and OIKP with small weights can both be solved optimally on worst-case instances via a threshold- based algorithm (see $ 2.1).
Consistency and robustness. In the literature on learning- augmented algorithms, competitive analysis is interpreted using the notions of consistency and robustness, introduced by Lykouris & Vassilvtiskii (2018); Purohit et al. (2018). An online algorithm with predictions is said to be b-consistent if it is b-competitive when given a correct prediction, and r-robust if it is r-competitive when given any prediction, regardless of its correctness. The goal is design an al- gorithm that achieves the best robustness for any chosen consistency - i..., achieving Pareto-optimal trade-off be- tween consistency and robustness.
Assumptions. We adopt the standard small weight assump- tion for OTKP, where w, & 1, Vi E [n] (Zhou al., 2008). This assumption is essential to achieve meaningful com- petitive ratio in worst-case instances of OIKP (Marchetti- Spuccamela & Vercellis, 1995; Zhou et al., 2008). In Theo- rem 1, we show that it remains necessary for OIKP even with a trusted prediction of the critical value. Notably, our OFKP algorithms do not rely on this assumption.
Prior results: competitive algorithms without prediction. Both OIKP with small weights and OFKP have received significant attention. Under the assumption of bounded unit values (i.c., V, E [L. UJ, Vi e [n]), prior works (Zhou et al., 2008; Sun al., 2021b) have shown an optimal determin- istic threshold-based algorithm (ZCL) for OIKP and OFKP, We present pseudocode for 2CL in the Appendix, in Alg, 4. Note that ZCL requires prior knowledge about the maxi- mum unit value U and minimum unit value L for an instance,
Prior work on OKP and related problems, such as one-way trading and online search (EI- Yaniv et al., 2001), often as- sumes bounded support for unit values, i.e., E [Z, U]. where L and U are known. This assumption is also critical for a bounded competitive ratio in worst-case in- stances (Marchetti- Spahhtti-Spaccamlll & Vercellis, 1995; Zhou et al., 2008). Notably, our naming--augmenter algorithms
3

---

Near-Optimal Consisteney-Robuuttne Trade-Offs for Learning-Augmentte Online Knapsack Problems
achieving the optimal competitive ratio In(U/t) + for both OFKP and OIKP. In 3, we show that this competitive ratio can be improved to a constant with no assumptions on L and U by leveraging trusted (i.e., accurate) predictions. To trade-off
weights are set to 1, making the critical value equivalent to the maximum value, i.e., the offline optimal solution only admits one item with the maximum value. Accurate prediction of the critical value enables the recovery of the optimal solution in this special case. However, in OFKP with arbitrary item sizes, leveraging such predictions becomes notably more challenging. One main contribution of this study is the design of an optimal competitive algorithm using an accurate prediction of the critical value in OFKP.
achieve a Pareto-optimal consistency-robustee in the untrusted prediction setting, our MIX algorithm uses the worst-case optimal ZCL algorithm as a subroutine.
2.2. Succinet Prediction Model
Throughout the paper we consider succinct predictions de- rived from the critical value of the offline optimal fractional OFKP solution, defined formally below.
The integral OKP has primarily been explored using other prediction models. Im et al. (2021) propose a frequency (interval) prediction model, predicting the total weights of items for each possible unit value in an instance. On the other hand, Balseiro et al. (2023) introduce model that fo- cuses on a frequency prediction over the possible unit values admitted by the offline optimal algorithms. However, any frequency prediction model demands large number of pre- dictions, significantly increasing the complexity of obtaining predictions with high accuracy. In contrast, our succinct prediction models only require a point or interval predic- tion, and can achieve comparable empirical performance to algorithms that employ more complicated predictions.
Definition 2.1 (Critical valued items (f, Given an in- stance of OKP, é is a critical value denoting the minimum unit value of any item (fractionally) admitted by the offline optimal solution. Let @ be the total weight of the items with value é. Note that 0 = min(e; Ejm,,o Wj < 1}.
Below, we introduce two prediction models of the critical value i of an instance. We note that our algorithms do not receive a prediction of the corresponding capacity w.
Definition 2.2 (Prediction Model I: Point Prediction). A single value prediction of the critical value é, as defined in Def. 2.1, is given a leaming-augmmntedd online algorithm.
Our succinet prediction is strictly weaker than the frequency prediction model. Formally, let ((f(()), denote the frequency prediction (as given by Im et al. (2021)), where ('(u) and (v) denote the lower and up- per bounds of the frequency density, respectively. Given such a frequency prediction, we can directly obtain an interval prediction over the critical value by calculating == minfv E [I.U] 1 (u() S 1} and u == minfu E [L,U] : 1t f"(v)dv S 1). Last, we note that de- veloping an ML model generate predictions is beyond the scope of this paper, as our focus is on leveraging predictions algorithms.
The point prediction is simple; however, we note that even when an algorithm is given an accurate point prediction of i, it cannot necessarily reconstruct the optimal solution online. In particular, the offline optimal solution fully accepts any item with a unit value strictly greater than é. However, it may only partially admit item(s) with value é. Hence, even with a perfect prediction of the exact value é, the online cannot optimally solve the problem since the optimal admittance policy for items with exact value é is unclear. In practice, one may argue that obtaining point prediction of the exact value 0 is almost impossible, motivating a more coarse- -raiind interval prediction.
to design and analyze
3. Algorithms with Trusted Predictions
Definition 2.3 (Prediction Model II: Interval Prediction). A lower bound É and upper bound u on the actual value of i (Def 2. are given to the cearning-augmented online algorithm, satisfying the condition E < 0 < u.
We first present lower bound results for OKP algorithms with trusted point predictions. Then, we design OFKP algo- rithms for trusted point and interval predictions that achieve optimal competitive ratios (i.e., matching lower bound).
In this prediction model, the quality of the prediction de- grades as the ratio a/e increases. In an extreme case of u = e, the interval prediction degenerates to the aforementioned point prediction. On the other hand, with u- = and L, the problem degenerates to classic OKP problem (i.e., with- out predictions but with bounded value assumptions) when only prior knowledge of the unit value bounds is available.
3.1. Lower Bound for Trusted Point Predictions
In what follows, we show that even with an exact point prediction of the critical value i, no deterministic ran- domized naugmntg- online algorithm can achieve I-competitiveness (i.e., no algorithm can match the offline optimal solution on all instances).
Comparisons to related prediction models. The notion of predicting the critical value has been explored in special case of CFKP known as the online search problem (Sun et al., 2021a; aa; Lee et al., 2024). In this problem, all item
Theorem 3.1. Given an exact prediction on the critical value é, no (deterministic or randomized) online algorithm for OPKP can achieve a competitive ratio smaller than 1 + min(1,40)
4

---

Near-Optimal cesistency-Rbbstteess Trade-Offs for Learning-Augmeente Online Knapsack Problems
Recall that w is the total weight of items with the critical value é. This result implies a 2-comperitive lower bound when @ 2 1, even with an accurate point prediction of 0. To understand the intuition, consider a special case when a = 1. If an algorithm is presented with the first item (i; 1), it cannot admit the entire item, as the next item could be (oo, 1 - +) (with e - 0); on the other hand, it must admit a portion of this item since there may be no following item. The optimal balance is to admit 1/2 of the first item, giving 2-competitive lower bound. A refined bound can be attained for instances with smaller values of w. The full proof is given in Appendix A. By nature of the CFKP relaxation,
Algorithm 1 PP-a: An improved (1 + mi](1,0])-
competitive algorithm with point prediction
Input: prediction
Output: (d))ag(m]
Initialization: w0 0, s0 =
for each item i (with unit value es and weight wyy do
if v, < i then
a; = 5
H; = 0
D. item is rejected
else if v > 0 then
Wn = Wi-1
v; w// + w b. item is partially accepted
Theorem 3.1 also lower bounds the harder case of OIKP.
else if n2 then
W; = 0 + min (w;, 1 Wi-13
3.2. OFKP Algorithms with Trusted Point Predictions
22 = min -in
8:-1 min( w..1-
I+
1+
item is partially accepted
We first present PP-b, musted-prediction algorithm for OFKP that is 2-competitive when given the exact pre- diction 0. Then, we present PP-a, a refined algorithm that improves the instance- dependetd competitive ratio to 1 + min (1, (1, ,,), matching the lower bound. Recall that @ is unknown and not provided by prediction (see Def. 2.1). We note that a naive trusted-prediction algorithm that ac- cepts all items with values 2 è results in an arbitrarily large worst-case competitive ratio (see Appendix A.5 and A.6.4).
Update 8, 8:-1 24
approach ensures that PP-a a selects an appropriate portion on either side of the prediction to achieve the desired bound.
Theorem 3.3. Given a point prediction, PP-a is (1 + min , 4 ( competiiive for OFKP,
Without prior knowledge of u, PP-a employs a "prehuying" strategy for items with values > 0. The extra capacity allocated to these items always has higher unit value than 0, allowing PP a to reduce acceptances from i based on how much extra capacity it has allocated in previous items. PP-a maintains a lower bound on & that increments each time an item with value è arrives. This lower bound determines PP a's strategy for values > 6. The remaining challenge is to ensure that PP-a does not overfill the knapsack, and attains at least 1 1/(1 + min OPT. We give the full proof in Appendix A.6.6.
PP-b: basic trusted point-prediction 2-competitive al- gorithm. We present an algorithm (pseudocode in Alg. 5) that, given the exact value of é, is 2-competitive for OFKP. The idea is to set aside half of the capacity for high-valus items (> 0) and allocate the other half for minimum ac- ceptable items with value 0. By doing so, PP-b obtains at least half of either part from OP''s knapsack. Note that achieving a competitive ratio of matches the lower bound in Theorem 3.1 for general a (i.e., across all instances).
() (1,4)
of the profit obtained by
Theorem 3.2. Given a point prediction, PP-b is 2- competitive for OFKP.
Intuition behind prebuying. The key idea of prebuying is that PP-a proactively reserves capacity for items with values strictly greater than the predicted critical value é, even before observing all such items. This is done to better utilize the knapsack when 4, the total weight of items at é, is small. If the algorithm later encounters many items at é, it dynamically reduces the amount allocated to higher-value items. This contrasts with reserve-thens then-greedy strategies, where reservations are fixed in advance.
Proof Sketch. PP-b selects min(1/2, 9/2) at ú, which is at least half of the profit that OPT obtains from items with value é. Let 2 < 1 be the total weight of items with value > G. PP-b accepts half of these items above the critical value, again obtaining at least half of OPT's profit. Moreover, we can show that PP b does not violate the knapsack constraint. The full proof is in Appendix A.6.5.
3.3. Trusted Interval Predictions
We next show how to modify PP-b to achieve the instance- specific lower bound of + min ( (1,0} from Theorem 3.1.
In this section, we present an algorithm that uses interval predictions [e, u). where i [e, u| -his is motivated by e.g.. uncertainty quantification schemes that provide a bound on the prediction error A, such that upper and lower bounds can be modeled as confidence interval é = ã - A < 0 and u = Ü+ 2 6, where is the predicted critical value.
PP-a: An improved 1 + min (1, ccopetitiive algoritlum PP-a leverages the observation that it can accept more than half of items with value > è when @ is low. However, since w is unknown, it exploits a "prebuying" strategy, initially selecting entire items with values > è before adjusting its selections upon observing items with value é. This adaptive
IPA: An interval prediction prediction-based algorithm. IPA builds
5

---

Near-Optimal Consistency-Robuuttooss Trade-Offs for Learning-Augmenter Online Knapsack Problems
Algorithm 2 IPA: An Interval-Prediitioon-aas Algorithm
4. Leveraging Untrusted Predictions
for OFKP
In this section, we extend our results to the case of imperfect or untrusted predictions. We present MIX, an algorithm that mixes the decisions of a prediction-based algorithm with a robust baseline, and prove its consistency and robustness. Furthermore, we give corresponding lower bound on the best achievable consistency and robustness using a point prediction - this shows that MIX achieves a nearly-optimal consistency robbssstess trade-off. Although the technique of combining algorithms is common the literature (Im et al., 2021; Christianson al., 2022; Lechowiez et al., 2024), it is not often the case that such technique approaches the optimal trade-off, making our result particularly noteworthy.
Input: interval prediction É, u, robust algorithm A with competitive ratio a
Output: online decisions 2:,5 Initialize A
for each item (with unit value U, and weight w;) do if e l then === 0 b item is rejected
else if v; > u then
2t = a+I x w; > item is partially accepted
else if u/ E [e, u] then
Pass item to algorithm A
2t a+I x xz!
item is partially accepted
MIX: A robust and consistent algorithm. MIX combines ZCL, the optimal (In(%/t) + ---ompetitivee OFKP algo- rithm, with one of the trusted OFKP prediction algorithms presented so far (e.g., PP-a in Alg. 1, IPA in $ 3.3). If the prediction is correct, we say that the "inner prediction algo- rithm" ALG is c-competitive, where c is the corresponding bound proved in the previous section.
on PP-b and is devised to solve OFKP when given interval predictions. It allocates a dedicated portion of the capacity for values higher than u, rejects all items with values lower than L, and employs a sub-algorithm (c.g., 2CL) to solve OFKP within the interval [e, u.. The results are then com- bined to yield a competitive result with a competitive ratio of a + 1, where a represents the competitive ratio of the sub-algorithm. We summarize pseudocode for IPA in Alg. 2, and give the competitive result for IPA below:
For robustness, we follow prior work (Sun et al., 2021b; Zhou et al., 2008; EI- Yaniv et al., 2001) and assume unit val- ues are bounded, i.c., v; E [L. UJ, Vi E [n]] Note that L and U are not related the predicted interval [é, u). MIX bal- ances between the inner algorithms (worst-case optimized ZCL and prediction-based ALG) by setting trust parame- ter X E [0, 1]. Both algorithms run in parallel when an item arrives. MIX receives an item with unit value and weight w; as input. MIX first "offers" this item to the inner prediction- ALG, receives its decision é;, and then "of- fers" this item to the inner robust 2 ZCI, receiving a decision ã4. Then MIX accepts I; Aē; + (1 - A)ã; fraction of the item. Note that when À = 1, MIX makes the same decisions as the inner prediction ALG, and when X = 0, MIX makes the same decisions as the inner robust ZCL. The inner ALG is chosen based on the type of prediction received, e.g., a point or interval prediction. Theorem 4.1 gives bounds on the consistency and robustness of MI X, which gives corre- sponding russitennc-rrbusttee results for the algorithms in the previous section (i.e., for point and interval prediction models, see Theorem 3.3 and Theorem 3.4, respectively).
Theorem 3.4. Given an interval prediction [e, u) and an algorithm for OF with worst-case competitive ratio of o, IPA (a + -)-ooppeti for OFKP.
Proof Sketch. For unit values higher than u, IPA allocates 1/a+1 of knapsack capacity. Within the range [e, u]. it em- ploys robust sub-algorithm, denoted as A, which is a- competitive- - it is allocated 9/a+1 fraction of the knapsack's s capacity. Within the interval [c. u). obtaining a c/a+1 frac- tion of A's solution intuitively yields an (a+ --coppetiiiee solution against OPT. The remaining challenge is to demon- strate that the bound holds across both parts (i.c., beyond the interval [e, u)). The full proof is in Appendix A.6.7. D
Corollary 3.5. Given an interval prediction [f, u], IPA is (2 + In( (cmmmo-comeeiievveeeeeeeeeee for OFKP when the sub-algorithm is given by Alg. 4 (ZCL). Theorem 3.4 and Corollary 3.5 show that IPA is (2 + In ((v/a))-commeeittt
when using an optimal OKP method as the sub-algorithm (e.g.. ZCL). A natural question to ask is whether this competitive ratio for trusted interval predic- tions can be improved upon by any other algorithm - in the following, we answer this in the negative.
Theorem 4.1. MIX is lo(5/s)+1
(1-X) -robust and --consistent for OFKP for any X E (0, 1), where e is the competitive ratio of
the inner prediction ALG with an accurate prediction.
Proof. MTX's profit is described by MTX(X](I) AALG(I) + (1 - (T) For consistency, the predic- tion is correct and ALG is c-competitive. Thus, we ob-
Theorem 3.6. Given an interval prediction [e, u), no (de- terministic or randomized) online algorithm for OFKP can achieve a competitive ratio better than (2 + In(w/z)). The result in Theorem 3.6 (full proof in Appendix A.6.2) implies that IPA achieves the optimal competitive ratio for any OKP algorithm using trusted interval predictions.
tain that (I) AALG(I), and MIX is f-consistent. For robustness, consider the case where the prediction is wrong. If ALG obtains no profit, we have MIX(A](Z) > (1 - (-))ZCL(Z), and MIX In(7/2)+1 In(//))+_rrobust.
(1-A)
6

---

Near-Optimal Consistency-Robusttess Trade-Offs for Learning-Augmeente Online Knapsack Problems
In(UW)
Upoer bound (Thecrem 4.1)
Algorithm 3 The Fr2Int algorithm
(2)
cons
Asymptatic lower bound (3)
Input: OFKP algorithm ALG, error parameter 6, preci- sion parameter e, bounds U. L
Output: Online decisions {dr)
Initialization: Arrays A(o..... (log1+ (4/D]] t- O. R R.O..... ( + 0
IntU))++
20
30
50
robustness
for each item i (with unit value vs and weight un:) do Send item i to ALC and obtain OFKP decision c;
Figure 1. The consislency-robuuttees. upper bound of MIX using a prediction of the critical value i (Theorem 4.1) and the lower hounds ((2) and (3)), with U/r. = 1000.
j 4 (151)+((//)))
R[i + R[i] + 8. U3
We use an example to further clarify the robustness of MIX. Set À = 3.- Assume that the prediction predictio-bbssd algorithm ALG obtains no profit. The ZCL algorithm is c-competitive.
if A[j] < R[j]- 3=0(1lo then
1+5
2; K- ut item is fully accepted
Ali] - Ali] + 2; -2:-0 Vi
Then, we have
else
1 MIX[A](Z) - 2 2- 0 (CL
1 OPT c
22 +- 0
> item is rejected
which shows MIX is 2c-competitive. Thus, for given non- zero X, MIX maintains a finite competitive ratio even in worst-case prediction scenarios, highlighting the role of the robust subroutine in guaranteeing performance.
assuming items have small individual weights and bounded unit values. It is worth mentioning that without any of these two assumptions, there exists no algorithm with meaningful competitive ratio (see Theorem A. A.2). In the exist- ing OKP literature without predictions, prior work notes that OIKP can be solved using discretized variants of the threshold-basee algorithmss for OFKP (Zhou et al., 2008; Sun et al., 2021b). However, because the algorithms that we present in 3 do not use the paradigm of threshold- based design, this straightforward connection is not applicable. In- stead, we propose a novel partitioning technique that divides the possible unit values into discrete intervals, allowing a conversion algorithm (Fr2Int, see Algorithm 3) to use any OFKP algorithm as a subroutine and achieve the same competitive ratio for OIKP. We start by formalizing the value partitioning component of the algorithm below.
4.1. Optimal Consistency- Roobustnessss Trade-Offs
We ask whether any considerable improvement can be made in the consistency-robusmess trade-off, i.e., whether an al- gorithm using succinct predictions can achieve better consis- tency for a given robustness (or vice versa). In what follows, we show that MIX nearly matches the best consistency- robustness trade-off for a critical value prediction é.
Theorem 4.2. Given an untrusted prediction of the critical value, any deterministic y-robust algorithun for OKP (where y E [In((/D) + 1, 00) is at least ny-consistent for
L
1
n 2 max 2
{2
---
1 1- In 10 (V/e)
U
(2)
Definition 5.1 (Value Partitioning). Recall that for OIKP, all item unit values lie in the interval [L,U], UJ. We divide this interval into K sub-intervals G1, G2. GK as follows. Let ò > 0 be small and let U = L(1 + 5) for some integer K. Then, for any E [K]. let G2. = [L(1 + 5y*-1, L(1 + 8)²). Note that by definition, G2 cannot contain values that differ by more than a multiplicative factor of (1 ++ +)).
Furthermore, in the limit as U/L + oc, any 2/ X-consistent (for some X E (0, 1)) algorithm is at least B-robust, for
B 1+ In(12)))) 1 A o(1)= = - 1-X
(1+1((4))
This result (full proof in Appendix A.6.3) implies that MTX achieves the nearly optimal trade-off between consistency and robustness. In Fig. 1, we plot the consistency- robusttess upper bound from Theorem 4.1, along with the lower bounds given by (2) and (3). All three bounds behave similarly. exhibiting a convex trade-off. The gap between the upper and lower bound due to constants in the proof of (3). We disregard consistency > In(4/r) + 1 since algorithms without predictions (e.g., ZCL) give better guarantees.
We now describe the "conversion" algorithm Fr2Int (see Algorithm 3) that connects OFKP with OIKP. Given any OFKP algorithm denoted by ALG, Fr2Int uses the value partitioning in Definition 5.1 to solve OIKP by simulating the fractional actions of ALG. When an item arrives for OIKP with a value in interval Gg, the item is accepted if the sum of values of previously accepted G3 items in the integral knapsack is less than the sum of values from interval G5 in the sinulated fractional one. With small item weights, this ensures that the total value in the actual knapsack is close to the simulated one, thus inheriting the competitive bound of OFKE. For an OFKP algorithm ALG, we denote its corresponding CIKP variant as Fr nnt-A....
5. Connecting OIKP with OFKP
In this section, we present a general result that connects the fractional case (OFKP) with the integral case (OIKP),
7

---

Near- Near-Optimal Consistency- Consisteney-Robustnees Trade-Offs for Learning-Augmentt Online Knapsack Problems
1.0
ZCL
ZCL
PP-b
ampirical competitive ratio
PP-b
empinccal compatt ratto
PP-a
empll amplrccall CDF
(PA(10%)
PP-n
0.6
0.4
PP
PP-b
0.2
PP-a
MIX
(PA(25%)
0.9.
1.5 2.0 2.5 3.0 3.5 4.0 4.5 5.0
empirical competitive ratio
300-000
U0L01000
500-5000
00L-20000
W=20.99
0=0.45
6=0.63
d=0.78
(a)
(b)
(c)
Figure (a) The CDF plot the empirical competitive ratio of different algorithms; (b) The performance of PP-b, PP-a and IPA
versus ZCL U/2 varies; and (e) The performance of PF-b, PP-a, and PP-n against ZCL when w varies.
Theorem 5.2. Given a 7-competitive online algorithm ALG for OFKP and fixed parameter ô 0, if the max- imum item weight of OIKP is upper bounded by e < 1/1lggn4, 4/4++,, then the algorithm Fr Fr2Int-ALG is r (100)1((108a1)) 11]]+1 competitive for OIKP.
6. Numerical Experiments
In this section, we present a case study of our proposed algo- rithms. We compare against baselines that do not use predic- tions (i.e., ZCL (Zhou al., 2008)), and the existing SEN- TINEL
algorithm from prior work (Im et al., 2021), using both synthetic and real datasets.! We defer additional experiments and details to Appendix A.7.
Fr2Int extends all our results presented in the con- text of OFKP thus far (e.g., PP-a in Theorem 3.3, IPA
in Theorem 3.4, MIX in Theorem 4.1) to the case of OIKP with minimal competitive loss. Note that when set 8 7 0 and the maximum item weight e is small (i.e., < < 6/DoBa++ 0/x]+1), Fr2Int becomes lims-s07 148/1-5 approaching 7-competitive. The loss factor 148/1-((Dosa)) 1)c]+1) results from the discretization of the value range and the discrete nature of the item sizes, and it is designed to ensure the feasibility of the integral algorithm after converting from fractional algorithm.
Experimental setup and comparison algorithms. To val- idate the performance of our algorithms, we conduct four sets of experiments. generated data, where the value and weight of items are randomly drawn from power-law distribution. Unless oth- erwise specified, the lowest unit value is I. highest unit value is U 1000. Weights are drawn from power law and normalized to the range [0, 1]. We report the cumulative density functions (CDFs) of the empirical competitive ratios, which illustrate both the average and worst-case performance of the tested algorithms.
the first set, we use synthetically
and the
Proof Sketch. Sketch. Fr2Int keeps track of the items accepted in ALG'S simulated fractional knapsack with list R (line Algorithm 3). In lines 8-12, Ir2Int checks how the items it has accepted far (saved in list A) compare against the simulated knapsack- this compels Int to accept items that approximate those chosen by ALG. The remaining challenge is to show that Fr2Int does not overfill the knapsack. For this, the partitioning method allows us to bound the value of a range
To report the empirical competitive ratio of different algo- rithms, solve for the offline optimal solution described in Appendix A.2. We compare the results of the following algorithms under several experimental settings: (1) ZCL: the existing optimal algorithm without predictions (Alg. 4); (2) РP-n: a naive point-predictee prediction- algorithm that accepts any item at or above the predicted critical value é; (3) PP-b: 2-competitive algorithm for trusted predic- tions (Alg. 5); (4) PP-a: (1 + min -coppeiittteettiieeee
weight. We can show w((A (A[[j))- L- (1 + 5) A[j] w(Ali)) L. LL (1+ 5)5+1, which helps bound the weight using the partitioning idea. The full proof is in Appendix A.6.10.
algorithm (Alg. 1): (5) IPA: trusted iiterval-prediccion
based algorithm (Alg. 2); (6) MIX:
algorithm (6 4); (7) Fr2Int- PP-a: converted OIKP ver- sion PF-a; and (8) SENTINEL algorithm using frequency predictions (Im et al., 2021). For IPA, we report the interval prediction range u E as a percentage of [L, U] and set to 15%, 25%, and 40%. The notation MIX, denotes instances of MIX under different values of trust parameter X, which we set according to X E (0.3, 0.5. 0.9}.
We note that by nature of the OFKP relaxation, the lower bounds for OFKP (namely, Theorem 3.1 and Theorem 4.2) extend OIKP. This follows by observing that on the in- stances constructed in these proofs, the optimal fractional solution obtains the same value as the optimal integral so- lution when each fractional item can be subdivided into many small OIKP items with the same value density. Since an arbitrary online algorithm can only do worse when it is restricted accepting entire items, the bounds follow.
OOr code is available https://github.com moreda-a/OKP.
8

---

Near-Optimal Seiiisteney-Rbbustteee Trade-Offs for Learning-Augmenter Online Knapsack Problems
Experimental results. Fig. 2(a) reports the cumulative distribution function (CDF) of empirical competitive ra- tios for six tested algorithms on 2,000 synthetic instances algorithms, PP-a
Disclaimers
This report was prepared as an account of work sponsored by an agency of the United States Government. Neither the U.S. Government nor any agency thereof, nor any of their employees, makes any warranty, express implied, or assumes any legal liability or responsibility for the accuracy, completeness, or usefulness of any information, appara- tus, product, or process disclosed, or represents that its use would not infringe privately owned rights. Reference herein to any specific commercial product, process, or service by trade name, trademark, manufacturer, or otherwise does not necessarily constitute imply its endorsement, recommen- dation, or favoring by the U.S. Government or any agency thereof. The views and opinions of authors expressed herein do not necessarily state or reflect those of the U.S. Govern- ment or any agency thereof.
of OF KP. Amongst the prediction-basee achieves the best performance in average and worst-case, verifying the results of Theorem 3.3. While P2-n n outper- forms most others on average (except PP-a), its worst-case performance is worse than ZCL (the optimal algorithm with- out predictions); this observation verifies bad edge cases for PP-n identified in Theorem A.4. Finally, even with relatively wide interval prediction, IPA outperforms ZCT, in both average and worst-case. We also report the impact of parameters on the performance of the tested algorithms. Given a trusted (i.e., correct) succinet prediction, our theo- retical results show that our algorithms (PP-b, PP-a, a, IPA) can obtain competitive ratios independent of the ratio U/z, in contrast to classic online algorithms such as 2CL. In Fig. 2(b), we verify this by varying U/r. These results show that the empirical competitive ratio of ZCL increases along with U/L, while prediction- basedd algorithms are robust to these variations. In Fig. 2(c). we vary the value of & using four values of 0.29, 0.45, 0.63, and 0.78. Due to its design (Theorem 3.3), PP-a's a's performance is better with smaller values of W, while other algorithms see less benefit.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
References
7. Conclusion
Angelopoulos, S., Kamali, S., and Shadkami, K. Online bin packing with predictions. J. Artif. Int. Res., 78, Jamuary 2024. ISSN 1076-9757 doi: 10. 3/jjair 1. 14820. URL pttps://doiin org/ / jair 14820.
In this paper, we propose near-optimal caaming-augmentte algorithms for both fractional and integral knapsack prob- lems using succinet and practical predictions. A number of questions remain for future work. Although the assumption of small item weights is standard in the (integral) OKP liter- ature (Zhou et al., 2008; Sun et al., 2021b; Im et al., 2021), questions remain about an algorithm that uses untrusted predictions without such an assumption. It would be inter- esting to further explore fundamental trade-offs between consistency and robustness the case of interval predic- tions- there is growing literature on uncertainty quantifica- tion (Sun et al., 2024) in online algorithms that could inform e.g., fine-grained consistency-robusteee trade-off bounds based on the error of given predictor.
Antoniadis, A., Coester, C., Elias, M., Polak, A., and Simon, B. Online Metric Algorithms with Untrusted Predic- tions. In Proceedings of the 37th International Confer- ence on Machine Learning, pp. 345-355. PMLR, Novem- ber 2020a.
Antoniadis, A., Gouleakis, T., Kleer, P., and Kolev, P. Sec- retary and Online Matching Problems with Machine Learned Advice. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 7933- 7944. Curran Associates, Inc., 2020b.
Acknovledgements
Antoniadis, A., Coester, C., Eliáš, M., Polak, A., and Simon, B. Augmente Dynamic Power Management with Multiple States via New Ski Rental Bounds, 2021.
This research was supported in part by funding from the Na- tional Science Foundation under grant numbers CAREER- 2045641, CPS-2136199, and CNS-2325956, and a research gift from Adobe Research. This material is based upon work supported by the U.S. Department of Energy, Office of Sci- ence, Office of Advanced Scientific Computing Research, Department of Energy Computational Science Graduate Fel- lowship under Award Number DE-SC0024386. We thank the anonymous reviewers for their valuable feedback.
Antoniadis, A., Boyar, J., Eliás, M., Favrholdt, L. M., Hoeksma, R., Larsen, K. S., Polak, A., and Simon, B. Paging with succinct predictions. In International Con- ference on Machine Learning, pp. 902-9522289889 PMLR, 2023.
Ball, M. O. and Queyranne, M. Toward robust revenue management: Competitive analysis of online booking. Oper. Res., 57(4):950 963, August 2009.

---

Near-Optimal Sennistene--Robustneee Trade-Offs for Learning-Augmeente Online Knapsack Problems
Balseiro, S., Kroer, C., and Kumar, R. Single-Leg Revenue Management with Advice, 2023.
Buchbinder, N. and Naor, Online primal-dual algorithms for covering and packing. Mathematics of Operations Research, 34(2):7002286, 2009.
Bamas, E., Maggiori, A., and Svensson, O. The Primal- Dual method for Learning Augmented Algorithms. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Pro- cessing Systems, volume 33, pp. 20083-20094. Curran Associates, Inc., 2020.
Böckenhauer, H.-J., Hromkovič, J., Komm, D., Krug, S., Smula, J., and Sprock, A. The string guessing problem as a method prove lower bounds on the advice complexity. Theoretical Computer Science, 554:95-108, 2014a. ISSN doi: 0304-3975.
006. Computing and Combinatorics.
Benomar, Z. and Perchet, V. Advice querying under budget constraint for online algorithms. Advances in Neural Information Processing Systems, 36, 2024.
Böckenhauer, H.-J., Komm, D., Královič, R., and Ross- manith, P. The online knapsack problem: Advice and randomization. Theoretical Computer Science, 527:61- 72, 2014b. ISSN 0304-3975, doi: http:://doi.or/110.1001 j.tcs.2014.01.027.
Böckenhauer, H.-J., Komm, D., Královič, R., Královič, R., and Mömke, T. On the Advice Complexity of Online Problems. Dong, Y., Du, D.-Z., and Ibarra, O. (eds.), Algorithms and Computation, pp. 331-340, Berlin, Hei- delberg, 2009. Springer Berlin Heidelberg. ISBN 978-3- 642-10631-6.
Christianson, N., Handina, T., and Wierman, A. Chasing Convex Bodies and Functions with Black-Box Advice. In Proceedings of the 35th Conference on Learning Theory, volume 178, pp. 867-908 PMLR, 02-05 Jul 2022.
Böckenhauer, H.-J., Komm, D., Královič, R., and Královič, R. On the Advice Complexity of the k-Server Prob- lem. In Aceto, L.., Henzinger, M., and Sgall, J. (eds.), Automata, Languages and Programming, pp. 207-218, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. ISBN 978-3-642-22006--
Christianson, N., Shen, J., and Wierman, A. Optimal robustness-consistenny tradeoffs for Searning-augmentt metrical task systems. In International Conference on Artificial Intelligence and Statistics, 2023.
Borodin, A. and EI- Yaniv, R. Online Computation and Competitive Analysis. Cambridge University Press, 1998.
Clemente, J., Adorna, H., and Fernandez, P. Online Algo- rithms with Advice for the k-search Problem. Philippine Journal of Science, 151(4), May 2022. doi: 10.56899/ 151.04.03.
Borodin, A., Linial, N., and Saks, M. E. An Optimal On- Line Algorithm for Metrical Task System. J. ACM, 39 (4):745-763, oct 1992. ISSN 5411- doi: 146585. 146588.
Cygan, M.. Jež, L., and Sgall, J. Online knapsack revisited. Theory of Computing Systems, 58:153-190, 2016.
Bostandoost, R., Sun, B., Joe- Doe-Wong C., and Hajiesmaili, M. Near-optimal online algorithms for joint pricing and scheduling in charging networks. In Proceedings of the 14th ACM International Conference Future Energy Systems, pp. 72-83, 2023.
El- El-Yaniv, R., Fiat, A., Karp, M., and Turpin, G. Op- timal Search and One-Way Trading Online Algorithms. Algorithmica, 30(1):101-139, May 2001. doi: 10.1007/ $00453-001-0003-00
Giliberti, J. and Karrenbauer, A. Improved Online AL- gorithm for Fractional Knapsack the Random Order Model. In Approximation and Online Algorithums, pp. 188-205. Springer International Publishing, 2021. doi: 10. 10.1007797--33 --177888----------00 0000-20002--880
Boyar, J., Favrholdt, L. M., Kudahl, C., and Mikkelsen, J. W. Advice Complexity for a Class of Online Problems. In Mayr, F. W. and Ollinger, N. (eds.), 32nd Interna- tional Symposium on Theoretical Aspects of Computer Science (STACS 2015), volume 30 of Leibniz Interna- tional Proceedings in Informatics (LIPIcs), pp. 116-129, Dagstuhl, Germany, 2015. Schloss Dagstuhl-Leibnic Zentrum fuer Informatik. ISBN 10. 00442001.PIcs.STACCS 20.55.....11111 16.
Im, S., Kumar, R., Montazer Qaem, M., and Purohit, M. On- line Knapsack with Frequency Predictions. In Advances in Neural Information Processing Systems (NeurIPS), vol- ume 34, pp. 2733-2743, 2021.
doi:
Boyar, J., Favrholdt, L. M., and Larsen, K. S. On- line unit profit knapsack with untrusted predictions. Schloss Dagstuhl - Leibmiz-Zentrum für Informatik, 2022. doi: 10.2300LIPCCS..SW.22222.00 pttps://dropge wtwp:ops.ddagttul.eeeeeeeeeeeeee document/10. http://t.......././/.ee #230/LIPICS, SWAT. www..s22...2.22.22222222
Jiang, Z., Lu, P., Tang. Z. G., and Zhang, Y. Online Selec- tion Problems against Constrained Adversary. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th Inter- national Conference on Machine Learning, volume 139 Proceedings of Machine Learning Research, pp. 5002- 5012. PMLR, 18 24 Jul 2021.
URL
10

---

Near-Optimal Consistency-Robustnee Trade-Offs for Learning-Augmenter Online Knapsack Problems
Komm, D., Královič, R., and Mömke, T. On the Advice Complexity of the Set Cover Problem. In Hirsch, E. A., Karhumäki, J., Lepistö, A., and Prilutskii, M. (eds.), Com- puter Science - Theory and Applications. pp. 241-252, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. ISBN 978-3-642-30642-6
Mitrinovic, D. S., Pečarić, J. E., and Fink, A. M. Inequalities Involving Functions and Their Integrals and Derivatives, volume 53, Springer Science & Business Media, 1991.
Noga, J. and Sarbua, V. An online partially fractional knap- sack problem. In 8th International Symposium on Parallel Architectures.Algoriinn
and Networks (ISPAN'OS), pp.
Kottarathil,
Bitcoin Historical Dataset.
5 2p0-,0055. doi: 10.1 (0.1109/SPANN2205.115
https: //www http///wwwwwwll..eeeee ctt haammdatann cataetts//ss////////aammm.. prasonnkottarrethi//bbd.mo
2018. [Li-
Purohit, M., Svitkina, Z., and Kumar, R. Improving On- line Algorithms via ML Predictions. In Bengio. S., Wal- lach, H., Larochelle, H., Grauman, K., Cesa- Jesa-Bianchi, N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
censed under CC BY-SA 4.0].
Langley, P. Crafting Papers on Machine Learning. In Lang- ley, P. (ed.), Proceedings of the 17th International Confer- ence on Machine Learning (ICML 2000), pp. 1207-1216, Stanford, CA, 2000. Morgan Kaufmann.
Lechowicz, A., Christianson, N., Zuo, J., Bashir, N., Ha- jiesmaili, M., Wierman, A., and Shenoy, The On- line Pause and Resume Problem: Optimal Algorithms and An Application to Carbon-Aware Load Shifting. Proc. ACM Meas. Anal. Comput. Syst., 7(3), Dec 2023. doi: 10.1145/3626778 URL https: 1145/3626776.
Reiss, C., Tumanov, A., Ganger, G. R., Katz, R. H., and Kozuch, M. A. Heterogeneity and dynamicity of clouds at scale: Google trace analysis. In Proceedings of the Third ACM Symposium on Cloud Computing, pp. 1-13, 2012.
Sun, B., Lee, R., Hajiesmaili, M., Wierman, A., and Tsang, D. Pareto-optimal learning-augmented algorithms for online conversion problems. Advances in Neural Infor- mation Processing Systems, 34:10339-10350 2021a.
Lechowicz, A., Christianson, N., Sun, B., Bashir, N., Ha- jiesmaili, M., Wierman, A., and Shenoy, P. Online Conversion with Switching Costs: Robust and Learning- Augmented Algorithms, 2024.
Sun, B., Zeynali, A., Li, T., Hajiesmaili, M., Wierman, A., and Tsang, D. H. Competitive Algorithms for the Online Multiple Knapsack Problem with Application to Electric Vehicle Charging. Proc. ACM Meas. Anal. Comput. Syst., 4(3), jun 2021b. doi: 10.1145/3428336.
Lee, R., Sun, B., Lui, J. S., and Hajiesmaili, M. Pareto- Optimal Learning- Augmented Algorithms for Online k- Search Problems, 2022.
Lee, R., Sun, B., Hajiesmaili, M., and Lui, J. C. Online Search with Predictions: Pareto-optimal Algorithm and its Applications in Energy Markets. In The 15th ACM In- lernational Conference on Future and Sustainable Energy Systems, pp. 50-71, 2024.
Sun, B., Yang, L., Hajiesmaili, M., Wierman, A., Lui, J. C. S., Towsley, D., and Tsang, D. H. The Online Knap- sack Problem with Departures. Proc. ACM Meas. Anal. Comput. Syst., 6(3), Dec 2022. doi: 10. 145/3570618.
Lorenz, J., Panagiotou, K., and Steger, A. Optimal Al- gorithms for k-Search with Application in Option Pric- ing. Algorithmica, 55(2):311-322 August 2008. doi: 10.1007/s004433008-991177
Sun, B., Huang. J., Christianson, N., Hajiesmaili, M., and Wierman, A. Online Algorithmss with Uncertainty- Quantified Predictions. In Proceedings of the 41st In- ternational Conference on Machine Learning (ICML), Vienna, Austria, July 2024.
Lykouris, T. and Vassilvtiskii, S. Competitive Caching with Machine Learned Advice. In Dy, J. and Krause, A. (eds.), Proceedings of the 35th International Conference on Ma- chine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 3206-3305. PMLR, 10-15 Jul 2018.
Vondrák, J. and Zenklusen, R. Approximating the stochastic knapsack problem: The benefit of adaptivity. In 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 208-217. IEFE, 2011. doi: 10.1109/ 201
Ma, W., Simchi-Levi, D., and Zhao, The competitive ratio of threshold policies for online unit-density knapsack problems. arXiv preprint arXiv: /907.08735, 2019.
Wei, A. and Zhang, F. Optimal Robustness Dobustness-Consisteeeyy Consistency Trade-off's for Leamiin-AAugmente Online Algorithms. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Pro- cessing Systems, volume 33. pp. 8042-805 8053. Curran As- sociates, Inc., 2020.
MarchettiiSSpaccane A. and Vercellis, C. Stochastic on- line knapsack problems. Mathematical Programming, 68 (1-3):73-104 January 1995. doi: 10. 1555077750018855888

---

Near-Optimal Sunsisteney-Robusteess Trade-Offs for Learning-Augmeente Online Knapsack Problems
Yang, L.,, Zeynali, A., Hajiesmaili, M. H., Sitaraman, R. K., and Towsley, D. Competitive Algorithms for Online Multidimensional Knapsack Problems. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 5(3), Dec 2021.
Zeynali, A., Sun, B., Hajiesmaili, M., and Wierman, A. Data-driven Competitive Algorithms for Online Knap- sack and Set Cover. Proceedings of the AAAI Confer- ence on Artificial Intelligence, 35(12):10833-1084 May 2021. doi:
Zhang, Z., Li, Z., and Wu, C. Optimal posted prices for online cloud resource allocation, Proceedings the ACM on Measurement and Analysis of Computing Systems, (1):1-26, 2017.
Zhou, Y., Chakrabarty, D., and Lukose, R. Budget Con- strained Bidding in Keyword Auctions and Online Knap- sack Problems. In Proceedings of the 17th Interna- tional Conference on World Wide Web, WWW '08, pp- 1244,1244, New York, NY. USA, 2008. Association for Computing Machinery. ISBN 978 605580852. doi: 10.1 10.1445/13774477.13777777
12

---

Near-Optimal Sunsistency-Robusttess Trade-Offs for Learning-Augmented Online Knapsack Problems
A. Appendix
A.1. Related Work
We make contributions to two lines of work: (i) work on online knapsack, one-way trading, and related problems, c.g.. k-search, single-leg revenue management, and; (ii) work on online algorithms with advice and describe the relationship to each below.
We
Online Knapsack and Online Search. Our work contributes to the literature on the classic (integral) online knapsack problem first studied in (Marchetti-Spaccamee) & Vercellis, 1995), with foundational results given by Zhou et al. (2008). In the past few years, many works have considered variants of this problem, such as removable items (Cygan et al.. 2016), item departures (Sun et al., 2022), and generalizations to multidimensional settings (Yang et al., 2021). Closer to this work, several studies have considered the online knapsack problem with additional information or in a Garning-augmentte setting, including frequency predictions (Im et al., 2021), online learning (Zeynali et al., 2021), advice complexity (Böckenhauer et al.. 2014b), and stochastic knapsack (Vondrák & Zenklusen, 2011). Most works in this literature focus on the more difficult case of integral item acceptance; thus, connections between this case and the fractional relaxation in the online setting have been relatively understudied in the literature thus far. A few studies have considered online knapsack with fractional item acceptance under slightly different assumptions, including "online partially fractional knapsack", where items are removable (Noga & Sarbua, 2005), or online fractional knapsack in a random order model (Giliberti & Karrenbauer, 2021), where the arrival order of items is a random permutation (i.e. not adversarial). Sun et al. (2021b) motivate the observation that online fractional knapsack is equivalent to the one-way trading problem with a rate constraint for each online price.
The connection between online fractional knapsack (OFKP) and one-way trading (with rate constraint) motivates further connection to another track of literature on problems broadly classified as online search, including problems such as 1-max/ / min search and one-way trading, both first studied by El-Yaniv et al. (2001), k-max / min search (Lorenz et al., 2008), and single-leg revenue management (Ball & Queyranne, 2009). In general, OFKP can be understood as a "bridge" between work on online search and online knapsack. Follow-up works have since considered applications of online search problems and additional variants, including cloud pricing (Zhang et al., 2017), electric vehicle charging (Sun et al., 2021b), switching cost of changing decisions (Lechowicz et al., 2023), and trading (Sun et al., 2021a) and k-search (Lee et al., 2022). However, to the best of our knowledge, none of these works consider the impact of rate constraints.
versions of both one-way
Sharning-Augenntee Algorithms. learned predictions about future inputs in algorithm designs, with the goal of matching the good average-case performance of the predictor while maintaining worst-case competitive guarantees. The concepts of consistency and robustness (Lykouris & Vassilvtiskii, 2018; Purohit et al., 2018) give a formal mechanism to quantify the rff between following machine- learned predictions and hedging against adversarial inputs, particularly with respect to predictions that are very incorrect. This framework has been applied to a number of online problems, including caching (Lykouris & Vassilvtiskii, 2018), ski-rental (Purohit et al., 2018; Wei & Zhang, 2020; Antoniadis et al., 2021), set cover (Bamas et al., 2020), online selection (Jiang et al., 2021). online matching (Antoniadis et al., 2020b), convex body chasing (Christianson et al., 2022), and metrical task systems (Antoniadis et al., 2020a; Christianson et al., 2023), just to name a few. Most relevant to our setting, it has been explored in the context of online knapsack (Im et al., 2021; Zeynali et al., 2021), unit-profit online knapsack (Boyar et al., 2022), one-way trading (Sun et al., 2021a), and single-leg revenue management (Balseiro et al., 2023).
algorithm design is an emerging field that incorporates machine-
An overarching goal in this framework is to quantify and match or nearly match optimal comsistency-rrbuuiieess trade- off' (Wei& & Zhang, 2020). Since gains in consistency generally result in worsened robustness guarantees, it is natural to consider a notion of Pareto-optimality between the two, and ideally to design algorithmss that can achieve this best trade-off for any desired robustness or consistency target. Several works have studied optimal trade-offs for different online problems - the closest results to our setting are for one-way trading (Sun et al., 2021a) and single-leg revenue management (Balseiro et al.. 2023). However, optimal bobustness-consisttees context of online knapsack- - differences in the problem settings of one-way trading and single-leg revenue management result in the substantially different results that we obtain in this work. We also note that the notion of online algorithms with practical and succinct predictions has recently been explored in the context of similar problems such as paging (Antoniadis et al., 2023) and non-clairvoyant job scheduling (Benomar& & Perchet, 2024).
trade-offs have not yet been considered in the
13

---

Near-Optimal Soniiitency-Roussnneee Trade-Offs for Learning-Augmentee Online Knapsack Problems
Leaming-augmmntted algorithms are also closely related to the field of advice complexity, which considers how the performance of an online algorithm can be improved with a specific amount of advice about the input, where the advice is assumed to be correct and is provided by oracle. This field was first established for paging by (Böckenhauer et al., 2009), with results following for many other online problems (Boyar et al., 2015; Böckenhauer et al., 2014a; Böckenhauer et al., 2011; I Komm et al., 2012). Of particular interest to our setting, Böckenhauer et al. (2014h) explore the online knapsack problem with advice, showing that single bit of advice gives a 2-competitive algorithm, but Q2 n)) advice bits are necessary to further improve the competitive ratio. They give an online algorithm with competitive ratio + e for any constant that uses (loggn) bits of advice (Böckenhauer et al.. 2014b, Theorem 13). where n is the number of items. A similar result was also recently shown for the k-search problem by ((Clemente et al., 2022)). To the best of our knowledge, there is no existing work considering the online fractional knapsack problem with advice.
A.2. Offline Optimal Solution
The offline optimal solution to Equation (1) in the fractional OFKP setting is straightforward compute. The optimal solution starts by selecting the item with the maximum unit value amongst all v; s and adds the maximum amount allowed (we) to the knapsack. If there is any remaining capacity to fill, the optimal solution then picks the item with the next highest unit value and adds the maximum amount allowed while respecting the capacity constraint. This process is repeated until the knapsack is completely filled.
For ease of analysis, we let (1/, w() denote the values and weights of the items sorted in descending order. That is, on 2 2/2 2 ... 2 We We let x² denote the portion of item (v/, w!) which is added the knapsack by some algorithm.
With this notation, the offline optimal solution to (1) can be written as:
def ( x;,) w01: u2- ................................ w/
End 0,0, 0, o....
(4)
As seen in (4), the optimal solution selects all the weight of the most valuable items until the knapsack capacity is filled. For lower values, it doesn't It acceptance anything. We refer to the last item with a strictly positive acceptance as the pth item, which is the maximum value of j E [1,n] n] such that v wo < 1.
This optimal solution yields total profit:
OPT (I) = Σ
+
w!!
(5)
1=1
Both (4) and (5) hold if the sum of all w; is greater than or equal to 1, which constitutes the majority of interesting OFKP instances.
In cases where the sum of wy is less than 1, the optimal solution selects all items, which cannot be described by the above equations. To address this scenario, we introduce auxiliary item denoted as 4n+1 with corresponding weight W,+1,, where un+1 = 0 and w 1. It's important to note that this additional item doesn't affect the profit of any algorithm; rather, it simplifies and maintains consistency in mathematical modeling. In the problematic case, where the sum of w; is less than 1, would be equal to n + 1, and both (4) and (5) would still remain valid. We note that this case (where the knapsack can accept all items) is somewhat trivial, as the optimal policy simply accepts all items. In the majority of the paper, we implicitly assume that the sum of all wys is greater than 1.
A.3. Lower bounds for integral
Theorem A.1. There is no deterministic algorithm for the online integral knapsack problem (OIKP) that has a meaningful competitive ratio with or without a critical value prediction when only the bounded unit value assumption holds.
Proof. Consider the following two input instances, each with a critical value 1 and a total critical weight of 2n the critical value:
I : number of items n = 1, (U1, w1) = (1, 2k).
Iz number of items n 2, (v1, wI) = (1, 2x), w2) = (U, 11-A) k).
14

---

Near-Optimal Mannistency-Robustten Trade-Offs for Learning-Augmmenter Online Knapsack Problems
where 6 + 0. The integral offline optimal solutions for the two instances are (PT(I,) 22x and OPT(I2) (1 U),, respectively.
Since both instances have the same critical value and are thus given the same prediction, and since they share the same first item, any online algorithm (whether it uses a prediction or not) will make the same decision regarding the first item, regardless of which instance is presented.
Since this problem is integral, the algorithm must either accept or reject the first item. If it accepts the first item, there not enough capacity for the second item. In this case, the competitive ratio for In is c(I2) = (11-x) which tends to infinity as R approaches O.
2x
In the alternative case, if the algorithm rejects the first item, then in I, the value obtained is O. meaning that the competitive ratio for 1 is also undefined. Thus, in both cases, the competitive ratio of the algorithm is not meaningful.
Theorem A.2. There is no deterministic algorithm for the online integral knapsack problem (OIKP) that has meaningful competitive ratio with or without critical value prediction when only the small weights assumption holds.
Proof. Consider the following set of imput instances, each with a critical value & and a total weight of at the critical value, where K > 0 is the (small) weight of each item:
I number of items 1/k, each item value and weight: (vi, w:) (0, 1t).
For this first instance, any c-competitive algorithm ALG must accept at least 1/c of the items. Other instances have the first instance as the prefix, with the second part defined as follows:
Vi E [1, 1/- 11, I total no, of items 1/a - 1, (Uf+2%4 Wyz1/)) = (d(e+1)) 8, 1 : > 1/k.
Since the critical value is the same across all instances {Zi}. and instance Z, is a prefix of all instances I₁ :j >>> i, we can say that any decision made by a deterministic algorithm on the shorter instance must be repeated in the larger instance as the early part of the input arrives.
Note that the total value of all items in each instance (c 1) Ignoring the knapsack's 's capacity limit, ALG can at most accept this amount. However, in instance i+ 1, the last item's 's actual value is c(c+ 1)² K ccc+ 1)²-1, which is times higher than the sum of all previous values. This implies that, in order for the algorithm to be competitive, it must pick the last item of instance i + 1. The same argument can be made for all i, meaning that the algorithm must accept all items; otherwise, ALG will not be c-competitive for at least one instance Iz.
However, if ALG was to accept all of the items that are necessary for c-competitiveness on all instances {I,} simultaneously, would require a capacity of 1 //c + (1/k- 1 1)x, which simplifies to 1/c+1 - K. As k - O, this is greater than Therefore, there is no fixed e such that an arbitrary ALG can be c-competitive.
A.4. Deferred Pseudocode for Existing Optimal Online Algorithm (ZCL)
Pseudocode for ZCL, Here we give the pseudocode for the baseline algorithm ZCL- this is the known optimal deterministic
algorithm for OKP (i.e., both the fractional (OFKP) and integral (OIKP) cases) without predictions. ZCL takes a threshold function ((z) : [] + [T., U] as input (note that the maximum and minimum unit values U and T. are assumed to be known). d(2) is understood as the pseudo price of packing small amount of item when the knapsack's 's current utilization (i.e. the fraction of total capacity filled with previously accepted items) is 2. The algorithm determines the decision x; by solving optimization problem 2; arg xx 222; f fst ((u)du, where recall that X; is the feasible decision set defined in $ 2. For OIKP, the algorithm will admit the item if 2 d(z) and there is sufficient remaining capacity wA < 1 2: for OFKP, the algorithm will continuously admit the item until one of the following occurs: (i) the utilization reaches  (v:): (ii) the entire item is admitted; or (iii) the knapsack capacity is used up. Notice the threshold function & is the only design space for Algorithm 4. (Sun et al., 202 lb) shows that the optimal competitive ratio can be attained when & is carefully designed as follows.
Lemma A.3 (Theorem 3.5 in (Sun et al., 2021b), Theorem 2.1 in (Zhou et al., 2008)). When the unit value of items is bounded within [L., U), Algorithm 4 (1 + In(U/I.))-copptttinn competiiivee for OFKP and OIKP (integral with small item weights)
15

---

Near-Optimal Consistency-Robusttien Trade-Offs for Learning-AAggeente Online Knapsack Problems
Algorithm 4 ZCL: An Online Threshold-Basee Algorithm for OKP Without Prediction
Input: threshold function (())
Output: online decisions [z.]ie|m]
Initialization: knapsack utilization (0) +0
for each item (with unit value U; and weight w;) do
P4 - {0, w or [0, wx] {feasible set: discrete for OIKP, continuous for OFKP
if' 0 ((-11) then
24
else
Zi f arg max 1....,, (i:0; - S200-11
+2, ((u) du)
Update 20)) t 2(--1) + xz
Algorithm 5 PP-a: A Basic 2- 2-Competitive Algorithm for OFKP with Trusted Prediction
Input: prediction
Output: online decisions {
for each item (with unit value u, and weight w;) do
if e < 0 (item is rejected}
then
else if v; > 0 then
2; f w4 {item is partially accepted}
2
else if 1/2
then
temp < min(w;, 1-11-- ()
@ e temp
temp {item is partially accepted)
when the threshold is given by
2 10, T+m(UtyT))
o(z) = (eex ((1 + In(U/L))= EE [+
77)
Further, no online algorithm can achieve competitive ratio smaller than 1 + In(U/L)
A.5. Deferred Pseudocode for 3 (Trusted Predictions)
PP-n: A naive trusted- preedccirreiition algorithm: We consider naive "greedy" algorithm that takes prediction on input. The first algorithm rejects any items with unit value and fully accepts any item with unit value until the capacity limit. In Theorem A.4, we show that Pp-n fails to achieve a meaningful improvement in the worst-case competitive ratio (i.c., consistency since we assume the prediction is correct). We prove the following result in $ A.6.4. The second way of defining is to reject items with value < and accept items with value > 0. This algorithm is not competitive too since there could be no item with greater value than è which means you won't It accept anything.
Theorem A.4. PP-n that fully trusts the prediction is U/L-ommpeiitive in the worst case.
It is worth mentioning that this algorithm's 's experimental results show the benefits of using critical value prediction even without improvements, seen in Figure A6. However, it falls short of providing meaningful theoretical results in special cases.
Pseudocode for PP-a. Here we give the pseudocode for the PP-a algorithm (Algorithm 5) discussed in 3.2 and Theorem 3.2.
16

---

Near-Optimal Consistency- Trade-Offs for Learning-Augmentte Online Knapsack Problems
A.6. Proofs
A.6.1. PROOF OF THEBREM 3.1
Proof. Consider the following two input instances, each with critical value e 1 and total weight w on the critical value:
I : n = 1, (V1, wi) = (1,4); I : n 2,
(1i, w1) = (1,4), (V2, w2) (U, c).
where U + +o0 and + 0. The offline optimal solutions for the two instances are OPT(Zi) = min(1, and (Z2 = (1 cjU + e, respectively.
Since both instances have the same critical value and thus are given the same prediction, and since they have the same first item, any online algorithm will make the same decision for the first item regardless of which instance presented. Let
X E 00, min denote the decision for the first item from randomized algorithm, where X is random variable with probability density function f(r). The expected returns of the randomized algorithm over the two instances can be derived
as
min
B[ALG(Z])]
f(x))dxx [
B[ALG(I2)] <
+ (1-l=+(1=)Ud==== E[X] (1 E[X]]U
where [[]] E [0, (i, As U +00 and 6 - the competitive ratio of the algorithm thus
(Z)
(IT
min ( (
max
2 maax
2 1 + min
E[ALG(I,) ]
E [ALG
E[X]
- E[X
where the final bound follows by observing that the competitive ratio is minimized when min(1.62
T- which occurs
X[
when [[X]= completes the proof.
1+min(1,00 Thus, the competitive ratio of any online randomized algorithm is at least + min(1,4). This
min(1.2)
A.6.2. PROOF OF THEOREM 3.6
Proof. Based on the matching lower bound from the ZCL paper (Zhou et al., 2008), for any (possibly randomized) algorithm with known lower and upper bounds and on value densities, there exists an input sequence, denoted by I, such that the expected total value of the algorithm is at most i=In(=/e]+ where = OP is the offline optimal value under the instance I. Note that in this instance, the last item is with the maximum value density within [e, u] and with weight 1.
Let J denote new instance by appending one item with value U and weight 1 - s (where E > 0 and = + 0) to the instance I. Note that the instance J has the same prediction interval as the instance I. The offline optimal value (PT(J) 2 (1 s)U + U. For an online algorithm A given an interval prediction [e, u). let M E [o, 1] denote total amount of admitted items under the instance I and let fm) denote the probability distribution of the random variable M. The total value obtained by the online algorithm can be caleulated as follows.
B[A(Z)) < S. 5(m)m- (T (+
dm,
Z m.
= =[M]] I+ 1n(/e/))
B[A(T)) & (/¹ f(m)
1+ ++In(v/e) + (1 - -mmju dm.
7
= -
+ + +1-E EE
1+ In((e))))
17

---

Near-Optimal Consisteney-Robusttee Trade-Offs for Learning-Augmentte Online Knapsack Problems
where [[M] [0, 1j. As U - xc; the competitive ratio of the algorithm is lower bounded by
OPT(Z) OPT(J) B[A(Z)] B[A(T))
max
max
2 2 In(u/)).
R[M]
E M
I+In(a/E)
A.6.3. PROOF OF THEOREM 4.2
We divide the proof into the proofs of the following two lemmas, provide the detailed proof of the asymptotic lower bound in Lemma A. and postpone the proof of the lower bound in Lemma A.5 to $ A.6.8.
Lemma A.5. Given untrusted prediction of the critical value, any deterministic ry-robust for OKP (where Y E [ln(U/L) 1,) is at least n-consistent, where is defined in (2).
algorithm
Lemma A.6. In an asymptotic regime for OKP where U/L + any deterministic algorithm given untrusted prediction of the critical value that is 20-consistent (x E (1)) is at least Ω 1+11((/))
-robust.
Proof of Lemma A.6. Suppose an algorithm for OKP is (3-consistent and a-robust, where 3 = 2x (noting that 2-consistency a firm lower bound by Lemma A.5). Consider the following instance:
The first batch items to arrive have value L. There are 1/c of these, each with weight e.
The second batch items has value AL, where
1. There are 1/+ - many of these items, each with weight c.
The third batch of items has value BL, where B > A > 1. There are many of these items, and each has weight epsilon.
First, we consider consistency on the first two batches of items, letting 0 = L. Note that OPT + AL as - 0. and observe that ALG must satisfy the following:
1
(
1
ALG(first two batches)
L
AL.
2x
2x
2Az
follows that ALG must use (1 ) of its knapsack capacity during these first two batches items in order to stay 2r-consistent. Also note when AL >> L, ZAz + 1/a.
Next, we consider robustness on all three batches of items. As previously, ALG uses (1 - - of its knapsack capacity during the first two batches of items, leaving (1 + 2 capacity remaining for robustness. We will assume that BL S AL, implying that the optimal strategy is to run an existing optimal OKP algorithm (i.c., ZCL) with the remaining capacity. Let ln(U/BL) + 1 be the competitive ratio of this "inner" 2CL algorithm, and note that the algorithm must accept (within the available capacity) a ++1((//n1) fraction of the items with value BL. This gives us the following for ALG on all three batches:
L+ (
AL (1
1- x. 2Ax In(U/BI) (
1
BL
BL)BB)
ALG(all three batches)
2x
2x
2Az
18

---

Near-Optimal Seniiitene--Roussteee Trade-Offs for Learning-Augmeente Online Knapsack Problems
Note that OPT BL on the sequence that includes the third batch. Then have the following for the robustness ratio B:
BL
8
1 L
AL + (1 + 2dz)
BL [TIn(U/BL))
2x
2x
2hm
1 + In(%/L)
1 1/2
1) 111 2Br 2x 2d2)
((00(1)))) 1410(0pmL)
A(In("/L)+ + + 20 Ihm
1+In(UBBL)
1 1 1m(1//
1- 1/2
2Bx - 2B
A(In(1/4)+ + 1) (2Bx 2B + =)-
In(U/D)+1
[+I(U/BL)
Let be constant (i.e., independent of A and B), let FAA,
=
A(n2"//++))(3aa--200 2 2) lu 1001
2Br-2B
(BL)
and consider the limit as + cc. - oc, B/A + xc, and U/L + 2.. Noting that ln(D/BL) R In(U/z) as + oc, we have that (A, B,,, L. + (11 under the above conditions. Thus, we have the following, completing the lemma:
8 1+ (nULLL
1 1+//0 = -Q (1 1 (++n(U/LL)
o(1) +
1-
1 1-X
1/1/
where À = 1/2 E 1).
The statement of Theorem 4.2 follows by combining the results of Lemma A.5 and Lemma A.6.
A.6.4. PROOF OF THEOREM A.4
Proof. Denote the prediction received by the algorithm as è, for any valid OFKP instance
Consider the following special instance in Ω
I: n == 2, (0i, w1) = (L, (V2, w22 = (U, c).
(10a)
where U + +oo and + 0. Note that the offline optimal return of this instance is OPT = U (1 L(e), and 0 L.
Observe that the naive algorithm will receive the exact value of 0 and greedily accept any items with unit value at or above 0. Then the first item with (V1, w1) = (I, 1) will fill the online algorithm's knapsack, and the competitive ratio can be derived as
OPT(Z) ATG(T)
UlI-e)+Le - - + L(E)
L
As + O, the right-hand side implies that the competitive ratio is bounded by U/L. Since an accurate prediction has 0 E [L by definition, this special instance also gives the worst-case competitive ratio over all instances.
A.6.5. PROOF OF THEOREM 3.2
Proof. Before starting the proof, we define new notation for the optimal offline solution, Let's assume that there are q 1 items with strictly greater values v/ and items y to p p-11 are items with unit value é (g can equal p p- 1, implying there zero such items). We can rewrite (5) as follows:
p-1
OPT(I) Σ
Σ
w/6
+
(1-
1
Σ
w/
(11)
i=q
19

---

Near-Optimal Seaiiseency-Rbuuttesee Trade-Offs for Learning-AAgmentee Online Knapsack Problems
using the above notation define är
(12)
where r is largest number which ey = ê and is greater or equal to p. Recall that 0 ;= v/-.
With this notation place, we can proceed with the proof.
As described in Algorithm 5, each item i with value less than the prediction is ignored. If the value is greater than the prediction, half of its weight is selected. If the prediction is equal to the value, will select half of it and ensure that the sum of all selections with a value equal to the prediction doesn't 't exceed 1/2. We first show that Algorithm 5 outputs feasible solution, i.e., that Σ 3t I 1. We derive the following equation:
JS
Σ
Σ BCN
(13)
t=1
The first sum is equal to zero, since the algorithm doesn't it select any items with U, < 0. The second sum considers ez and the algorithm selects half of every weight wt unless @ is greater than 1/2. The algorithm ensures it doesn't 't select more than 1 1/2 by definition in line 9, which checks whether to take half of an item and not exceed the remaining amount from 1/2. For of 2 v/g. Algorithm 5 sets to w
Σ
0 min
W 1 2' ( +
Wi 2
(14)
The last sum is 1/2 times the of the sum w,s for any items with a value greater than é. If we look at (11), all these wi; are completely selected in the optimal offline solution (in the first part of the equation). Thus, their sum less than or equal 1, since the optimal solution is feasible: Eeeo. Wy E w
Σ
Σ BCV.
wi
+ =1
(15)
2
2
2
2
Equation 15 proves that the solution from Algorithm 5 is feasible. We next calculate the profit obtained by Algorithm 5 and bound its competitive ratio. The profit can be calculated using (1) as:
ALG(Z) min
a -+
2'
Σ MAC
Wi
2
1//
(16)
Looking at (11), we claim that the second part of (16) is 1 Σ w/u4.
To calculate the competitive ratio, we give a bound on OP OPT ALG((I I) by substituting (11) and (16) into the definition of CR (i.e. OPT/ALG), obtaining the following:
Σ
wat
Σイ w (1- EE- w!)
CR
max ZEN
(17)
2- 1=
2 + min ( (7 -
Σ wiy
EE w + (1- Ei'l w3) i
CR max
2
(18)
Tes
E w/y + min (w: 1) -
Here we prove that the numerator is less than or equal to the denominator, which will give us (19).
Σ w + Σ w/o + (1 (1- 11 E'
CR max
2
2.
(19)
Σ 2 - why! + min (w), 1) -
20

---

Near-Optimal Consistency-Robusttee Trade-Offs for Learning-Augmenter Online Knapsack Problems
We argue two cases: first, if < 1, then Algorithm 5 will always select half of every item with value ö. Then, by rewriting the value of a we have:
1 Σ dht, + min (0, 1).0
9-1
q 8
1
Σ
wouy
+
+ w 0 wfo
Σ
(20)
==1
x=p+1
Using the fact that the definition of up in (4) and LP constraint (I), we claim 1 1 EE= w o S Wp. Thus, (20) is greater than the numerator in (19).
In the second case, if à 2 1, then the algorithm will stop selecting items with a value of after it reaches a capacity of 1/2 for those items. The optimal offline solution is feasible, so Ei=l u +1 +1- wf) S 1, which implies that the (E
following is also true: Di=g w/ +1
w!) I 1. Using this, we can rewrite the numerator:
p-1
p-1
Σ w + 1
W
i
(21)
Which subsequently implies that the numerator is less than or equal to the denominator.
Both cases have been proven, completing the proof of (19) PP-a a is 2-competitive.
A. PROOF OF THEOREM 3.3
Let I : {(w,, U/) Heg(n) denote an instance for OFKP, where the value density e 2 é, Vi E [n]. It is without loss of generality to focus on I since both offline algorithm and PP-a ignore items with value density smaller than ô. To distinguish the items with critical value density è and those with value density greater than é. Define NV. {i [t] : uy 6} and N₁ = (j E [i] 0y 0 as the sets of items (up to the i-th item) whose value densities are equal to and greater than é, respectively. Then the offline optimal value under instance I can be shown as
OPT(I)= E U,00; 0(1
ΣxENa w:)-
(22)
where the first part total value of items with value densities greater than è and the second part is the value of items with density 0, filling the remaining knapsack capacity.
Let v; denote the online admission solution of item i. We first show that the online solution by PP-a is feasible.
Lemma A.7. The online solution of PP-a is feasible for OFKP.
Proof of Lemma A.7. We use = Σjen Ij to denote the cumulative amount of admitted items by PP-a, up to item i. The goal is to prove 8n < 1. We claim that the cumulative amount of admitted items by PP-a is
Wi +
W Vi We
8,
[m]]
(23)
where Wi = min jENs Wy.1) denotes the cumulative amount of item weights with critical value density 0, upper bounded by 1, and W; = Ej Wy denotes the cumulative amount of item weights with critical value density greater than 6. Note that Wn, < 1 by definition of the critical value. Thus, if (23) holds, the online solution of PP-a is feasible since Sn W.. + < 1. 1+hh
In the following, we prove (23) by induction.
Base Case: i = 1. Initially, wn = 0 and = 0. If item 1 is not with critical value, i.c., 1 E No, then by PP-a, we have @1 = رy = 0 and $1 = 21 = wi = W1, which satisfies (23). If item 1 is with critical value, i.c., 1 E N/. then Wi = Wi, 2 which satisfies (23).
#1 =0, 0. and 81 = .1 14
Induction Step: i 2 Suppose $
6; 1+0; 1, we next show that s; 146
0. 14
Consider the following two cases.
21

---

Near-Optimal -oabusteney-Robustneess Trade-Offs for Learning-Augmenter Online Knapsack Problems
Case (i): If item i Ng have Wi W and x2 1+04-1
by PP-a. This gives
Wi + W4-1
Wi-1
( + W5
8 8 22
(24)
+ W1-1
1 1+
Case (ii): If item i E Ng. then we have W; W5-1 and W5 min( + wi, 1}. In addition, min min(w:. (w.. I l-; 1), Then we have
min (ar -
1+2;
8(-1"
140
8;-1 + 24
wi-1 1 + Wi min main(w;; Wi. 1 - Wi-13
Wi-1 + Wi min
(.. min(w;;
Wi-1 13
1 + Wi-1
+ wi
1 + W;
1 + 4i
min ( 1 - wi-1 }
+ Wi-1 + W/
1 + Wi min (W, 1 w
+ Wi
1 Wi-1
+ W3
min(ut; 1 - w
Wi 1 + Wi-1
+
1 Wis
1 + W
@4 + +W
1 Wi
where the last equality holds because from PP-a a we have
+ Wi min(w,, 1 w1-13 + 01-1.
(25)
This completes the proof.
Next, we prove that PP-a achieves at least 1/(1 + Wn) of the offline optimal value OPT(I), where a, min 13 by definition.
Lemma A.8. The total value of admitted items by PP-a is lower bounded
ALG(I)= 2 wnO Σiena W;2s
+
(26)
1 6n
1 + wn
Based on (22) and (26), we can show PP-a is (1 (.,) comppetiie, i.c..
EiENe Us00 + (1- --EiN 14
(ZT(Z) ALG
< (1 + wx)
Eiene Wabt + w
< + wn.
(27)
where the last inequality holds since Wn, 2 1 ΣieNg we by definition of the critical value density. We complete the proof of Theorem 3.3 by proving Lemma A.8.
Proof of Lemma A.8. Let (Z) denote the total value PP-a after processing the i-th item. We show the lower bound of the online algorithm by showing the following inequality holds.
ΣjENS Wyyy
A
2
Vi E [n].
(28)
1 W5
W
Base Case: i = 1. If item 1 E No, then W1 = Wo = 0 and w1, and thus ALG, (I) = U which satisfies (28). If
@1 item Nr. then W1 W1 and æ1 = 1+#1
Then we have ALG, (I) = وz = 1+40
which satisfies (28).
Induction Step: Suppose (28) holds for we aim to show the inequality for
22

---

Near-Optimal Mumsistency-Robustnnee Trade-Offs for Learning-AAgmentee Online Knapsack Problems
Case (0): If item Ny, have wi W;-1 and I2- I+0,
ALG,(Z) ALG,-1(I)) D
Σjere, Wyyy
6,ū
w4y% 1 1 Ws
+
1 w
+ Wi
6,ú
E EJENY W
+
1 Wi
1 Wi
Case (ii): If item i E N2, we have d; min + wy, 1}, then
(Z), = ALGG-1 + i2
Σ Ejexp, Wjty
@1-10
$min (0,, (i-1) 81-1
min(ws ac
W1-1
1 Wi-1
1
+ wi
1 1 wi min x.-13 ΣSENz 2syy
w1-10
0
minf W/ w.-1
min w., 2
4
1 1111
1 We
Wi-1
1 W
+ W
ΣjENp Wytty
11-10
mmn (1; 2i-1)
1 05
1 W;
1 1 0,
ΣjExo Wyd5
1+ W
+ W.
where the first incquality obtained by using the induction hypothesis and substituting x, min MM 1
1+
min(mr,11 10 the second equality is obtained by substituting 83-1 1 from (23), and the last inequality 9:-1 1+5;
1
holds because Σjeve, WyDj 2 f6;-1 and 1 + ai min(w,, w = 41
A.6.7. PROOF OF THEOREM 3.4
Proof. First, analyze the feasibility of the solution we show that Σ J; I 1.
Σ
+
+
Σ
(29)
By substituting sub-algorithm selections, we have the following:
z
0+
Σ
Σ
(30)
a+11
Using the fact that the sub-alg aub-atgorithm is also feasible algorithm, say that:
Σ [
x
Σ x mE((aa)
1.
(31)
a+1
a a+1
a a
Also, from (4), we know that the optimal solution will select every w; with > é. since & E [e, u). We can say that w; for which U; >> u implies 0; > 0. Moreover, (5) is feasible result, we know that Σ Exee, wA I 1. So, we claim that:
Σ a=1
Wi
Wi
Σ wi S
1.
(32)
a
a +
Br
23

---

Near-Optimal Seaiilteney-Rbuutteess Trade-Offs for Learning-Augmenter Online Knapsack Problems
Substituting (32) and (31) into (30), obtain:
Σ 14420
C
Ii = +
+
S
=1.
(33)
++1
a+1
a+1
which completes the proof that the solutions are feasible.
We proceed prove that the algorithm achieves a competitive ratio of 1 (given sub-algorithm ZCL, which has competitive ratio a:.. The profit can be calculated based on æ; decisions, using (30);
ALG(I) =
Σ [FC
+
Σ 2e
W2 02
(34)
a
a
For the first sum, know that Algorithm ZCL guarantees a-competitivenesss, which show as follows:
Σ
x
x a 2 OPT(Z).
(35)
where Io is all items in I such that i E (e, u]. Also, we claim that:
w/ r/ + (1-
OPT(To)
Σ
Σ
w/
(36)
Where of represents the critical value for Zo. We argue that up S 6. we denote the pth item in the sorted list, as defined in (5), and ufo as the p'th item in the sorted list of the instance I, we assert that S p/. The rationale behind this assertion is rooted in the definitions. Specifically, p is defined the largest number for which E w/ 1. Now, let us assume & is the first item with value less than or equal to u. By definition, p' represents the largest number for which E w/ 1. we were to assume that p > p', this would contradict the definition of p' as the largest number, because changing p' p would yield sum less than one, but we increased from the p' another larger number. Consequently, not valid to claim that p p'; instead, conclude that p $ p/. This implies w/ è.
Using this observation, we can now compare OP and OP (Io):
OPT(I) Σ
1- Σ
1
un
0,
p-1
p-1
Σ
w/ok
w///+ +
1 Σ usb
B,
(37)
3/
p/-1
wiyk
+
wool +
Σ woys +
(1-Σ
w/
t=p
t=
iat + (Io(
where (37) holds because p = p', then we have i = ufo, implying that the last sum of OPT(Z) (which is (1- w!) 6).
equal to (Er'z w()
On the other hand, if p < p', the last part of OPT(I) can be bounded by w v/ which is subsumed within Σn'r1 w/rl. This follows from the fact that -P- wt < wh due to the definition feasible answer.
24

---

Near-Optimal Consistency-Robusttoss Trade-Offs for Learning-AAgmentee Online Knapsack Problems
Using (35) and (37), claim that:
Σ
x
Us
2
1
(OPT(I)
Σ wyvz).
(38)
a
Now, let combine this with other parts in (34):
ALG(T)=
Σ
a
x
+
Σ
wi Vi
[r,
a
OPT(I)
Σ witl )
+
Σ 0.20
(39)
a ++1
a c
1
OPT(
Thus, we conclude that IPA using ZCL as the robust sub-algorithm is a + competitive.
A.6.8. PROOF OF LEMMA A.5
To show this lower bound, we first construct a family of special instances and then show that the achievable consistency- robustness when given a prediction of the critical value is lower bounded under the constructed special instances. Assume that item weights are infinitesimally small. It is known that difficult instances for OKP occur when items arrive at the algorithm in non-decreasing order of value density (Zhou et al., 2008; Sun et al., 2021b). We now formalize such a family of instances (T=) where I is called an z-continuously non-decreasing instance.
Definition A.9. Let N,m E N be sufficiently large, and 5 = (U L)/N. For E [L, an instance In Q is r-continuously non-decreasing if it consists of N₂ == [( L) + batches of items and the i-th batch (i [Na]
contains m items with value density L + (i 1)5 and weight 1/m.
Note that L is simply a stream of m items, each with weight 1/m and value density L. See Fig. A1 for an illustration of an x-continuously non-decreasing instance.
w (1+68// 10 1/m
(1+68/
7/m
Batch O with y7 items
Batch with in items
Batch N. with in items
Figure AI. Ia consists of Na batches of items, arriving in increasing order of value density.
We will operate with types of æ--icreeaing instances follows. Let Iz I, defined in Def. A.6.8. Furthermore, let Iz denote sequence defined as Lz,U = Ia; {U (t/- - 1)}. In other words, append (1/- 1) items with value density U to the end of the sequence Iz. (this is the worst-case for consistency, observing that 0 = I))
Suppose a borriig--uugented algorithm ALG is 7-robust and -y-consistent. Let g(x) [L + [o, 1] denote an arbitrary acceptance function, which fully parameterizes the decisions made by ALG under the special instances. g(x) gives the final knapsack utilization (total weight of accepted items) under the instance Iz, Note that for small 6, processing I is equivalent first processing Iz, and then processing m identical items, each with weight 1 and value density x + 6. Since this function 9(-) is unidirectional (item acceptances are irrevocable) and deterministic. m must have g( 5) 9(x), i.e. g(x:) is non-decreasing in [L, U]. Once batch of items with maximum value density U arrives, the rest of the capacity should be used, i.c., g(U)= = 1. ALG is r-rouus.. Observe that in order to be "-competitive under the instance Iz. we must have that (L) Z +.
Furthermore, under the instance Iz, the online algorithm with acceptance function g obtains value of ALG((.) g(L)L+ + fT udg(u), where udg(u) is the value obtained by accepting items with value density and weight dy) Under the instance I,, the offline optimal solution obtains a total value of OPT(I,) = æ. Therefore, any y-robust online algorithm must satisfy:
ALG(I.) = ALG(Z.)=9(L))) =((() + '' udg(u))
Vr E [L.
25

---

Near-Optimal Consistency- Robbsssesss Trade-Offs for Learning-Augmenter Online Knapsack Problems
By integral by parts and Grönwall's Inequality (Theorem I, p. 356, in (Mitrinovic et al., 1991)), necessary condition for the competitive constraint above to hold is the following:
(
- + 1 [ g(u)du 1 1 In
I (T.)
(40)
Assume that a items with value densities strictly greater than have total weight less than 1. If the actual best value density U, ALG must satisfy ALG(Io, 2 (2I(Zo, Note that g(U) = by the structure of the problem. This gives
algorithm ALG receives prediction ë. If the prediction is correct, we know that the
u(U)U J g(u)du 2
U
(41)
7j
Furthermore, for ALG to be 17-consistent on an instance where é x, recall that Iz,, denotes an instance where prices continually increase up to æ, and g(z) denotes the fraction of knapsack capacity filled with items of value density S x. By the definition of consistency, it follows that g(x) must satisfy g(x) 2 " Combining the above condition with the robustness condition on g(z), an n--oonisttntt and 7-robust algorithm must have g(x) 2 m + In (1),, 1/n). Thus, we have the following:
max [1
1 dee, 7/
I [+ In
{ do S I glu)du SU- U 1)
(42)
where the last inequality is based on (41).
Then the optimal y is obtained when the inequality is binding, which gives:
1 U
//
|
In
F
U dr
U
7 11
L
L dx U
1 In
U
1 17
11
1 -
U L U
U
7
1 In
4
S 7
L
2
51
U
Combining the above two cases completes the lemma.
A.6.9. PROOF OF COROLLARY 3.5
Recall that ZCL is (In(V/L) + 1)-competitive. Letting U = u and L = l, we have that (a 1) = 22+ As l and approach each other, In(4/e) approaches 0 - in the case of = u, this recovers the 2-competitive result of PP-b (Algorithm 5).
A. 10. PROOF OF THEOREM 5.2
We first prove that given the algorithm Int feasible, it is y 1+88/1=((1o0(- */4]+1) competitive, and then prove its feasibility. Let A.Dj] and R,]s] denote the cumulative total value of items in range j (where j = 0, ...... [lg +44) U/4]) after processing item i. We claim the following inequality holds for all i = 0, ... and j 0, ... [lo l/r.]:
(8) 0/4] + 1)
A.D Z R.Di
(43)
1+8
We prove this inequality by induction. Initially, Aoli) = Roly] = O, and thus the (43) holds. Suppose (43) holds for i
1,
we show that it also holds for in the following two cases.
1-e([og 1a; 1/6]+1) where Rb R [5] + U,W, then we have
Case (i): if 1=1 2 RD..
1+8
A = A, 2 R E( (1g 0/4] + 1)
1 8
26

---

Near-Optimal Consistency-Robustiee Trade-Offs for Learning-Augmented Online Knapsack Problems
I-<([ookaia 1/4]+1)
Case (ii): if A < R
then
140
A, A;-105] + wa 2 A,-1 W,V,C,
1 E( (((oo 4/L] +1)
2 Rí R
+ Wy0ū0,
1
2 R1 1- e([log(1+0) (/10)+))/1111111 + 1
1+8
where the first inequality is using the induction hypothesis and the second inequality is because the factor 1-c(Dogaai: 1/4]+1) 148
S 1.
With (43), we further have
(((10811+)) 9/6] + +) OPT 1- 1-e((10((15)) 4/6 + + (44)
EA Z Rnll) (1)
2
1
1+0
where the last inequality holds since the fractional algorithm is 7-competitive and the offline optimum of the fractional problem is no smaller than that of the integral problem.
In the following, we prove that the online solution of Fr2Int is feasible. Define wi (A, and w [il) as the weight of all items in range of Fr2Int and ALG after processing the last item n, respectively. Based on the value partitioning in definition 5.1, the value density of items in range is lower bounded by L 5-11 + 8) and upper bounded by L (1 + 8)++1 Thus, have:
(A,A)) L (1 8)$ < A.Il),, and, R, S w R bl) L (1 55+t1
Let ij denote the last item admitted by Int in the range j. Then we have
A R2ybi] (1 - ((log(1+5) 1/r, + 11)
(1 + 5)
S wwR bil) L (1 61+11 (1- (1-e( e([og1140)) 4/z] 1))
(1+
Since A1,-1 2 -bi) L. (1+66) combining with above equation gives we( n((Ai--15)) & we( (o,Ri, (I) <([log(44)) 8/z| 1)).
(45)
Then we further have
w (A,bli))) S w(A,-- S w(R, (i) (1 - -ee(ee([ogggg <([oog(1+0) U/2 + 1)).
(46)
Summing the weights over all ranges gives
Σ ((Ar, Se. ([oo U/L] + +1)+ Σ (Ri bi) - (1-e((log)))) -((1o8(1+5) 1/2] 1)) < 1.
(47)
where the last inequality holds since E, w Ra, (i1) < 1. Thus, the solution of Fr2Int is feasible.
A.7. Additional Numerical Experiments
In this section, we discuss other sets of experiments and report additional experimental results of the proposed algorithms' performance.
A. OTHER EXPERIMENTAL RESULTS SETUP
We talked about part of the first set of experiments in We should add that an MIX instance is created with uniformly random prediction intervals, where each instance makes a correct prediction with a fixed probability of 8 and chooses
27

---

Near-Optimal Consistency-Robustie Trade-Offs for Learning-Augmentt Online Knapsack Problems
wrong prediction otherwise. For IPA, we used uniformly random interval around the correct critical value since it is trusted prediction.
The second set of experiments compares against the existing learning-augee augmented OKP algorithm that uses frequeney predictions (SENTINEL) (Im et al., 2021) using the synthetic data set from the original paper. This data set constructs a sequence of items with a small weight of 0.0001 and values between 1 to 100, where each value appears (on average) 100(1 + 6/2) times in sequence. It has a lower bound and an upper bound with a fixed ratio uP/low = (1 + d), where 8 also a parameter showing the amount of prediction error as used in (Im et al., 2021).
In the third set of experiments, use a historical data set of Bitcoin prices (Kottarathil, 2018) in 2017-2019 to evaluate algorithms under realistic data. Each instance is constructed by randomly sampling 10,000 prices from one month of the data, setting all item sizes equal to 0.001. We used the same notation of 8 from (Im et al., 2021) to show the the accuracy of this experiment.
Finally, in the fourth set of experiments we follow related work (Sun et al., 2022) and construct instances based on Google cluster traces (Reiss et al., 2012). This data set records information about compute jobs on a cluster, with many short jobs and few long jobs. To construct values based on these job durations, we first scale each duration by a random number between 1 and 250, followed by resource scale factor randomly chosen from the set f0.01, 0.03, 0.05). Each instance includes 10,000 items generated as above, each with size 0.001.
A.7.2. EXPERIMENT RESULTS
To convey the henefits of succinct predictions, Fig. A2 presents results on the synthetic data set and prediction method used in the original paper presenting the SENTINEL algorithm that uses frequency predictions. We compare PP-a, -a Fr2Int-PP- aa and ZCL against SENTINEL. As 5(error parameter introduced by (Im et al., 2021)) grows, the number of items increases, and the prediction becomes worse. Here, is worth mentioning that due to the way that they made their dataset, ō is also a parameter for range of values. which make ZCL to act worse as 5 grows because it grows "P/low = (1 + 5). For PP-a, we use the average of the upper and lower bounds in the frequency prediction to derive a single number indicating the average critical value i And we use this number as the prediction to PP-a. As shown in Fig. A2, a single prediction, in practice, outperforms complex predictions.
In Fig. A3, we use a real data set of Bitcoin prices for 2017-19. Each month consists of 10,000 prices. To derive frequency predictions for SENTINEL, we generate two random numbers, a and h, between and + 5_ Each upper bound set to x s, where is the true frequency of a given price, and the lower bounds are set e/b. As in the previous experiment, our critical value prediction is derived from this frequency prediction. While PP-a, Pw2Innt-P---- and SENTINEL all perform well, achieving competitive ratios close to 1, our algorithms outperform SENTINEL on average.
Fig. A4 plots a similar comparison for the same algorithms on the real data set of Google cluster traces. Frequency predictions for SENTINEL are generated using the same technique described above. In this experiment, we find that PP and F F Itt-PPa a significantly outperform SENTINEL - this is likely the case due to the underlying distribution of values (i.e.. duration) in the cluster traces, which make the frequencies (and hence the predictions) of values less robust to error.
It is worth mentioning that for evaluating MIX performance we presented probabilistic input that has the probability of 1 - 8 for the correctness of the prediction and the probability of ó for prediction being wrong. In Figure A5(a), we evaluate the performance of IPA for different interval prediction widths, given as percentage (higher is worse). As shown in Theorem 3.4, we find that tighter prediction intervals yield better empirical performance. Furthermore, all IPA algorithms outperform the baseline robust 2CL algorithm. In Figure A5(b), we evaluate the performance of MIX for untrusted predictions. We test regimes where 8 (probability of correct prediction) is 10%, 20%, and 50%; we fix X = 0.9, and the interval is 20% of [L, UJ. We find that the performance of MIX smoothly degrades, and even bad predictions result in algorithm that outperforms the robust. baseline ZCL. Finally, in Figure A5(c), we show similar result for MTX- we fix 8 = 50% and vary the trust parameter À E {0.3, 0.5, 0.9). showing that when predictions are sufficiently good, MIX performs better when the predictions are trusted more (i.e., increasing A).
In Figure A6(a), we evaluate the performance of MIX for different values of - 5. This plot is a CDF plot version of Figure A5(b), which illustrates how increasing the probability of correct predictions (corresponding to empirically more accurate learmed predictions), we consistently achieve a better competitive ratio, both on average and in the worst case.
28

---

Near-Optimal Consisteney-Robustnees Robustness Trade-Offs for Learning-Augmenter Online Knapsack Problems
LSC
PP-a
PP-a
PP FrZine PP-a SENTINEL
1.3
Fr2Int-PP-a
empirical competitive rabo
Rr2Int-PP-a SENTINEL
empirical competitive ratio
SENTINEL
empirical competitive
ZCL
1.3
LG4
6=0
6-0.5
6=1
6=1.5
6=2
6=0
6=0.5
6=1
6=1.5
6=2
6=0
6=0.5
6=1
6=1.5
6=2
Figure A2. Empirical competitive ratios of PP-a, Pr2int-PP-a, SENTINEL, and ZCL on synthetic data from original SEN-
Figure A3. Empirical competitive ratios of FP-a, E F 1nI--PP--a and SENTINEL in experiments on real Bitcoin data (Kot- tarathil, 2018).
Figure A4, Empirical competitive ratios РP-a, Fr 2 Int-Pp-a, and SENTINEL in experiments on Google-Trace data.
TINEL paper (Im et al., 2021).
e01 competive rebl
ZCL
ZCL
ZCL
IRAI15NI 1RA140%
emner cal Compattoone
emor emprcall Compateree
1-0 50%
=
(a)
(b)
(c)
Figure A5. Interval-reediction--oe algorithms with different interval sizes, probabilities 8, and trust parameters A: (a) Competitive ratios of three interval widths IPA against baseline 2CL; (b) Competitive ratio three probability values in MIX against baseline ZCL. À = 0.9 and interval 20%; and (c) Competitive ratio of three À values in MIX against ZCL. ō 50% and interval 20%.
In Figure A6(b), examine the trust parameter À with values 0.3, 0.5, 0.9 for MIX. This figure represents CDF plot of Figure A5(c) and shows that the algorithm increases its trust in predictions (i.e. by increasing λ), the average competitive ratio improves. However, the worst-case competitive ratio (represented in this plot by the tail of the CDF) will deteriorate faster when placing more trust in predictions.
Similarly, Figure A6(c) demonstrates that the width of the prediction interval (tested as 10%, 30%, and 50% of the "width" of the interval [L, UI) also has an slight effect on average and worst-case competitive ratio for MIX- namely, tighter prediction intervals yield better empirical performance, which aligns with our expectations.
In Figure A7, which is CDF plot of Figure A5(a), evaluate the empirical competitive ratio of IPA for various interval widths, represented as percentage (where higher values indicate worse performance). We test intervals that are 15%, 25%, and 40% as "wide" as [L, U). Intuitively, reducing the interval size results in better competitive ratio, because the bounds on the value of are tighter.
Figure A8 is a box plot version of Figure A5(c), illustrating that MIX's average-case performance is not significantly impacted by the width of the predicted interval, although tighter intervals are still intuitively better.
Finally, in Figure A13, vary the value of @ in four CDF plots, for each tested value. In contrast to PP-n, PP-b, and ZCL, these results show that the performance of PP- substantially improves with smaller values of W, confirming the results in Theorem 3.3, which establish that PP-a's 's competitive ratio depends on a. These figures correspond to the CDF plot of Figure 2(c). Another interesting observation is that as w decreases, PP-a's empirical performance worsens, but for high @ values, it improves. This occurs because PP-a is designed to target 2-competitiveness, but performs well when selecting more items in é than the optimal solution. This occurs when & is high.
29

---

Near-Optimal Sesasteency-bbustteeee Trade-Offs for Learning-Augmentte Online Knapsack Problems
1.0
1.0
1.0
0.8
0.8
empinical CDF
empirical CDF
empirical CDF
0.6
0.6
0.6
0.4
0.4
0.4
ZCL
ZCL
ZCL
MIX; (110%
(IX,(0.3)
(10%)
0.2
-
MIX,(0.5)
mf 30%)
-IX;-5(50%
MIX,(0.9)
(50%)
0.9 1.5 2.0 2.5 3.0 3.5 4.0 4.5 5.0
0.0.
1.0
1.5 2.0 2.5 3.0 3.5 4.0 4.5 5.0 empirical competitive ratio
0.9
1.5 2.0 2.5 3.0 3.5 4.0 4.5 5.0 empirical competitive ratio
empirical competitive ratio
(a) interval: 20%; A: 0.9.
(b) 1-8: 50%;
(c) 1-6: 50%; X: 0.9.
interval: 20%.
Figure A6. Performance of the mcta-algorithm (MIX) when provided with interval predictions, with varying parameters (probability of correct prediction (1 6), parameter and interval size) against the robust threshold-bee based algorithm (2CL).
1.0
ZCL
empirical competitive ratio
interval 10%
0.8
interval 30%
4.-
empirical CDF
interval 50%
0.4
ZCL
2.5
(PA(15%)
0.2
IPA(25%)
IPA(40%)
0.0
1.5 2.0 2.5
4.0 4.5 5.0
1.0
empirical competitive ratio
MIX
Figure A7. The performance of interval- www.raa-peeiiiio--baaee based al- gorithm (1 (A)A) with three intervals against online threshold- based algorithm (ZCL).
Figure A8. Performance of meta-algorithm when pro- vided with interval predictions versus threshold-base algo- rithm (ZCL). 8 50%, 0.9
30

---

Near-Optimal Consistency- Robusstess Trade-Offs for Learning-Augmentee Online Knapsack Problems
1.0
1.0
0.8
0.8
empirical CDF
empirical CDF
0.6
0.6
ZCL
ZCL
0.4
PP-n
PP-n
PP-b
PP-b
PP-a
PP-a
0.0
1.0
1.5
2.5 3.0 4.0 4.5 5.0
0..00
1.5
2.5 3.0
4.0
4.5
empirical competitive ratio
empirical competitive ratio
Figure A9. 0.29.
Figure A10.
0.44
1.0
1.0
0.8
0.8
empirical CDF
empirical CDF
0.6
ZCL
ZCL
PP-n
PP-n
PP-b
PP-b
0.2
PP-a
PP-a
0.0
1.0
1.5
4.0 4.5
0.0
1.0
1.5
2.5 3.0
4.5 5.0
empirical competitive ratio
empirical competitive ratio
Figure A11. & 0.63.
Figure A12,
3 0.78.
Figure A13. Performance comparison of naive greedy algorithm (PP-n), basic 2-competitive algorithm (?P-b), and improved + min(1. ( (1111)-ccompp c--mpptttiiivee algorithm (PP-a) against threshold-based algorithm (XC1.) with varying a.
31


Reviews:
[{"review_id": "id7xVYthgT", "reviewer": "Reviewer_6Cmk", "summary": "The paper considers the OKP problem based on succinct predictions and design learning-augmented algorithm to achieve a good trade-off between robustness and consistency. The succinct prediction model provides either a single-valued prediction or an interval prediction. The paper first consider trusted predictions and design competitive algorithms for both point prediction and interval-prediction, respectively. Next, the paper considers untrusted predictions and prove the robustness-consistency tradeoff for the algorithm MIX which linearly combines the prediction based solution and the robust algorithm ZCL. Further, the paper extends the algorithm from the fractional setting to the integral setting. The authors present a case study on both synthetic and real datasets.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review and for highlighting the key question about the robustness of MIX when predictions may be arbitrarily incorrect.\n\n**On the robustness guarantee of MIX despite poor predictions:** The MIX algorithm handles untrusted predictions by combining the decisions of a robust baseline (ZCL) and a prediction-based algorithm using a parameter $\\lambda \\in (0,1)$. Since this is a maximization problem, the competitive ratio is defined as $\\text{OPT} / \\text{ALG}$. Even if the prediction-based algorithm performs poorly (e.g., contributes zero profit), the robust algorithm still guarantees a fraction of OPT.\nTo make this concrete, consider a simple example: suppose the algorithm allocates half the capacity to the robust algorithm and half to the prediction-based one. If the prediction is arbitrarily wrong and the prediction-based component gets zero value, then the robust half still contributes half of its guaranteed performance. The total gain is then:\n$\\text{ALG} = \\frac{1}{2} \\cdot \\text{ALG}{\\text{pred}} + \\frac{1}{2} \\cdot \\text{ALG}{\\text{robust}} = 0 + \\frac{1}{2} \\cdot \\frac{\\text{OPT}}{C} = \\frac{\\text{OPT}}{2C}$\n\nwhere C is the worst case competitive ratio achieved by $ALG_{robust}$. Thus, the competitive ratio of ALG is: $\\frac{\\text{OPT}}{\\text{ALG}} = \\frac{\\text{OPT}}{\\text{OPT}/(2C)} = 2C$.\n\nSince ZCL is $C = \\ln(U/L) + 1$-competitive, the MIX algorithm remains $2 \\cdot (\\ln(U/L) + 1)$-competitive in this extreme case. This reasoning critically relies on the fact that we are solving a maximization problem, where getting zero gain from the learning-augmented part of the algorithm still results in a bounded ratio. In contrast, in minimization settings, such an approach could lead to an unbounded competitive ratio if one component incurs a large cost. We will clarify this in the final version.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "The paper considers competitive ratios under trusted or untrusted predictions.  This evaluation criteria is common for OKP problems. The empirical competitive ratios are evaluated in numerical experiments, which also makes sense.", "theoretical_claims": "I didn't check the detailed proofs of theoretical claims.", "experimental_designs_or_analyses": "The experimental designs look sound.", "relation_to_broader_scientific_literature": "The contributions of this paper are closely related to broader literature of learning-augmented algorithms for online problems.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "The paper consider the succinct predictions which are different from previous prediction information model.  The optimality of the robustness-consistency tradeoff is justified by proving the lower bounds.  The algorithm is also extended to the OIKP setting and the competitive ratio bound shows the effect of the rounding error $\\delta$.\n\nThe weakness is that the learning-augmented design MIX is a simple linear combination of the prediction-based and prediction-free results, so there is no novelty from the  learning-augmented algorithm design.\nMy concern is about the robustness of MIX. Given any possible prediction, the performance of prediction-based algorithm $\\hat{x}$ can be arbitrarily bad. In such case, how can we get a finite competitive ratio given a non-zero $\\lambda$?", "other_comments_or_suggestions": "N/A", "questions_for_authors": "My concern is about the robustness of MIX. Given any possible prediction, the performance of prediction-based algorithm $\\hat{x}$ can be arbitrarily bad. In such case, how can we get a finite competitive ratio given a non-zero $\\lambda$? Please let me know if I miss something.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5lLsVGeDMh", "reviewer": "Reviewer_jFAU", "summary": "The paper considers the online knapsack problem with predictions. In this problem, we are given a knapsack and a set of items that arrive sequentially. When each item arrives, its value and weight are revealed, and we must decide immediately and irreversibly whether to place the item in the knapsack. The goal is to maximize the total value of the selected items while ensuring that the knapsack's capacity constraint is not exceeded.\n\nThe authors propose two prediction models: in the first model, the algorithm has access to the predicted minimum item value in the offline OPT; in the second model, the algorithm has access to an interval in which the minimum item value in the offline OPT falls. The paper designs algorithms for both of them. Specifically, the authors first assume that the predictions are accurate and design semi-online algorithms for each model. They then use a simple random combination between the proposed semi-online algorithms and a classic robust algorithm to maintain robustness and consistency. The superiority of the proposed algorithms is demonstrated through theoretical lower-bound proofs and empirical performance evaluations.\n\n## update after rebuttal\nI appreciate the authors' rebuttal and will keep my original score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed and thoughtful review. You have raised some great points which will help clarify the paper.\n\n**On Theorem 4.2 and randomized algorithms:** Thank you for the careful reading – you are correct that Theorem 4.2 is currently proven only for deterministic algorithms. We will revise the paper to make this explicit in both the theorem statement and the surrounding discussion.\n\nWe strongly suspect that the theorem can be extended to randomized algorithms with some small modifications, and we will attempt to do so for the camera-ready. As evidence for this, note that the ZCL algorithm [4], which achieves the optimal worst-case competitive ratio for both fractional and integral OKP under a bounded value range, is itself deterministic, and cannot be improved on by any randomized algorithm. \n\nTo extend Theorem 4.2 to randomized algorithms, a first step is to modify the existing proof of Lemma A.5. Specifically, we can replace the deterministic utilization function with its expectation under a randomized algorithm—an approach aligned with the proof structure in Lemma A.6, which already reasons about expected capacity usage.\n\nThanks again for raising this point—we believe addressing it will significantly strengthen the clarity and completeness of the paper. Some of our lower bounds do hold under both randomized and deterministic algorithms (e.g., Theorem 3.1). We will make this explicit in their statements. \n\n**On the reviewer’s suggested randomized algorithm to avoid the small weights assumption:** We appreciate the suggestion of a simple randomized strategy that mixes between accepting all items with unit value ≥ v^\\hat{v} and accepting only items with unit value equal to v^\\hat{v}. This algorithm does indeed achieve a 2-competitive ratio in the oblivious adversary model, and does not require a bounded weight assumption.\n\nHowever, under an adaptive adversary, meaning that an adversary can change the input sequence “on the fly” based on the algorithm’s past decisions, this approach can fail. E.g., the first item presented can have unit value \\hat{v} and weight 1. If the algorithm does not accept it, the adversary halts the input sequence. If the algorithm does accept it, the adversary may follow with a very high-value item with weight slightly less than 1, which cannot be packed due to limited capacity. \n\nFor this reason, the mentioned randomized algorithm does not contradict our lower bounds, which hold for an adaptive adversary. The adaptive adversary model is the standard model in the online algorithms literature [1,2]. However, we agree that we should add text throughout that explicitly mentions which adversarial model we are working under. We will also qualify the statement about small item weights being required by saying that this is for an adaptive adversary model only, and will note the simple randomized baseline for oblivious adversaries given by the reviewer.  Thanks again for pointing this out. \n\n**On using Yao’s Minmax for Theorem 3.1:** Thanks for the suggestion – we agree we should be able to do this and clean up the proof a bit. \n\n**On terminology \"value\" versus \"unit value\":** Thank you for pointing this out. We use “value” to refer to the unit value (i.e., value-to-weight ratio). This convention is common in the online knapsack literature. For example, it is used in prior work by [3, 5] and other papers on learning-augmented knapsack. Nonetheless, we will revise the paper to clarify our terminology up front and make our usage more precise.\n\n[1] Adam Lechowicz, Nicolas Christianson, Bo Sun, Noman Bashir, Mohammad Hajiesmaili, Adam Wierman, and Prashant Shenoy. 2025. Learning-Augmented Competitive Algorithms for Spatiotemporal Online Allocation with Deadline Constraints. Proc. ACM Meas. Anal. Comput. Syst. 9, 1, Article 8 (March 2025), 49 pages.\n\n[2] Cygan, Marek & Jeż, Łukasz. (2014). Online Knapsack Revisited. Theory of Computing Systems. 58. 10.1007/978-3-319-08001-7_13. \n\n[3] S. Im, R. Kumar, M. Montazer Qaem, and M. Purohit. Online Knapsack with Frequency Predictions. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, pages 2733–2743, 2021.\n\n[4] Y. Zhou, X. Lin, and H. Zhao. Online budgeted truthful matching: A randomized primal-dual approach. Theoretical Computer Science, 2008.\n\n[5] Bo Sun, Lin Yang, Mohammad Hajiesmaili, Adam Wierman, John C. S. Lui, Don Towsley, and Danny H.K. Tsang. 2022. The Online Knapsack Problem with Departures. Proc. ACM Meas. Anal. Comput. Syst. 6, 3, Article 57 (December 2022), 32 pages.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "The proposed method makes sense, and the paper provides both theoretical and empirical evaluations.", "theoretical_claims": "I checked most of the proofs. One issue I found is that in Theorem 4.2, the lower bound is only proven for deterministic algorithms, rather than for any algorithm as claimed in the theorem.", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "The paper makes contributions to the field of online problems. However, although the authors claim that their goal is to design learning-augmented algorithms, I am inclined to view their work as primarily focused on semi-online algorithm design. The learning-augmented results are achieved via a straightforward random combination, without incorporating many advanced techniques.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "The paper's writing could be improved. The first two sections feel somewhat disorganized, as they frequently switch between introducing the authors' work and discussing related literature. Moreover, the paper refers to an item's cost-effectiveness as its \"value\" rather than using \"value\" to denote the item's actual worth, which seems weird to me.", "other_comments_or_suggestions": "- It might be better to use Yao's minimax principle to prove Theorem 3.1, as it would make the proof look cleaner.\n\n- The paper repeatedly claims that without either of the two assumptions, no algorithm can achieve a meaningful competitive ratio. However, this is not necessarily true. A simple randomized algorithm (e.g., accepting items larger than $\\hat{v}$ with half probability and accepting only \\(\\hat{v}\\) with half probability can achieve an expected competitive ratio of 2.", "questions_for_authors": "See the weakness mentioned above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WoyyH6hFn8", "reviewer": "Reviewer_qrRA", "summary": "This paper studies the online (integral/fractional) knapsack problem under the learning-augmented framework. The prediction is either a single value revealing the smallest unit value of items included by the optimal offline solution or an interval containing this value. When the prediction is trusted and items are fractional, the paper gives an algorithm with the optimal competitive ratio for both the value prediction and the interval prediction. When the prediction is untrusted and items are fractional, the paper gives algorithms that are both consistent and robust by combining a trusted algorithm and a robust algorithm, and it shows that the consistency-robustness trade-off of its algorithm is optimal. Moreover, the paper gives an algorithm to convert an algorithm for fractional items to an algorithm for integral items with almost the same guarantees, under the assumption that the weight of each item is small enough. Finally, the paper conducts experiments to validate the empirical performance of its algorithms.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful and positive review.\nWe especially appreciate your recognition of the simplicity and practicality of our prediction models, as well as the value of extending results to the integral setting. We will continue to refine the writing and presentation to further improve clarity, especially in the introduction and technical sections.", "claims_and_evidence": "The claims in this paper are all supported by rigorous and clear proofs.", "methods_and_evaluation_criteria": "The proposed methods make sense.", "theoretical_claims": "The proofs are correct to the extent that I have checked.", "experimental_designs_or_analyses": "The experiments are sound and valid.", "relation_to_broader_scientific_literature": "The paper is broadly related to the literature on learning-augmented algorithms and the online knapsack problems.", "essential_references_not_discussed": "To the best of my knowledge, there is no essential references missing.", "other_strengths_and_weaknesses": "This paper studies an important and interesting problem closely related to the ICML community. It is also well-written, and I enjoy reading it. This paper gives fairly comprehensive results regarding the online knapsack problem under the critical-value (or interval) prediction, and the proofs are non-trivial. In particular, the prediction form considered by this paper is arguably much simplier than the predictions in prior work for the same problem, and all the technical assumptions made in the paper are reasonable and well-justified. Overall, I believe this paper clearly exceeds the bar for acceptance.", "other_comments_or_suggestions": "I don't have further comments.", "questions_for_authors": "I don't have further questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0BUwluC6tN", "reviewer": "Reviewer_jEdr", "summary": "This paper introduces learning-augmented algorithms for the online knapsack problem (OKP) that balance consistency (performance with accurate predictions) and robustness (worst-case guarantees). The authors propose algorithms leveraging succinct predictions (point or interval estimates of the critical value in the optimal solution) and provide theoretical guarantees, including matching lower bounds. They also present a fractional-to-integral conversion method and empirical validation on synthetic and real-world datasets. This leads to all proposed algorithms for OFKP work for OIKP.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive review and your constructive feedback.\n\n\n**On the small item weight assumption:** We agree that this is a standard and important assumption in the integral setting. Our lower bounds (e.g., Theorem A.1) show that it is necessary for meaningful guarantees in our setting. But we agree that exploring other settings, or making additional assumptions that allow the small weight assumption to be relaxed, would be interesting.\n\n\n**On clarifying the intuition behind “prebuying” in PP-a:** Thank you for this suggestion. We will improve the explanation of PP-a’s dynamic reservation strategy in the main text and use a small running example to provide better intuition for the “prebuying” mechanism.", "claims_and_evidence": "The claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods make sense for the problem.", "theoretical_claims": "I checked the correctness of some claims but didn't go through all the proofs. The proofs that I have checked are reasonable and sound.", "experimental_designs_or_analyses": "I only made a quick pass on experimental designs, and it looks reasonable. Note that the main contribution of this paper is theoretical.", "relation_to_broader_scientific_literature": "The key contribution of this paper is inspired by the previous learning-augmented online knapsack and classical knapsack algorithms. But, this paper still provides sufficient technical contribution.", "essential_references_not_discussed": "All necessary related works are discussed in the submission.", "other_strengths_and_weaknesses": "Strengths\n\n1.  The paper provides rigorous analyses, including near-optimal consistency-robustness trade-offs. The lower bounds (Theorems 3.1, 3.6, 4.2) tightly align with the algorithms’ guarantees, demonstrating the Pareto optimality. \n2. In my view, the technical contribution reaches the bar of ICML. PP-a’s dynamic reservation strategy and IPA’s interval handling are novel. The MIX algorithm combines trusted and robust baselines, achieving near-optimal trade-offs. I also appreciate the rounding algorithm, which might be useful for another learning-augmented algorithm.\n3. This work also includes the experiments. The synthetic and real-data experiments validate theoretical claims, showing robustness to prediction noise and outperforming baselines like ZCL and SENTINEL.\n\nWeakness:\n\n1. The proposed algorithm deeply relies on the assumption of small item weights. However, I understand that this is a standard assumption in the literature. However, it is still interesting to see algorithms without this assumption.\n2. The presentation can be further improved. For example, algorithm PP-a's “prebuying” idea deserves more intuition in the main text.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: All reviewers agree that the paper makes a solid contribution to learning-augmented algorithms for online knapsack, with rigorous theoretical analysis and strong empirical validation. They praise the clarity of the proofs, the near-optimal consistency–robustness trade-offs, and the extension from fractional to integral items under reasonable assumptions.
Decision: Accept (poster)