Online Knapsack with Frequency Predictions
Authors: Sungjin Im
Ravi Kumar
Mahshid Montazer Qaem
Manish Purohit
Venue: NeurIPS 2021 Poster (2021)
Keywords: online knapsack
learning-augmented algorithms
semi-online algorithms

Abstract: There has been recent interest in using machine-learned predictions to improve the worst-case guarantees of online algorithms.  In this paper we continue this line of work by studying the online knapsack problem, but with very weak predictions: in the form of knowing an upper and lower bound for the number of items of each value.  We systematically derive online algorithms that attain the best possible competitive ratio for any fixed prediction; we also extend the results to more general settings such as generalized one-way trading and two-stage online knapsack. Our work shows that even seemingly weak predictions can be utilized effectively to provably improve the performance of online algorithms.

Online Knapsack with Frequency Predictions
Sungjin Im Electrical Engineering and Computer Science University of California, Merced sim3@ucmerced.ed.
Ravi Kumar
Google Research Mountain View, CA ravi wwwkkk3ammll...mmm com
Mahshid Montazer Qaem Electrical Engineering and Computer Science University of California, Merced
Manish Purohit
Google Research
Mountain View, CA
rmottazzerrqembbccerrrcc... edu
mpurohit@@oogle..oomm
Abstract
There has been recent interest in using machine-leamed predictions improve the worst-case guarantees of online algorithms. In this paper we continue this line work by studying the online knapsack problem, but with very weak predictions: in the form of knowing an upper and lower bound for the number of items of each value. We systematically derive online algorithms that attain the best possible competitive ratio for any fixed prediction; we also extend the results to more general settings such as generalized one-way trading and two-stage online knapsack. Our work shows that even seemingly weak predictions can be utilized effectively to provably improve the performance of online algorithms.
Introduction
An algorithm designer's ultimate goal is to develop algorithms that are reliable and work well in practice. High reliability has been the major focus of discrete algorithmic research that primarily seeks to give strong worst-case guarantees for all inputs. Unfortunately, such algorithms treat all input instances on equal footing-even pathological ones that rarely occur in practice-and do not necessarily exploit the latent structure that can be present in realistic instances. In contrast, machine learning has demonstrated amazing successes in many real-world applications, yet occasionally exhibits unacceptable failures on specific (worst-case) instances.
Leaming-augmentte algorithm design has recently emerged model achieve both reliability and worst-case guarantees, particularly in the online setting. In this model, an online algorithm is given certain predictions the input it will face in the future, and the algorithm then makes irrevocable decisions as the actual input is revealed one by one. Ideally, the algorithm should perform close to the optimum when the predictions are good, and yet possess worst-case guarantees even when the predictions are malicious. Recent work has shown that this is achievable for online problems such as
caching [7 26 29] ski-rental [4] 22] scheduling (6 [15 22 (28), load balancing [23], secretary problem metrical task systems set cover (7], flow/matching (24], bin packing [3, etc.
given as prediction specific value of key parameters of the online instance, e.g., the number of days to ski in the ski-rental problem the next request time of page in the caching problem. In this paper, take relaxed approach and assume that the prediction only gives a range of values for key parameters. This is natural way model weak predictions where the predictor has high uncertainty and only provide a reliable range in which the value must lie. Given such weak predictions, we seek to obtain beyond worst-case guarantees for all inputs respecting the prediction, by possibly exploiting the structure
Most prior work
augeeeted online algorithms assumes that
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

provided by these predictions. In fact, we seek algorithmss that give worst-case guarantees for all inputs while promising sharper bounds for instances that indeed respect the predictions. In this paper, we design such dearning-augmentie algorithms with weak predictions for the online knapsack problem, which a basic problem of practical importance
Knapsack Problem and the Prediction Model. In the classic online knapsack problem, we have knapsack of unit capacity" and n items that arrive online. Each item has profit pt 2 and size 0 S 8/ S 1. For convenience, we define the value of an item, V/ ;= pi/s;, to be the profit of the item per unit size. We assume that the value of each item lies in a range known a priori, i.e. we have Umin I 0 S Umax for some known constants Umin and Vmma algorithm must make an irrevocable choice of whether to accept or reject the item. The goal is to select subset of items of the highest total profit whose total size is at most the knapsack capacity.
ii When an item arrives, an online
Recall that online algorithm is said to have competitive ratio c, equivalently, be e-competitive if the algorithm's 's objective (profit) is at least e times the total profit obtained by the optimal solution for all inputs. Zhou, Chakrabarty, and Lukose [31] gave a 1/(1 In Ymax )-competitive algorithm (that we call ZCL) under the assumption that all items have infinitesimal sizes (or can be accepted fractionally) and further showed that no algorithm can obtain a better competitive ratio.
Vmin
Online knapsack is a fundamental problem in online algorithm design and finds applications in many real-world settings, e.g., in the context of online auctions [1 and charging electric vehicles [30]. For these practical applications however, the worst-case guarantees offered by standard competitive analysis are too pessimistic to be useful. Indeed, practical instances are not typically worst-case and further one often possesses some forcknowledge of the kind of items that expected to arrive in the future. In an online ad-auction, for instance, the advertiser can reliably predict a range such that the number of queries in a day for particular keyword lies within the range. In this work, we explore formal models to utilize such predictions to obtain provably good algorithms for online knapsack beyond what is possible via classical competitive analysis. In particular, we introduce and study the online knapsack problem with frequency predictions (KNAPSACK-FP),, described next.
Let Vdenote the set of all possible values that items may take, and Umin min(V) and Umaa mVx(V)) denote minimum and maximum values respectively. We may assume that the items have discrete values by rounding them to the closest power of (1 + e) for some > O, yielding [V| (log((mmax) (mmxx/mmm))) and making the competitive ratio only marginally worse. For any value u E V. let s, = E ble== S; denote the total size of items with value In the online knapsack with frequency predictions problem, for each value v V, the frequency predictions P {ly; uele provided to the algorithm are a lower bound E and an upper bound Uy such that eg I S. S. Uyg We say that the algorithm has a competitive ratio of a for KNAPSACK-FP with prediction P if the algorithm's 's profit is at least a times the optimum for all inputs respecting the given frequency prediction P. Our goal is to design an online algorithm with the best competitive ratio for this prediction model.
1.1 Our Results and Techniques
Our main result is a nearly optimal algorithm for KNAPSACK-FP.
Theorem 1. For KNAPSACK-FI -P,, given any frequency predictions, we can find an algorithm of competitive ratio a Smax
([VI + 1). max; 8ú, where a² is the best possible competitive ratio for the problem (with predictions).
Umin
Our algorithm, called SENTINEL, pre-computes a budger by for each value e and accepts items that maintain the invariant that the total size of accepted items of value at most v is at most B,- := Sang. by for all v E V. some sense, B, can be viewed as a sentinel to guard against accepting too many low-valued items. The key intuition underlying our algorithm that the knowledge regarding the arrival of future higher-valued items enables it to not over-allocate capacity to earlier lower-valued items. Our algorithm can also be implemented using only Olog VV) time per item. We note that the additive loss of Famax (1V++1) max; 8, in the competitive ratio in Theorem is
Eysin
'This without loss of generality by scaling all sizes. i "Such an assumption is necessary since otherwise we cannot hope for bounded competitive ratio in the adversarial model [27 31).

---

due to reduction to a continuous version of the problem (as discussed in Section 2 and this quantity approaches zero as max, s; - 0.
Interestingly our algorithm has a distinguishing feature from the ZCL [31 algorithm for the standard online knapsack. The ZCL algorithm constructs threshold function (t) (e Umax/ /maax//unin) //ninn ) (Emin/e) a priori and accepts an item online if its value is no smaller than (t) when é is the knapsack capacity that has been consumed. In contrast, we show that no such algorithm that maintains threshold function based on the capacity used can give the optimum algorithm (Section (.2).. We note that by combining our algorithm and ZCL (say by using a Y fraction of the capacity to run our algorithm and the other case guarantee of 1-y
fraction to run ZCL), we can simultaneously obtain a worst- Iolog Jmaxy as well as our improved guarantees for instances that respect the
prediction. Further, we can easily extend our result to show that our algorithm has a small loss in the competitive ratio when the predictions are slightly incorrect, for example, when have ( + S S, S u +)).
Extensions. We extend our model and results to two generalizations of the knapsack problem: the generalized one-way trading problem and the two-stage online knapsack problem. In generalized one-way trading [13] 30), each item of type is associated with certain concave function fa with fe(0) = 0. If an algorithm accepts s amount of items having type t, then it obtains profit f(()). The goal, as always, is to accept a set of items subject to the knapsack capacity maximize the total profit. This is a well-studied problem. motivated by converting given amount of money from one currency to another, in the presence of time-varying conversion rates.
The two-stage online knapsack a generalization that we introduce this paper. The key difference from the standard setting is that after sceing all the items, the online algorithm is given another chance in a second stage to accept any items that it rejected before. But, an item accepted in the second stage gives only À < 1 fraction of its original profit. The two-stage knapsack effectively interpolates between the online and offline problems: it becomes the standard online knapsack problem À = O, and the offline problem if X = 1. The two-stage setting has natural applications. For example, while clients typically prefer to know if their requests will be accepted instantly, some might choose to wait further for discount, albeit with the possibility of getting service if the service provider accepts other competing requests arriving later.
For both extensions we generalize our results and obtain the best competitive algorithms given frequency predictions (Sections 4 5p. This shows that our prediction model and analysis could find more applications, providing beyond-worst-cas. guarantees even with weak predictions.
Experiments. In Section 6 we conduct experiments on synthetic data sets, and show our algo- rithm augmented with frequency predictions considerably outperforms the classic worst-case ZCL algorithm.
1.2 Other Related Work
The knapsack problem has been extensively studied in the literature. For a comprehensive survey of the results the offline knapsack problem, [18). The offline version of the standard knapsack problem and most of its variants are well-known to be NP-hard.
The classic online knapsack problem falls into general class of problems called online packing problems and one can obtain an Q In(Umax (00ma//mmm))))) Ummnn) -compeiiceeeee algorithm via the online primal- dual technique [10 11 For a nice survey of online primal-dual technique and its applications for various packing and covering problems, see [12. Sun et al. [30] generalize the threshold algorithm in 31 by introducing control parameter that adjusts how fast the threshold grows. They empirically learn the best parameter within a certain range to retain some worst-case guarantees, but do not provide optimality. Kong et al. [2I] empirically show that reinforcement learning can find good threshold for the online knapsack.
Another line of work considers the stochastic online knapsack problem where items' profits and sizes are drawn from distribution (e.g.. see (2 25 20 and their follow-up works). In the random arrival model, the items are assumed to be chosen adversarially but arrive in uniformly random order. In this model, one can obtain constant competitive algorithms 19] and further if all items have an infinitesimal size, one can obtain nearly-optimal online algorithms
197. There are many other
3

---

variants studied and we only mention few here, e.g., removable online knapsack problems [16] and online knapsack with reservation costs [8]
2
Preliminaries
To ease the presentation, we will consider the following relaxed model, which differs from KNAPSACK-FI in aspects: first, we allow item to be accepted fractionally and second, we allow an item to have any value in [Umin, Umax] not from discrete set. The second relaxation is purely for ease of presentation and preserves the competitive ratio. The first relaxation results in a small additive loss in the competitive ratio since at most one item is accepted fractionally among those of the same value and all items assumed be small. We now formalize the relaxed model.
Continuous- Valued Online Knapsack with Frequency Predictions (C-KNAPSACK-FP) In the continuous version, we assume that there is a continuum of items, each having infinitesimal size and some value [Uming Umax]. In particular problem instance, for any value [Umin; Umax] let s(r)dv be the total size of items having value in the range [t; v + du] for some sufficiently small du. For each value [Umin: Umax]; we given a lower bound [(v) ((())")(()))
and upper bound u(v) such that s(v) E [L(v), u(v]]. We assume that (v), ((v), u(u) are all continuous in v. Define S(v) = Sy= s(x)d I(v)= == Ja= ((x)dr, and U(v) == f -=mmin u(z)dr, which are differ- entiable at all E [umin: Umax by definition. As in the standard model, we have knapsack of unit capacity, and the goal to select subset of items of total size at most one that maximizes total value. The following relates the competitive ratio of the standard and the continuous-valuee versions.
Lemma 2. Given prediction P (fri ) NEV for KNAPSACK-FP. we can create prediction P' (L(v); (()))
(())) vElymin (mnne) for C- C-KNAPSACK-FF in polynomial time such that
1. An a-competitive algorithm for C-KNAPSACK-FI with prediction P' implies an (a Pmaa V max; 8.) comppttiieeee algorithm for KNAPSACK-FP with prediction P.
Vmin
2. If no algorithu has a competitive ratio better than a for C-KNAPSACK-FP with prediction Pt, then no algorithm has a competitive ratio better than a + max; s; for KNAPSACK-FP with prediction P.
Thus, if we find an algorithm with the optimum competitive ratio for C-KNAPSACK-FP, then we will have Theorem In the rest of the paper only consider the continuous version for convenience.
The SENTINEL algorithm
Let (l(v); u(v) ( (e( (moa: be a fixed set of predictions; this defines a family of knapsack instances, where each instance is a sequence of items, each with profit and size. Let denote the desired competitive ratio of our algorithm. We first derive an online algorithm that guarantees a competitive ratio of assuming one exists and then discuss how one can find the optimal such competitive ratio a". For any instance Z, let OZT(Z) denote the total value obtained by the optimal solution for instance I. To systematically derive our algorithm, it is instructive to consider the following family of instances. For any value v E [Umin: J. let M(r) denote an instance containing the maximum possible amount of items of value at most and the minimum possible amount of items
of value larger than v. Formally, M(U) is an instance such that s(x) = u(x) for all x S v and s(x) {(x) for all > Further, items in M(r) arrive in the following order: first ((x) items
of value x E [umins Umax] arrive in non non-decreasing order of value, followed by u(x) - f(x) items
of value x < arriving in non-decreasing order. Note that we consider M(r) only to derive algorithm.
Step
Let denote the largest value such that
Umax T f(x)dr aa OPT((((()
(1)
We use the functional notation (e.g., {(v)) for the continuous case and the subscript notation (e.g., f..) for the discrete case.

---

Intuitively v" denotes the largest value such that an algorithm is guaranteed to be a-competitive even it does not accept any items value less than v². Note that since assume that the functions {(-) and u(-) are continuous, such a value " is guaranteed to exist by the intermediate value theorem.
Step 2.
Consider an adversary that has constructed an instance of the form M(x) for some unknown value By instead constructing instance of the form MMx + dr), the adversary gain
additional profit of d OPT(MM())) In order to maintain competitive ratio of a, our algorithm must dx
accept enough additional items of value that it receives profit of at least d (PT((((x))
dr Motivated by this discussion, we define a function 7 [v", Umax] + [0, oc) to determine the additional amount items particular value that our algorithm accepts.
T(x)
a (M))) x de
Vor E [v", Umax]-
Step For any value x E min: ma we define budget function as follows.
[0, b(x) = (((x)+ + Txx),
< o² Vx 2 U²
f b(x)dr
and B(v)
Vu
[Umins Umax]-
For any value the budget function ((v) defined above prescribes the maximum total amount of items of value most that must accepted. Formally, let A(v) denote the total amount of items of value at most that has been accepted by the online algorithm so far. Then, when an item of value arrives, the algorithm accepts the item if and only A(x) ((x) for all U.
Step 4. Finally, discuss how find the optimal competitive ratio. The functions T(-). 6(-), and B-) defined above are all (implicitly) functions of the desired competitive ratio a. To make this dependence explicit, let (-) denote the budget function for some fixed a. It can be easily verified that (Umax) is a continuous and monotonically increasing function of a. Assume U (? > 1 since otherwise
accept all items by setting b(z) = u(x) and we obtain competitive ratio of 1. We set a* E (0, 1) to be such that Ba (Umax) = 1. Again, by the intermediate value theorem, such a" is guaranteed to exist and further one compute it up arbitrary precision by binary search. For clarity, we include a formal description of the algorithm in the Supplementary Material.
3.1 Analysis
We begin by proving that our algorithm is indeed a" a--compttitive for any instance of C-KNAPSACK-FP that respects the given frequency predictions. Let ū be the largest value such that A(o) B(ū): if no such a value exists, 0 Emin- Let ALG and OPT denote the total value of items chosen by our online algorithm and the optimal solution respectively. In the following two claims, we first bound ALG and OPT respectively.
Claim 3. ALG
S Sam
b(x)))))))) dx + fiman x s(x) dr.
Proof. For convenience of notation, let ((v)
4 A(x))an denote the marginal amount of items of
de value u accepted by the algorithm. Since we have A(v) B(v) for all o, the algorithm accepts all items having value larger than and thus a(x) = (1;), Wo > 6. Also, by definition of ö, we have A (6) B()). Thus, we have the following.
a(z)dx + f x e-s(x)dr
ALG
a(z)dz=
z=vmin
integrating the first term by parts yields
Vmnax
ALG = 5 A(ö) Vnnn A(vmin)
A(x)dz +
x s(x)dr
Vmin
5

---

since A(o) B()) and A(x) I B(x), Vz, by definition of our algorithm
Ü. B(ū Umin ((emin)
B(x) +
z==
Pmin
x b(x)dx + [ a s.s())d
Claim 4. OPT S OPT(M(()) + J (s(x) (((x)) dr.
Proof. Let the optimum solution accept s(x) {(x) items of value for free without consuming the knapsack capacity for all x E (0, Unnax] The remaining items form an instance I' that is dominated by M()), Le., for any value I' is at most the amount of items with value x in M()). However, by definition, OPT(M(() the maximum profit that one obtain from M(ž) and the claim follows.
[Mmin mmax]. the amount of items having value in the instance
The following is from the definition of SENTINEL and is useful to relate the value of the optimal solution for any instance of the form M(r) to the budget function b(-) utilized by algorithm.
Claim 5. For any value v E [o", Umax] a" OPT(M(F)) femas (((x(())))){( dic + + Sammanu b(x) dr.
Proof. For all 2 vt, we have the following.
a' . OPT(M(()) = = (OPT(M(O'))
l" ==
d (PT(MM()))rr
substituting and
-f Je x.((x)d + S x T(r)dr.
Vmax
The claim follows by the definition of b(x) ((x)++(x) forall 2 v², and b(x) = 0, Vo v².
Finally, we are ready to show that the algorithm is indeed a competiiivee. Claims 3 and 5 together yield that:
Umax
ALG 2 a OPT((((()
+
x x (5(x) - {(x))dx
==
2a (OPT(O(TMM)
Pmaa
x (s(x) {(x))dr) 2 a OPT,
where the last inequality follows from Claim Thus, we have the following theorem. As discussed, the value of ax depends on the predictions.
Theorem 6. For any input instance that respects the frequency predictions (E(v), (Vmin Pmuax) the SENTINEL algorithm is o -=-copeetitive for C-KNAPSACK-FP.
3.1.1 Optimality of Competitive Ratio
In this section show that the competitive ratio obtained by SENTINEL is optimal. In other words, no algorithm, even randomized, can obtain a competitive ratio of better than a for C-KNAPSACK-FPP.
We will consider the family of instances ((x) amount of items of all values E [Umin; Umpax] arrive in non-decreasing order of value, followed by u(x) - {xx) amount of items of value x E [Umin: vr). which also arrive non-decreasing order of value. Consequently, until an algorithm sees items of value higher than in the second stage, it cannot distinguish between instances in
Recall that in the instance M(v), first
In other words, the instance M(U) is prefix of each of the instances in {M(x)) [efv:wa() Thus for any value v, the adversary can either strategically stop the instance M(v)) continue to release higher-valued items.
Lemma 7. For any given set {l(v). (((u))e((unn (e(lumnn of frequency predictions, let o² denote the competitive ratio of the SENTINEL algorithm. Then no deterministic algorithm can obtain a competi- tive ratio larger than a on all instances in the family {M(r) (0min Pmaas]

---

To see why randomization does not help, consider the deterministic algorithm that accepts each item by the expected amount that the optimum randomized algorithm accepts. This is well-defined as we are allowed to choose items fractionally. It is easy to see that the algorithm never exceeds the knapsack capacity and obtains as much value as the randomized algorithm. Thus, we have:
Theorem 8. For any given set { ro((min (umin, of frequency predictions, there exists no randomized algorithm that attains a competitive ratio better than that of the SENTINEL algorithm.
Figure 1: Illustration of the optimal competitive ratio a' obtained by SENTINEL (in red) for predictions b, 1/100 and ut = (1 d) by for integers v [Umin 1, 1maxxx 100]. The competitive ratio is shown for E [0, 2]. For comparison, the competitive ratio result- ing from accepting & items of value e is shown in blue, i.e. (PT(M(O))/or(((((a))
C4-
412
37 5.%
125
188
Thus SENTINEL yields the optimal competitive ratio for any given set of predictions. It can be easily verified that the classical adversarial online knapsack problem is equivalent the special case with predictions {(v and u(v) oc for all v E [Vmin, Umax]] For this special case, we recover of ZCL. For more informative predictions, obtain much tighter
the competitive ratio I+In
Vaniin
competitive ratios. Indeed, ((2) u(v).. (, Ve [Umin Umax]. then a* 1 and SENTINEL obtains the optimum solution. Figure 1 illustrates the optimum competitive ratio for family of predictions.
3.2 Need for Sentinel
30 have all been threshold Prior algorithms for (variants of) the online knapsack problem 31 algorithms. i.e., the algorithm chooses a threshold y that is a function of the amount of residual capacity left in the knapsack and the algorithm accepts an item if and only if its value is higher than the threshold. On the other hand, the SENTINEL algorithm does not fit into this framework since the threshold for choosing an item depends on the values of items already chosen by the algorithm. In this section we show that there are predictions (l,; Uh hev such that no pure threshold-based algorithm can achieve the best competitive ratio. In fact, these predictions use only two values.
Let I denote a family of instances that respect the following predictions. There are two distinct values, V {1,2). The predicted bounds are given by 4 l2 and μ u2 2/3. As discussed in Section 3.1.I since randomization has no benefits, we only consider deterministic algorithms.
Claim 9. No deterministic online algorithm that maintains a non-decreasing threshold function (2), where is the knapsack capacity used, and accepts item and only if its value is higher than To (z) has competitive ratio better than 4/5 for the family of instances I.
On the other hand, with these predictions there is a simple algorithm that obtains competitive ratio of 6/7. 7. Let Agentinl denote the following algorithm: accept all items of value and accept at most 4/7 items of value 1. The proof of the following claim follows from simple case analysis.
Claim 10. For the instances in I, the algorithm Aventinet yields competitive ratio of 6/7.
4 Generalized One-Way Trading
In the classical one-way trading problem 13], trader needs to convert unit of money from one currency another. Faced with sequence of (unknown) exchange rates that are presented online, the goal is to maximize the amount of money obtained in the target currency. In this section we consider following generalized one-way trading problem, also considered by (30]: There are T different types of items and each type / is associated with concave value function ft. For convenience, we consider the setting where each item i has the same infinitesimal size X. Items arrive online and the total value carned by the algorithm is E. f(()), where I denotes the total size of items of type t
7

---

accepted by the algorithm. The goal is to design an algorithm that maximizes the total value such that the total size of accepted items is at most one. As the online knapsack problem, we assume that the algorithm has access to a lower bound & and an upper bound u4 on the total size of items of type I.
We now show that can reduce this problem to the online knapsack problem with predictions. For each type t, we create & f mandatory items with values fA), fe(2)) (f.)............. f:(4.........)))))-.....)..) f((e respectively. Additionally, we create /t/ Ä optional items with values fc f fe(w, - X) respectively. Note that many created items belonging to different types may have the same value. For each value v, let E(v) be the total size of mandatory items of value v and similarly let u(v) be the total size of all mandatory and optional items of value v. Let A be an online algorithm for the knapsack problem using predictions {E(v), u(v) J. For the generalized one-way trading problem, as items arrive online, we construct an instance of the knapsack problem online such that the kth item of type t has value (k-2 (e((k 1))). Finally, we accept an item (in the generalized one-way trading problem) iff the corresponding item is accepted by algorithm A in the knapsack instance.
(ue)
It is easy to verify that the optimum solution attains the same value, say OPT, in both the problem instances. Let a" denote the competitive ratio attained by A, and hence the total value obtained by A on the knapsack instance is at least a' OPT. On the other hand, suppose A accepts items of type i, then due to concavity of fe, it attains a value of at most Σ Sc(iA) - fe((i - 1)A) = (k())
Thus, the total value obtained by the online algorithm for the generalized one-way trading problem at least that obtained by A and hence it is also a coomppttiiivee
5 Two-Stage Knapsack
Consider the following two-stage version of the typical fractional online knapsack problem. An instance here is parameterized by a discount factor 0 S X S 1. Once again, for convenience, we work in the continuous model, so there is continuum of items each having infinitesimal size") We assume that all items have value between [Umin: | When an item of value v arrives, an algorithm can either pick the item and receive value of v or it may choose to reject the item. After all items have arrived, the second stage starts and the algorithm can go back to previously rejected items and choose some of them, subject to the knapsack capacity. However, an item originally of value v is only worth Au in the second stage. Note that an item cannot be rejected once it gets accepted in either stage.
We note that this two-stage knapsack formulation naturally interpolates between the online and offline versions of the standard knapsack problem; when O. an algorithm cannot obtain any value from the second stage and hence reduces to the regular online knapsack problem, whereas with X = 1, an algorithm can commit to only accepting items the second stage after all items have been revealed and thus the problem reduces to the offline version.
To the best of our knowledge this problem has not been considered in the literature. Thus first show how to obtain the optimal competitive ratio for the problem in the absence of predictions. We then continue show how incorporate predictions on item frequencies for each value. We present the algorithm without predictions and defer the one with predictions to the Supplementary Material.
5.1 Algorithm for Two-Stage Knapsack without Frequency Predictions
As before let a* be the optimal competitive ratio for the problem, which will be decided later. In the absence of predictions, the optimal competitive ratio can be attained by threshold algorithm. In the first stage of the problem, the algorithm will maintain a threshold function depending on the knapsack capacity used and accept an item if and only if its value is higher than the current threshold. Finally, in the second stage, is easy to observe that any reasonable algorithm accepts the highest value items that can still be accommodated in the knapsack. We now show how to systematically derive such an algorithm.
For any value v. let 2()) be the fraction of the knapsack capacity for which the algorithm maintains the threshold at value v. To derive 2(0) we will consider the following family of adversarial instances: (i) items arrive in increasing order of value: (ii) there are enough items of each value to fill the entire knapsack; and (iii) the adversary can stop releasing items at any point in time.
" As in Lemma D when items have sufficiently small sizes, this assumption only leads to a small additive loss in the competitive ratio.
8

---

1.0
0.5
640
0.90
0.5
0.00
compaiiive
30.15
0.00
0.0
0.00
0.25
0.75
1.00
1.25
2.00
actual competitive ratio
ZCL's actual competitive ratio
Our theoretical competitive ratio
ZCL's theoretical competitive ratio
Figure 2: Illustration the empirical and theoretical competitive ratios our algorithm SENTINEL and ZCL. In the left, Umin 1, Umax 100, and 5 E [0, 2]; and in the right, Unin E 100] Pmax
Umin 99 and In both uh [(1 + 6) All items have size 1/10000.
We construct z(v) that is continuous at all E (Umins Mmax follows. First we set, 2(Umin) = e'-A This is because if the adversary only gives items of value Vmin and they enough to fill up the knapsack, then by accepting z(Vuin) of them in the first stage and more to the full capacity in the second stage we obtain profit (=(Umin) + A(1 - z(Umin) Mmiin a Umin
1-X
Now consider any value >> Umin If the adversary stops the instance at value the profit obtained by algorithm is:
ALG(u)= Umin a (Umin)
x. =xx)dx + Xu =(Umin)
[ =(x)dx)
Here, the first two terms denote the value earned by the algorithm in the first stage while the last term denotes the profit gained in the second stage. In particular, (1 - =(Umin) - Jz=e =(x)dr) is the amount of capacity left in the knapsack after the first stage and the algorithm will fill with the best items-ot value u u-and receive value of Au per each unit.
To maintain competitive ratio of ax, we need to maintain for all v E (Vmins Umax) M(v)) = a"v. By solving this, together with ((imin) + J.e (eean Umax] 2(x)dr we can find and 2(1). Then, set the threshold function & (t) as follows:
T (t) = Umin
if <
a'-2
1-X
Z
otherwise
<x;)dx;; this integral includes 2(Umin). And if we see an item value in the first phase when the knapsack is f-full, we accept v 2 (t). In other words, we keep the threshold at Umin until the knapsack gets ='uA-f afterwards, keep the threshold at u for z(v) units. In the second phase, we accept the highest valued remaining items to the full capacity. Further details in the Supplementary Material.
where
6 Experiments
We design experiments to show that our algorithm, SENTINEL, achieves considerably larger profit than ZCL [31 even when we are given loose frequency bounds as predictions. Specifically, we consider the following setup. The knapsack capacity is set to 1. Each item is assumed to have a size 10-4 and an integer value the range of [Umin = 1, Umax = 100). For each value e, its frequency lower bound f, is sampled from [50, 150] independently and uniformly at random; therefore, in expectation, least 10a items arrive an instance. We use a control parameter 8 to derive the upper bounds from f, and set u, [(1 + 8)6, For each instance, s, is sampled from [L., up]

---

independently and uniformly at random and items arrive in random order. The results are the geometric average over 10 instances.
In the first experiment we observe how the competitive ratios of SENTINEL and ZCL. change as we vary ó from 0 to 2. Intuitively, smaller å value means better predictions. We confirm that SENTINEL outperforms ZCL for all values of in terms of empirical as well as theoretical competitive ratios. The actual competitive ratios degrade ô grows, but SENTINEL continues dominate ZCL.
In the second experiment, we consider different values of Umin in the range of {l...., 100), fixing the difference Umax Vmni 99 and 2. The goal of this experiment is ratios change as the ratio Vmaxx/ Umin changes. Note that the ratio decreases from 100 to nearly 2. Recall that ZCL has competitive ratio 1/(1 In(Vmax/ |n((max//uun))) /min)) Again, SENTINEL consistently outperforms ZCL,, although the difference becomes smaller as Umax/ Umin decreases.
how the competitive
7 Conclusions
In this paper we studied the online knapsack problem and its extensions when given the range of the number of items of each value predictions. We showed that even such weak predictions can be exploited to give provably better competitive ratios. It would be interesting to revisit other problems with such weak predictions. Another fruitful direction is explore other types of weak predictions.
References
[1] Albers, A. Khan, and L. Ladewig. Improved online algorithms for knapsack and GAP the random order model. Algorithnica, pages 1-36, 2021.
[2] K. Anand, R. Ge, and D. Panigrahi. Customizing ML predictions for online algorithms. In ICML, pages 2020.
[3] S. Angelopoulos, S. Kamali, and K. Shadkami. Online bin packing with predictions, 2021. arXiv:2102.03311.
[4] A. Antoniadis, C. Coester, M. Elias, A. Polak, and B. Simon. Online metric algorithms with untrusted predictions. In ICML, pages 345-355, 2020.
[5] A. Antoniadis, T. Gouleakis, P. Kleer, and P. Kolev. Secretary and online matching problems with machine learned advice. In NeurlPS, 2020.
[6] É. Bamas, A. Maggiori, L. Rohwedder, and O. Svensson. Learning augmented energy mini- mization via speed scaling. In NeurlPS, 2020.
[7] É. Bamas, A. Maggiori, and O. Svensson. The primal-dual method for learning augmented algorithms. NeurlPS, 2020.
[8] H. Böckenhauer, E. Burjons, Hromkovic, H. Lotze, and Rossmanith. Online simple knapsack with reservation costs. STACS, 2021.
[9] C. Borgs, J. Chayes. N. Immorlica, K. Jain, O. Etesami, and M. Mahdian. Dynamics of bid optimization in online advertisement auctions. In WWW, pages 531-540, 2007.
[10] N. Buchbinder and Naor. Online primal-dual algorithms for covering and packing problems. In ESA, pages 689-701. Springer. 2005.
[11] N. Buchbinder and Naor. Improved bounds for online routing and packing via a primal-dual approach. In FOCS, pages 293-304, 2006.
[12] N. Buchbinder and Naor. The design of competitive online algorithms via primal-dual approach. Found. Trends Theor. Comput. Sci., 3(2-3):93-263, 2009.
[13] R. EI- Yaniv, A. Fiat, M. Karp, and Turpin. Optimal search and one-way trading online algorithms. Algorithmica, 3001):011-13, 2001.
10

---

[14] S. Gollapudi and D. Panigrahi. Online algorithms for rent-or-buy buy with expert advice. In ICML, pages 2319-2327, 2019.
[15] Im, R. Kumar, M. Montazer Qaem, and M. Purohit. Non-clairvoyant scheduling with predictions, In SPAA, pages 285-294, 2021.
[16] K. Iwama and S. Taketomi. Removable online knapsack problems. In ICALP, pages 293-305, 2002.
[17] Z.. Jiang, D. Panigrahi, and K. Sun. Online algorithms for weighted paging with predictions. ICALP, pages 69:1-69:18, 2020.
[18] H. Kellerer, U. Pferschy, and Pisinger. Knapsack Problems. Springer, Berlin, Germany, 2004.
[19] T. Kesselheim, K. Radke, A. Tonnis, and B. Vocking, Primal beats dual on online packing LPs the random-order model. SIAM Journal on Computing, 1735)11939-196, 2018.
[20] A. J. Kleywegt and J. D. Papastavrou. The dynamic and stochastic knapsack problem. Opera- fions Research, 46(1):17-35, 1998.
[21] W. Kong, C. Liaw, A. Mehta, and D. Sivakumar, A dog learns old tricks: RL finds classic optimization algorithms. In ICLR, 2018.
[22] R. Kumar, M. Purohit, and Z. Svitkina. Improving online algorithms using ML predictions, In NeurIPS, pages 9661-96700 2018.
[23] Lattanzi, T. Lavastida, B. Moseley, and Vassilvitskii. Online scheduling via learned weights. In SODA, pages 1859-1877, 2020.
[24] T. Lavastida, B. Moseley, R. Ravi, and C. Xu. Learnable and instance-robust predictions for online matching, flows and load balancing. In ESA, pages 59:1-59:17, 2021.
[25] G. S. Lueker. Average-case analysis of off-line and on-line knapsack problems. Journal of Algorithms, 29(2):277-305, 1998.
[26] Lykouris and S. Vassilvtiskii. Competitive caching with machine learned advice. In ICML. pages 2296-3305,,0 2018.
[27] A. Saarchetti-Spaccammee and C. Vercellis. Stochastic on-line knapsack problems. Mathematical Programming, 68(1):33-004 1995.
[28] M. Mitzemmacher. Scheduling with predictions and the price of misprediction. In ITCS, pages 14:1-14:18, 2020.
[29] D. Rohatgi. Near-optimal bounds for online caching with machine learned advice. In SODA, pages 1834-1845, 2020.
[30] B. Sun, A. Zeynali. T. Li, M. H. Hajiesmaili, A. Wierman, and D. H. K. Tsang, Competitive algorithms for the online multiple knapsack problem with application electric vehicle charging. Proc. ACM Meas. Anal. Comput. Syst., 4(3):51:1-51:33 2020.
[31] Y. Zhou, D. Chakrabarty, and R. M. Lukose. Budget constrained bidding in keyword auctions and online knapsack problems. In WINE, pages 566-576, 2008


Reviews:
[{"review_id": "qOvgAeOTWRu", "reviewer": "Reviewer_ZGPi", "summary": "This paper considers a variant of the classical online knapsack problem where each possible value, the size of an item is contained in a known interval (called frequency prediction). The paper proposes an algorithm and shows that its competitive ratio is optimal. Furthermore, the authors show some applications of the problem and the algorithm.\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Comments:\nThe writing is generally good. However, Summarized descriptions of the proposed algorithms are helpful (such as the algorithmic environment of latex). Also, the protocol of the problem is not clearly written, in that the information of size or profit of item is given to the player before or after the player makes a decision to accept/reject the item. This information is important but is missing. So, I do not fully understand why “predictions” of intervals of sizes are helpful. \n\nThe technical results are non-trivial and strong, in that the proposed algorithm is optimal in some sense. But, the analyses of the paper seem to follow standard approaches of the online algorithm literature (e.g., continuous relaxation) and I am not sure how significant the techniques are. \n\nMaybe one of my concerns is if the scope of the conference matches the topic of the paper. At a glance, the paper is more suitable for algorithm-related conferences. The problem setting might be interesting from an algorithmic perspective, but I am not aware of any realistic motivations for the formulation. This could be a weakness of the paper unless the authors address motivating applications.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "bWBRc-opuo", "reviewer": "Reviewer_YbwL", "summary": "This paper studies the well-known online linear knapsack problem (and two of its generalizations) in the learning-augmented setting where the goal is to incorporate some ML predictions of the future online input such that the algorithm is consistent when the predictions are good and also robust in case of malicious predictions. The authors show that the threshold-based algorithms (such as the optimal worst-case algorithm for this problem) could not achieve the best competitive ratio in the learning-augmented setting and they provide a novel algorithm to attain this goal. Finally, some experiments on synthetic data sets are provided to verify the superior performance of the proposed algorithm compared to the worst-case algorithm in the setting with predictions.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Main strengths of the paper:\n- The online knapsack problem is extremely well-motivated and therefore, obtaining learning-augmented algorithms for this problem is of potential interest to a wide audience.\n- Unlike many previous works in the learning-augmented setting, the techniques used to design the algorithm are quite different from those used in the optimal worst-case algorithm for the problem and so, the theoretical contributions of the work are significant.\n- The experiments are well designed to verify and highlight the theoretical results of the paper and show the superiority of the performance of the proposed algorithm.\n\nMain drawbacks of the paper:\n- It is really hard to follow all the notations used in the paper and understand the arguments of the proofs. For instance, I am not sure what $B_{\\alpha}(\\cdot)$ is in Step 4 (Section 3) of the paper. I did not find the definition elsewhere. It would be great if all the notations are summarized in one place for future reference (currently, it is scattered throughout pages 4 and 5)\n- The authors need to precisely discuss the size of the additive loss in the competitive ratio (due to discretization) in intermediate cases where $\\max_i s_i$ does not approach zero. For example, if we consider the discretization mentioned in the paragraph before Section 1.1 (with $k$ discrete values), what is the exact dependence of $\\max_i s_i$ on $k$ and how fast the whole additive loss approaches 0 as $k$ grows larger.\n- The proposed algorithm addresses the case where predictions are all correct and the authors mention that a linear combination of this algorithm with the optimal worst-case algorithm leads to a consistent and robust learning-augmented algorithm. However, this linear combination might not be the best way to incorporate both robustness and consistency, and designing a single algorithm that incorporates both the worst-case and predictions usually leads to better results. For instance, if similar to [7], there is a parameter $\\lambda \\in [0,1]$ denoting our confidence in the predictions, how would the robustness and consistency bounds depend on $\\lambda$?\n********************************\nPost-Rebuttal Update: Thanks to the authors for their detailed responses to the raised questions. While I highly value the theoretical contributions of this work, I still believe that a detailed discussion about the dependence of the additive loss in the competitive ratio (due to discretization) on $k$ and its order of magnitude for finite $k$ is necessary to complement the result of Theorem 1. The authors have described their result in their response, but my main concern was about the dependence of the term $\\max_i s_i$ on $k$ (i.e., the magnitude of the additive loss for finite $k$). Also, a precise description of the results in the case of incorrect predictions is required as well. I will keep my initial score for the paper. \n\n----Final Update-----\n\nAfter discussing the raised questions with the authors, my concerns were resolved. I will increase my score to 6 for this paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a theoretical work without any potential ethical concerns. The authors have perfectly described the scope of their proposed algorithm and its limitations.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2-3 hours"}, "extra_text": {}}, {"review_id": "bISMqgj9fyd", "reviewer": "Reviewer_et4L", "summary": "This paper revisits the online knapsack problem using machine-learned predictions in order to improve on prior the competitive ratio of classical algorithms. The authors take a different approach compared to other works in the area of learning-augmented online algorithms. Specifically, instead of having the prediction be a specific value predicting the true value of some parameter, they use intervals to indicate a range of values in which each parameter is predicted to be in. In this case, the parameters predicted are the frequencies of elements of some specific value that will arrive in the future. In the analysis, the authors compute the competitive ratio of their algorithm given that all the predictions are accurate in the sense that the true parameters indeed fall into their corresponding intervals.  The authors show that the competitive ratio of their proposed algorithm is instance optimal with regard to the predictions given and that the competitive ratio improves as the predicted intervals become shorter and match the performance of the algorithm by Zhou et’al when the intervals equal the entire domain.  The predictions are used by the algorithm to prevent too many low-valued elements being selected, while higher valued elements are predicted to arrive later. The choice of this approach is supported by a hardness result simpler threshold based algorithms cannot achieve an arbitrarily good competitive ratio. Also, an application to one-way trading is shown via a reduction to the online knapsack problem and two-stage knapsack variant, in which the algorithm can select elements in a second round (with some penalty on their value), is discussed. Finally, experimental results show the improved performance of the proposed algorithm compared to the algorithm by  Zhou et’al that does not use predictions\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I believe that this paper suggests a very interesting approach for the analysis of learning augmented algorithms by introducing the predictions as an interval. This could fit very well in practice with the idea of machine learning algorithms providing confidence intervals for their predictions. One might need to be careful though, since the error from different confidence intervals could accumulate. It is conceivable that this approach could lead in new results for different problems in the area. Finally, the paper is quite well written and easy to follow.  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors as well as myself do not see any potential negative societal impact from this work.\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "832o2tzA1s", "reviewer": "Reviewer_PbZr", "summary": "The paper studies the online Knapsack problem in the new framework of Learning Augmented algorithms. In this setting the goal is to use predictions to improve the performance of online algorithms. Generally, two properties are wanted: (1) robustness which is a worst case bound of the competitive ratio of the algorithm (even if the predictions are totally incorrect) (2) consistency which is the guarantee that if the prediction are correct then the algorithm should be better than what any online algorithm can do. As noted by the authors in introduction, robustness here is trivial hence the focus of the paper is to obtain the consistency property. Interestingly, they can use rather weak predictions and still manage to obtain an improved bound over what online algorithms can do (more details below). \n\n\nThe formal definition of the problem is the following. We have a knapsack of unit capacity and n items are revealed in an online fashion. Each item $i$ has a profit $p_i$ and a size $s_i$ (the value of an item is defined as $v_i=p_i/s_i$). The goal is to maximize the profit without exceeding the capacity of the knapsack.  Once an item arrives, the algorithm has to decide whether to take it or leave it.\n\n\nIn the online setting without prediction, an algorithm with competitive ratio of $1/(1+ln(v_{max}/v_{min}))$ is known (if items have infinitely small size) where $v_{max}$ is the max value and $v_{min}$ the min value. It is also known that it is not possible to do better. This result is due to Zhou, Chakrabarty, and Lukose [ZCL08].\n\n\nThe prediction model is the following. Before receiving the instance, the algorithm is given a lower bound $l(v)$ on the total size of items of value $v$ for all $v$. Similarly, an upper bound $u(v)$ on the total size of items of value $v$ is given. These are called frequency predictions. The main result of the author is to obtain an algorithm that is optimal on instances for which the true total volume $s(v)$ of items of size $v$ is in-between the lower bound and the upper bound (i.e. $l(v)\\leq s(v)\\leq u(v)$ for all $v$), that is, if the frequency predictions are correct. Precisely they design an algorithm that is $\\alpha$-competitive where $\\alpha$ is the best competitive ratio on all instances for which the frequency predictions $l,u$ are correct.\nThere is no closed form of the value of $\\alpha$ which depends in general on the predictions $l$ and $u$ in some non-trivial way. However they demonstrate that for reasonable predictions, the value of $\\alpha$ is much better that what the ZCL algorithm can guarantee.  \n\n\nThe authors also generalize their results to more general problems such as generalized one-way trading and two-stage online knapsack. Finally, they also demonstrate that their algorithm for online Knapsack outperforms ZCL in practice.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality/Quality: I believe the results are non-trivial and very interesting. In particular, an interesting challenge in this problem (that the authors mention) is that simply applying the technique of ZCL with a “threshold algorithm” cannot work in the learning augmented setting. This means that from a technical point of view, new ideas were needed for this problem. \n\nClarity: I find the paper clearly written and I believe in the correctness of the results of the paper although I did not check the appendix entirely.\n\nSignificance: This paper gives interesting results on a clean and natural problem.\n\nI don’t see any major weakness in this work however I have a few questions/comments for the authors:\n\n(1) In other learning augmented algorithms, there is also a concept of “smoothness” that says that if the prediction is slightly incorrect then the performance of the algorithm does not degrade a lot. Here I understand the prediction is rather weak so you already have some kind of smoothness but what happens if you realize that some frequency prediction is in fact slightly incorrect? Can you still maintain a better guarantee that online algorithms without predictions?\n\n(2) I believe that if the lower bound is equal to the upper bound (i.e. $l(v)=u(v)$ for all $v$) then $\\alpha^*=1$. Is this true? If yes, then I would suggest to include a brief explanation of this as I don’t think it is immediately clear from the description of the algorithm.\n\nTypos:\n\nLine 110 : outperform -> outperforms\n\nLine 170 : smallest -> largest ?\n\nLine 176 : a profit of at $\\alpha$… -> a profit of at least $\\alpha$…\n\n\n==== UPDATE ==== after reading the author response and discussing with other reviewers, my initial opinion remains: the result and techniques are interesting. I think this is a nice paper. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers all find the results in this paper to be technically strong and interesting. This paper makes a nice contribution to the area of algorithms with ML predictions. Please address reviewer YbwL's comments regarding the additive loss and the description of the results in the case of incorrect predictions in the final version.
Decision: Accept (Poster)