Advice Querying under Budget Constraint for Online Algorithms
Authors: Ziyad Benomar
Vianney Perchet
Venue: NeurIPS 2023 poster (2023)
Keywords: online algorithms
competitive ratio
learning augmented algorithms
scheduling
ski-rental
secretary

Abstract: Several problems have been extensively studied in the learning-augmented setting, where the algorithm has access to some, possibly incorrect, predictions. However, it is assumed in most works that the predictions are provided to the algorithm as input, with no constraint on their size. In this paper, we consider algorithms with access to a limited number of predictions, that they can request at any time during their execution. We study three classical problems in competitive analysis, the ski rental problem, the secretary problem, and the non-clairvoyant job scheduling. We address the question of when to query predictions and how to use them.

Advice Querying under Budget Constraint for Online Algorithms
Ziyad Benomar CREST, ENSAE, Ecole polytechique ziyad. benomar@ensee
Vianney Perchet
CREST, ENSAE and Criteo Al LAB vianney- peru org
Abstract
Several problems have been extensively studied in the where the algorithm has access to some, possibly incorrect, predictions. However, it is assumed in most works that the predictions are provided the algorithm as input, with no constraint on their size. In this paper, we consider algorithms with access a limited number of predictions, that they can request any time during their execution. We study three classical problems in competitive analysis, the ski rental problem, the secretary problem, and the non-clairvoyant job scheduling. We address the question of when to query predictions and how to use them.
setting,
Introduction
With the rise of data science and the huge emphasis on research in machine learning and artificial intelligence, powerful predictive tools have emerged. This gave birth learning-augnen augmentted algo- rithms, which use these predictions to go beyond the standard long-standing worst-case limitations. The design of such algorithms requires establishing good tradeoffs between consistency and robust- ness, i.e. having improved performance when the predictions are accurate, and not behaving poorly compared to the case without predictions if they are erroneous. This was formalized by Lykouris and Vassilvitskii [41] for the caching problem, and Purohit et al. [47] for the ski-rental and scheduling problems. Since then, the Baaming--augentin setting had many applications in implementing data
structures (36 2
39] and in the design of algorithms 15 7
30 [5] 10 40)
Several questions and research directions have been explored, such as exhibiting optimal robustness- consistency tradeoffs [48], incorporating predictions from multiple experts
3
19,, or customizing
learning approaches to make predictions for such algorithms 49 21 I8
34
2 In most papers,
those predictions are assumed to be given as inputs, which is unfortunately not realistic, practical or applicable to real-life scenarios. Indeed, many problems such as scheduling, paging, or set cover, require some arbitrarily large number of predictions (roughly speaking one request or job). We claim that, on the contrary, algorithms might have only access to a finite budget of predictions as each one of them is costly to compute. Therefore, the main question rather becomes deciding how and when to spend the assigned budget, by requesting new predictions. Such a setting was considered for example in (31 for the caching problem. Moreover, it also happens that the quality of the predictions improves with time, as more data are collected, more knowledge of the problem is gathered, or delaying the computation of prediction allows allocate more computational power to them, hence enhancing their precision, for instance with more powerful forecasting models. The question of planning the prediction requests thus quite erucial.
The problems we mentioned fall into the category of online algorithms, operating under uncertainty, and gaining more information about the input of the problem through time, eventually depending their past decisions. The performance of such algorithms is measured by their competitive ratio [14), which is the worst-case ratio between their output and that of the optimal offline algorithm, having full knowledge of the inputs and parameters of the problem. To illustrate our claims, we shall focus
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

on three well-established and fundamental problems in competitive analysis: ski rental, secretary, and job scheduling problems.
Ski-rental In the ski-rental problem, the decision maker faces each day the choice of either renting a ski for a unit cost, or buying it at a cost of and skiing for free after that. The only decision to be made by the algorithm is therefore when buy. The unknown parameter is the length of the ski season, and the objective is to minimize the total cost of renting and buying. The optimal offline algorithm has a cost min 6). the deterministic online break-even algorithm. which consists in renting for the first b 1 days and then buying. results in a competitive ratio of [32), and the optimal randomized algorithm introduced by Karlin et al. [33 yields a competitive ratio of c-
Secretary problem The second problem we study is the secretary problem. Consider having N applicants observed sequentially in a uniformly random order. Immediately after a candidate is observed, the algorithm has to either select them and stop, or refuse them irrevocably. The objective is maximize the probability of selecting the best applicant overall. The partieularity of this problem is that a single incorrect decision at any point leads to failure and zero gain. Consequently, the cost of making wrong decision significantly high. The optimal offline algorithm has access to all values and thus can choose the maximum with probability 1. The optimal online strategy is to reject the first N/e applicants, then stop at the first applicant who is better than all of them [17 25 This is often
referred to as the 1/ce rule, and it gives a success probability of 1// e x 0.368.
Job scheduling The third problem we consider is the preemptive non-clairvoyant job scheduling. The imput is set of jobs with unknown sizes, that the algorithm needs to schedule on single machine, with the possibility of halting a job during its execution and resuming it later. The goal is to minimize the sum of their completion times, i.e. finish many jobs possible rapidly. The only observations made during the run of an algorithm are the completion times of the jobs. These observations, along with the times at which they are received, depend both the input instance and the algorithm's 's past decisions. The cost of early incorrect decisions is more significant than that of later incorrect decisions. Take for example the instance of job sizes {z) = 1, 22 1003, running 1 then 22 gives an output 1 + 101 = 102, while running them in the inverse order gives 100 + 101 = 201. The optimal offline algorithm and a deterministic online algorithm called round-robil gives a competitive ratio of 2, which is optimal for an arbitrarily large number of jobs 46).
schedule the jobs in increasing order of size,
1.1 Organization and contributions
In Section we consider the ski rental problem, where we assume that an oracle provides binary predictions on how the snow season length x compares to the purchasing cost b, and that these predictions are accurate with a probability that is a function of time, known to the algorithm and denoted as pt. This assumption accurately reflects and models what is practically occurring. As the snow season begins, there is significant uncertainty about how long it will last. However, over time, the accuracy of predictions increases as more weather observations are made, the direction of snowstorms becomes clearer, and additional data is collected. The algorithm is permitted to request only one prediction during its execution, at time of its choice. Depending on the function and on how the prediction is used once queried, it can be more advantageous to rent for period of time before requesting it, i.e. paying a cost for making a better decision in the future. We consider that once the prediction is queried, we use either the deterministic or the randomized algorithm presented in 47 for the ski rental problem. We show how to optimally choose I, and how the knowledge of pt allows to tune the parameter X, regulating the levels of consistency and robustness in both algorithms.
Secondly, we consider in Section 3 the secretary problem with access to an oracle, accurate with a probability p. telling if there are better applicants in the future. In practice, this would correspond to the following scenario: consider decision- maker with an imperfect interviewing process, and thus can only compare the applicants with each other, i.e. observe their relative ranks, but lacks access to their true value. On the other hand, an expert who, due to extensive experience, knows how to better interview the applicants and extract their true value, and also knows the distribution of their values (as in prophet setting with i.i.d variables). The decision-maker can ask the expert to interview some applicants for a cost. After that, the expert does not disclose the precise value of the applicant that is irrelevant to the decision maker-, but they provide recommendation (accept reject) and
2

---

accompany it with a confidence level, which is the probability that this recommendation is accurate. Assuming that the pecision-makee has enough budget ask for the expert's 's advice B times, we give an algorithm whose success probability depends on p and B, converges to as p goes to and B grows, and that is always lower bounded by 1/e. Our algorithm easily adapts to the case where the accuracy of the oracle is time-dependent.
Section 4 is dedicated to the preemptive non-clairvoyant job scheduling, where we assume that the algorithm can request access to the sizes of B chosen jobs. In contrast with the two previous problems, there is no advantage in waiting before querying the hints, and since the jobs play identical roles, the algorithm can only request the sizes of B randomly chosen ones. We show first that the competitive ratio cannot be improved unless B (2 where N is the number of jobs. Then we present an algorithm that chooses randomly B jobs and requests their sizes, then runs concurrently the optimal offline algorithms on those jobs and round-robin on the others, with imeedependent processing rates. We prove generic expression for the output of this algorithm that depends on the chosen processing rate, and then we give particular processing rate that yields a competitive ratio of 2 - (B/N)², therefore interpolating the competitive ratios 2 and met respectively when no hint is given, and when all the job sizes are known.
Finally, we run simulations of our algorithms in Section 5 We show that the performance of the algorithm we introduced for the secretary problem matches our theoretical lower bound, and we compare it to another heuristic version that we did not study theoretically. Then, by exhaustively testing the algorithm we designed for the scheduling problem with access B job sizes on various benchmark instances, we observe that it has better performance in practice than the theoretical upper bound 2 (B/N)?.
1.2 Related work
The ski-rental and scheduling problems have received extensive attention in the realm of learning- augmented algorithms [47 48 3
19
18
37
9]. They serve respectively as notable examples for
problems requiring single prediction and multiple predictions. Moreover, they both have numerous applications and variants, as [3] 12
24
44] for the ski rental and [42] 16 (38 for the scheduling
problem. The secretary problem was also among the first problems studied with the advice model. Dütting et al. [22] consider that a binary prediction is received with each applicant, indicating whether it is the best overall or not. Assuming that these predictions independently, they design algorithms that improve upon the 1/c success probability. While this model closely aligns with ours, consider scenario where the algorithm has limited budget of predictions and must carefully determine when to query them. Antoniadis et al. [7] studied a variant of the problem where the objective is to maximize the value of the selected applicant. They consider that the algorithm is provided with a prediction of the value of the best applicant.
accurate each with a probability p
For both the ski-rental and the secretary problems, consider predictions that are accurate with known probability. A similar assumption was made in (28), where the oracle is assumed to deliver a prediction that is accurate with probability of at least e, and that can be arbitrarily inaccurate with the remaining probability. The authors give improved competitive ratios depending on e for some online problems including caching, online set cover, and facility location.
The aspect of having limited prediction budget is relatively underexplored in the literature. The question was initially examined in the context of the online linear optimization problem with hints, where Bhaskara et al. [I] demonstrated that a sublinear number of hints sufficient to achieve regret bounds similar to those in the full hints setting when the timing of requesting hints is well chosen. Im et al. [31] also investigated this question for the caching problem, presenting an algorithm that strategically utilizes the assigned prediction budget to improve the competitive ratio the budget increases. In a very recent paper, the ski-rental and the Bahncard problems were explored in setting with costly predictions [20]. where the cost of predictions is added to the total cost paid by the algorithm. This can be seen as a penalized version of querying predictions under budget constraints. Other works have also investigated the reduction of the prediction size rather than the number of predictions. Specifically, they consider binary predictions encoded on a single bit and explore how the competitive ratio can be enhanced compared other types of predictions (22 45 g
Another important question we cover thanks to the ski-rental problem is how to optimally balance robustness consistency with respect to predictions [47]. This tradeoff is usually done by adding
3

---

some extra- parameter À E [o, 1] that reflects how much the decision- maker is willing to trust blindly the prediction, and which appears naturally in the bounds of the competitive ratio. Roughly speaking, for À = 1, the decision maker focuses solely on the performances of their algorithms when predictions are incorrect (hence predictions are actually disregarded), while for O, they naively consider that predictions are correct. Intermediate values of À correspond to less extreme behaviors, and the final competitive ratio strongly depends on the value of this parameter and the total "amount" of errors (measured with respect to some problem--ependent metric) in predictions. Setting value for this parameter requires having some knowledge about the quality of the prediction. Khodak et al. [34] shows how to learn to set X's value in an online learning setting, where the algorithm runs repeatedly on different instances, and learns to predict unknown parameters based on features on the new instances. After many runs, the value of À can be increased since the predictions become more and more accurate. In our case, we have binary predictions that are correct with a known probability, and we show that this allows to
which is natural assumption for binary predictions 45 22 optimally choose the value of X.
2 Ski-rental with time-dependent guarantees on the prediction
We consider that the cost of renting ski for one day is while the cost of buying is b > 1, and we denote x the duration of the ski season, which is unknown. For all the algorithms we present, if the ski season is over then the algorithm stops and further cost is paid. In the carming-auggenete setting, we assume that the algorithm possesses a prediction for x. Many variants of this scenario have also been explored in previous research papers [47 35 27 48 We restrain ourselves to the case of binary predictions, comparing the number of snow days to the budget. More precisely, we assume the existence of oracle, that can be called at any time l, predicting whether x ( > or not, where - f is the number of remaining snow days. Furthermore, we assume that the accuracy of the oracle improves over time. If queried at time f, then the prediction is correct with a probability Pt, known to the algorithm, that is independent of the problem's 's history and increases over time. We assume that, due to budget limitations, the algorithm can access the oracle only once during its execution, and thus it must carefully choose the time of asking for the prediction.
Let ALG be an algorithm such that, with prediction accurate with probability p. it has a competitive ratio C C(ALG.p). p). We define the algorithm ALG, that rents for the first & days, then queries a prediction Q. of 1(x & 2 b) the start of day ++1 1, and then acts like ALG. We have the following result.
Lemma 2.1. ALG, has competitive ratio of at most + C(ALG,
The term t/b represents the additional cost due to renting the first & days, in order have better accuracy Pt which decreases the second term. The optimal time for querying a prediction is t* minimizing the function t/b+ + C(ALG, Pt). Although this requires knowing all the sequence (p:) in advance, we can design simple online heuristics for being close to a local minimum, where the accuracy of the oracle some step is only revealed when that step is reached. We can for example access the oracle at the first time f when t/b + C(ALG, Pt) increases.
In the following, given a binary prediction as input. We consider the algorithms [ [ which were first introduced in [47]. In both algorithms, the parameter À indicates how much the prediction is trusted. Assuming that the input prediction is accurate with probability p P(o 1(xx 2 b)), we show how to tune A in both algorithms to minimize their costs, and we upper bound their competitive ratios.
show how Lemma 2.1 can be applied with explicit algorithms ALG that
Algorithm 1: Deterministic algorithm with input binary prediction [47]
Input: cost b for buying, a prediction Q for 1( 2 b)
if Q = 1 then buy on the start of day [bb]; 2 else buy on the start of day [b/A]:
Lemma 2.2. If the oracle Q delivers accurate prediction with probability p 2 0.5, then by choosing x - / --", the algorithm achieves a competitive ratio of at most + 222p(11 -p(1-)). p).
The optimal choice of X gives therefore a competitive ratio that is always upper bounded by 2, which is the optimal competitive ratio without prediction, and decreases to I when the accuracy of the oracle

---

Theoretical upper bound for the vatio
theoretical upper bound
2.4
Determivdic (0=50)
c
1.6
1.4
1.4-
1.2-
Kasiemical (bws]
betemniiitt:
Santemited (0-20)
1.5
1.0
Kaniemizal
35
3.6
0.7
0.8
100
30
22
30
50
Accuracy sracle
time qug.gagggggggggg................ cwd.icictoooodooooooo crodictioon
Figure I: Competitive ratios of Algorithms and 2 with the optimal choice of X, for p (0.5, 1) and b 5, 10, 100
Figure 2: Competive ratio obtained by renting days before querying prediction, with pt 0.95 0.4 eexp-1//5) and 50, 100
is better. While Algorithm is deterministic, the next algorithm we study is randomized, where the day of buying random variable, drawn from a probability distribution that depends on the prediction Q. We show again optimal choice of À for minimizing the competitive ratio.
Algorithm 2:
Randomized algorithm with input binary prediction 47
Input: cost & for buying, a prediction Q for 1(x 2 b) if Q = 1 then buy on the start of day d {l..... [A6]], with probability x (1- 1/b)[Ab) -d;
else buy on the start of day d E {I,..., [b/A]], with probability (1 (1-1/b)[b/A1-
Lemma 2.3. If the oracle Q delivers accurate prediction with probability p 2 0.5, then with = min 1,1/b + Vle - 1)(1/p-)))) - 1)} Algorithm 2 has competitive ratio of at most
+ 2 pll-pi e-1
+ (1- (1-
1-1 p if 2 (1+ --1/11 -1 e-
otherwise.
Figure shows the competitive ratios of both algorithms depending on p when À is chosen optimally. The upper bound shown in Lemma 2.3 de3eedsss on h, this is why we test with different values of As expected, the randomized algorithm yields better guarantees than the deterministic one. However, when p is very close to 1, Algorithm iis slightly better, because the randomized algorithm requires having À 2 1/b, and therefore in the limit where p = the optimal choice is 1/b, giving the upper bound + 1/6 instead of on the competitive ratio.
Now, assuming that the oracle is accurate with known time-dependent probability pt, the previous lemmas allow to optimally choose the time of querying the prediction when one of the two algorithms presented is used after the prediction is obtained. We only state the result for the where Algorithm Dis is used. The proof is immediate using Lemmas 2. and [ and a similar result can be shown using Lemmas 2.1 and 2.3 when Algorithm is used instead.
Theorem 2.4. the predictions delivered by the oracle are accurate with a probability Pt that only depends on the time, then renting until time t, then querying prediction Q, and running Algorithm
1 with parameter X
V1
1-pt yields competitive ratio of at most + t/b b + 2 Pc(1 11 pt).
We consider in Figure limt- Pt = 0.95. The figure shows the competitive ratio renting days then using one of the Algorithms | or 2 with 50, 100. We observe that this strategy can significantly improve the competitive ratio if is chosen correctly. Of course, this depends strongly on Pt and b. In particular, for the randomized algorithm, it better to query the prediction at 0 when b 50.
example where p: 0.95 0.4 ex4 thus Po 0.55 and
3 Secretary problem with B predictions
Assume that N applicants are observed sequentially in uniformly random order (#1, ., xx ), all having distinct values. After applicant is interviewed, the Decision-maker has to either accept them
5

---

and halt the process, or refuse them irrevocably. We consider a setting where, when an applicant Fy is observed, and the budget is still not exhausted, the algorithm can request binary prediction ((xx) indicating if there are better applicants coming in the future. We assume maximal budget of predictions, where B a constant independent of N. We assume first that the predictions are error-free, and we give theoretical guarantees on Algorithm in that case, and after that, we show how can be adapted to handle predictions that are accurate only with a probability p. In this section, we say that an algorithm succeeded if the selected applicant is the best overall.
We consider first Algorithm 3 which rejects the first [rg.V] applicants, where 7B E (0, is a threshold depending on B. and then queries a prediction for the first applicant zy better than all of them. If the oracle predicts that there is a better candidate in the future (Q(z)) then the algorithm is restarted with the inputs (I.+1....,,NN and budget B -.
Algorithm 3: ADATHRESH Adaptive Threshold
Input: Budget B, sequence of applicants (I1,..., 2N)
Reject the first [rgN]] applicants;
for t [r + I, ,,....NN N do
if' [1 >> max [1,. Ix-1} then if > 0 then query prediction Q(x²); if (xx,) then Return: t; else Return ADATURESH(( - 1,, else Return: t;
Theorem 3.1. Let (2-)) the sequences defined by q-1 = =0 and for B 2 0
yB = 98-11 + (1 11 exp
(- 1--9--1)
1
exp
98-1
If the oracle Q delivers error-free predictions, then with the thresholds (FB) ADATHRESH with budget B has a success probability of at least QB independently of the input size N.
Observe that, as B increases, the lower bound (B of the success probability of ADATHRESH converges and the thresholds rg converge to zero, meaning that the higher the budget, the higher the risks: there are fewer applicants in the first observation phase, thus the probability of selecting future sub-optimal one is higher (yet this risk is hedged by the predictions), but on the other hand, reduces the probability of naïvely disregarding the best applicant if it is among the first arriving ones. Although ADATHRESH is naive algorithm that does not make full use of past information, we showed that adequately choosing the thresholds
(rB) B guarantees success probability that goes to 1 as the budget increases. We present in Appendix [B.3|an improved version ADATHRESE that keeps in memory the maximum value M observed far and that rejects all applicants having values below M. We show numerically in Section how this increases the success probability of the algorithm.
Handling imperfect predictions If the predictions of the oracle are imperfect, then one way of guaranteeing robustness, since the objective is maximize the success probability, is use the 1/e- rule with probability À and Algorithm with probability 1 - A. This guarantees success probability of at least A/e if the predictions are incorrect. On the other hand, given that the oracle's 's predictions are binary, it reasonable assume that each prediction is correct with probability independent of all the observations, as explained in the introduction. Based on this assumption, Algorithm can be modified to include the option of trusting or disregarding the oracle's 's trust
2-333
13335
prediction at each step. We show that is advantageous the oracle when is above certain threshold and run the 1/c-rule otherwise. This algorithm achieves a success probability of at least 1/e, with improving performance as p approaches 1. We show in the appendix how this can generalized when the accuracy of the oracle is time-dependent.
Figure 3: (p)) for p E
[0.5, 1] and B < 20

---

Theorem 3.2. Assume that each oracle's prediction is independently correct with probability p 2 (e exxp(=--1 0.73, then there is an algorithm that achieves a success probability of at least qu(p) e/ B = 0, and (B(P) for B 2 1 defined as
(p)p) = p9n- + p(1 (p)1(p)) exp (-I-1E-10)
If we denote W. the Lambert function, ie. the inverse of + wee on 00), then we have
1
lim B-000
(p())
1+ W (((-p))
Moreover, the algorithm has success probability of at least 1/e for any value of E [1/2, 1].
Optimal algorithm Assuming that the predictions are error-free, the problem is equivalent to the multiple-choice secretary problem (26), where the algorithm is allowed to select k > 1 applicants, and it successful if the best overall candidate among them. Indeed, the algorithm is given B + attempts to identify the best applicant, and it halts if it finds it. This is analogous to choosing = B + 1 applicants, where following the selection of each one, the algorithm employs selection strategy as if the previous guesses were unsuccessful. The optimal algorithm for selecting &: applicants is a (ax..... a1) )-ulle [26 43,, where at any step L, if the number of applicants already selected is i E {0.............. (O....,ki k., then reject everyone until step min (t. ax-i). and accept the first applicant after that is the best observed so far. Although this family of algorithms has a simple structure, analyzing is difficult and hides many technical challenges. The optimal thresholds and the asymptotic success probability are explicitly computed only up to k S 5, and a recursive formula is proven, via a dynamic programming approach, compute the next thresholds. This formula is however difficult exploit even numerically, while the optimal thresholds and the success probability of ADAT'RRESH can be computed very easily.
the predictions are correct with a probability p. then the optimal algorithm must be a generalization of the (aa..... a1) )-rule, and thus it is even harder to analyze. The algorithm we proposed is naive in the sense that it does not take into account all the past information and only remembers the history since the last prediction was queried. However, it illustrates how the limited budget of predictions should be spent, and it presents good robustness and consistency guarantees with respect to p and B, in the sense that it always has success probability of at least 1/e, which is optimal without predictions, and it has a success probability that converges to as B and p increase.
Preemptive B-clairvoyant job scheduling
We consider the problem of scheduling multiple jobs on single machine, with the objective of minimizing the sum of their completion times. More particularly, we place ourselves in the preemptive setting, where the jobs can be temporarily halted and resumed later, equivalently that they can be run in parallel with rates that sum at most to 1. Let N be the number of jobs and Tı,... NN their sizes. If the algorithm knows beforehand the sizes of the jobs, it called clairvoyant, and the optimal algorithm OPT is to run the shortest jobs first. An algorithm is non-clairvoyar if the size I, of any job j is unknown until the job is completed. Motwani et al. [46] showed that no deterministic or randomized algorithm can have a better competitive ratio than 2, which is achieved by round-robh robin (RR), which a deterministic algorithm. RR works as follows: at any time t, if is the number of remaining jobs, then RR runs them all in parallel with rates 1 1/n. each.
An in-between setting, surprisingly not explored yet, is when the algorithm has only access to the sizes of a limited number of jobs. We say that an algorithm is B-clairvoyant when it is allowed to access the sizes of B jobs. We assume that it can query their true sizes, and not just noisy predictions. We start with a negative result, stating that we need to have B ?(NN to achieve a better competitive ratio than 2. Then, we give an algorithm with competitive ratio of at most 2 (B/N)².
Let us first remind a few classic notations in the scheduling problem. For any algorithm ALG, and any instance J = {II...., ,,
.......,N] ) the sum of the completion times obtained by ALG can be written as
ALG(J)
Σ r +
(L, DALG
(I)
i=1
i
7

---

where (i. () is the delay caused by job i to job j. i.e. the amount of job executed before the complction of job j. With this notation, we have for any i < j that D (i.j] + DOPT(j.
min(a;, mJ and (i,() DR
min xz}. Thus, if α S S UN we obtain
N
N (N -
N
OPT(J) = E
+
-)
RR(J) = Σ
T2 +
(N i)x4.
(2)
1=1
4.1 Few hints are not enough
In opposite to other problems where it has been proved that a sublinear number of hints is enough
for improving the performance [3] 3T,, the following theorem demonstrates that, for the scheduling problem, no algorithm can achieve competitive ratio better than 2 when B = o(N).
Theorem 4.1. Any B-clairvoyant deterministic random algorithm with B o(N), has competi- tive ratio lower bounded by 2.
4.2 Parallel OPT-RR algorithm with adaptive processing rates
We assume in this section that the B = (NN). A first naive algorithm would run RR until there are B jobs left, then query their sizes, and use OPT to finish. However, when all the jobs have the same size, they terminate at the same time and no hint is queried. The output of the algorithm with this instance is exactly the same as RR, which is twice the output of OPT asymptotically in N [46], and therefore its competitive ratio is at least 2. More generally, any algorithm that runs RR waiting for a certain number of jobs finish before querying the sizes of / unfinished ones is no better than RR for the same reasons. Alternatively, the algorithm can wait for a possibly random amount of time T > O, independent of the observed completion times, before querying the first hint. However, by taking job sizes sampled from an exponential distribution with parameter such that their sum is smaller than with an arbitrarily high probability, the algorithm terminates with high probability before requesting any hint and is no better than non-clairvoyant algorithm on such input instances, leading to a competitive ratio of least Therefore, the best moment to query the hints is at the very beginning of the execution, and since the algorithm cannot differentiate between the jobs, it can only query the sizes of B randomly chosen ones.
We propose a generic algorithm that queries the sizes of B randomly chosen jobs, then concurrently runs OPT on them and RR on the others with respective rates a and a, where a parameter that can be adjusted throughout the course of the algorithm, depending on the information available at each time, i.e the predicted job sizes, the number the remaining jobs, and the sizes of finished jobs.
Algorithm 4: PAR Parallel algorithm with Adaptive processing Rate
Input: Budget B, N jobs with unknown sizes (21.-..,22,
1 + Sample B jobs uniformly at random without replacement;
J < {1, .1.....Ny. II;
3 while there are still unfinished jobs do
Adjust a;
run for a time unit
with rate a: OPT (., her
with rate - a: RR on {z, bey:
In the following, for any algorithm ALG and for any subsets H1 K of {1...., N}, we denote DALG (H, K) = Ete ΣjEK(o) (i, the sum of all the delays caused by jobs in H to those in K. We demonstrate first generic upper bound for the output of PAR,
Lemma 4.2. For any update rule of have
N
N i)., + PAR P (I.J) + PAR (J, (J, 7)]-
E ([PA((()) = Σ x,
Σ (N
This Lemma shows that the output of PAR depends only on the delays generated by jobs in / on jobs in J and vice versa. The difficulty now is choose an adequate update rule for the rate a, with provable upper bounds on (AR (1, J)+ + (PR (J,
8

---

1
3
3
4
4
5
5
5
5
Figure 4: In this example, N = 5, the job sizes are {a1 = 1,42 = 23 = 4, 24 5, 233 = 6.3). and / = 2.).. On the left visualize of RR this instance, and the right of PAR with the SRR update rule. The X-axis represents time and the Y-axis represents the processing power allocated to each job.
4.3 Simulated round-robin update rule
We consider the Simulated Round-Rober (SRR) update rule, which adjusts a as follows. It simply puts global processing rate on 4, the of unfinished jobs in proportional to the cardinal of IAR, the number of unfinished jobs in / had RR be run instead (this counterfactual quantity can be computed at any time step predictions are correct, see proof of Theorem 4.3) and similarly for J. Formally, af AR R / /(/AR + (J Figure 4 gives an illustration of the SRR update rule: to the left, shows run of RR. where initially the jobs run each with processing rate 1/5 until job terminates, then the remaining jobs run each with processing rate of 1/4 until job 2 terminates, and so on. To the right, the figure shows rum of PAR with SRR update rule, where the algorithm knows the sizes of jobs 1,2 and 3. The total processing rate of these jobs during the run of the algorithm is represented by the yellow area, and identical their total processing rate during the run of RR.
Theorem 4.3. If PAR uses a processing rate AR then is most (2
B B(B-1) N
competitive.
The competitive ratio of PAR with processing rate (a (a(R))ss )=20 decreases B grows, going from 2 to thus interpolating the non-clairvoyant and the clairvoyant settings.
5 Experiments
In this section, we test the performance of the algorithms we presented for the ski-rental, secretary, and scheduling problems, supporting our theoretical results and giving further insight.
2,2
DET
Query then
RAND
MAND
1.5
1.7
12
0.5
6.7
0.5
1.2
20
scourncy of oruiee
Bime 212 curryting the iredictioon
Figure Competitive ratios of Algorithms and 2 with oracle Q accurate with probability p E [0.5,1 and b 50.
Figure Competitive ratio querying the pre- diction at time f, then running Algorithm T or 2
with = 0.95 0.4 0.4 exp( -t/5) and b 100.
For the ski-rental problem, we set buying cost of = 50 for Figure 5 and = 100 for Figure and the number of snow days is sampled randomly from uniform distribution in [1, 4b). Each point in both figures computed over 10" simulations. The value is chosen optimally with respect to
indicated in Lemmas 2.2 and 2.3
The competitive ratios of both algorithms D and [and[[ when the prediction is given as input are shown in Figure 5 as well as their theoretical upper bounds. The experimental ratio of the deterministic

---

algorithm in this particular scenario is significantly better than the theoretical upper bound, while that of the randomized algorithm is close the theoretical upper bound. In Figure 6 we consider that the oracle is correct with time-dependent probability p: 0.95 0.4 exp(-175) (1/5). We show the competitive ratios obtained by renting until time then querying a prediction and running the deterministic or the randomized algorithm. The theoretical upper bounds are represented in dotted lines. We observe that adequately choosing the time of querying the prediction can significantly improve the competitive ratio, which proves our claims. This time strongly depends on the cost b and on the evolution the probability Pt. with time.
0.7-
-Paretr1.11
0.5
Adalhresh
lower to de
Adllhres with memory
1 numberat presiettnnn 0
Figure 7: Success probability of ADATHRESH compared to the lower bound QB. and compared to the case with memory.
Figure 8: Competitive ratio of PAR with SRR update rule, tested with N 50 and different benchmark input instances.
In Figure 7] we test ADATHRESH with N = 1000, and we show how the success probability improves with B. We also test variant of the algorithm memorizing the value of the best-observed applicant after restarting, which improves the success probability (See Appendix B.3 for a detailed description of the algorithm). The success probability of ADATHRESH matches ςB. therefore is a tight lower bound. We also observe that the success probability increases rapidly for the first values of B, but then becomes slower. This is because whenever the algorithm is restarted, there a new observation phase, with risk of missing the best applicant.
Secondly, we test the algorithm PAR with the SRR update rule various benchmark inputs. We test it with N = 50 and jobs having (i) identical sizes, (ii) sizes sampled from the exponential distribution, (iii) uniform distribution, (iv) and Pareto distribution. (i) critical instance because is the worst-case input for RR. (ii) is classical benchmark used in many variants of the scheduling problem to prove lower bounds [66.. (iii) is a natural benchmark to test randomness. Finally, (iv) is well-suited in practice for modeling the job size distributions [47] 22),, and also it shows how the algorithm behaves on instances with very high variance. Each point in the figure was obtained by averaging over 10000 runs. we see that the competitive ratio of PAR is at most 2 B/N for all these benchmarks, which is better than the upper bound 2 - (B/N)² proved in Theorem 4.3 Therefore, PAR can be highly efficient in many cases, since the gain obtained with B known job sizes proportional B as shown in the simulations.
Conclusion
We presented different settings where online algorithms operate under restricted budget of pre- dictions, that can be queried during their execution. We show that adequately using this budget significantly improves upon the worst-case performance. Our results pave the way for investigating paradigm, providing insights
more realistic and practical challenges within the that can be extended to various other problems in competitive analysis.
References
[1] Sara Ahmadian, Hossein Esfandiari, Vahab S Mirrokni, and Binghui Peng. Robust load balancing with machine learned advice. In SODA, pages 20-34, 2022.
[2] Keerti Anand, Rong Ge, and Debmalya Panigrahi. Customizing ml predictions for online algorithms. In International Conference Machine Learning, pages 303-313. PMLR, 2020.
10

---

[3] Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi. Online algorithms with multiple predictions. In International Conference on Machine Learning, pages 582-598. PMLR, 2022.
[4] Alexandr Andoni and Daniel Beaglehole. Learning to hash robustly, guaranteed. In International Conference on Muchine Learning, pages 599-618. PMLR, 2022.
[5] Spyros Angelopoulos, Christoph Düm, Shendan Jin, Shahin Kamali, and Mare Renault. Online computation with untrusted advice. arXiv preprint 1rXiv:I905. 05655, 2019.
[6] Antonios Antoniadis, Christian Coester, Marek Eliás, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. In Proceedings of the 37th Interna- tional Conference on Machine Learning, ICMI. 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 345-355. PMLR, 2020. URL http://prroceedings mlr. www.r.pressvviiv htt111////nnonniii20aaaa. html
[7] Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. Secretary and online matching problems with machine learned advice. Advances in Neural Information Processing Systems, 33:7933-7944, 2020.
[8] Antonios Antoniadis, Joan Boyar, Marek Eliáš, Lene M Favrholdt, Ruben Hoeksma, Kim S Larsen, Adam Polak, and Bertrand Simon. Paging with succinct predictions. arXiv preprint arX1v:2210.02775, 2022.
[9] Étienne Bamas, Andreas Maggiori, Lars Rohwedder, and Ola Svensson. Learning augmented energy minimization via speed scaling. Advances in Neural Information Processing Systems, 33:15350- 15359, 2020.
[10] Evripidis Bampis, Bruno Escoffier, and Michalis Xefteris. Canadian traveller problem with predictions. In Approximation and Online Algorithms: 20th International Workshop. WAOA 2022, Potsdam, Germany, September 8-9, 2022, Proceedings, pages 116-133, Springer, 2022.
[11] Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, and Erik Vee. Learning- augmented weighted paging. In Proceedings the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 67-89. SIAM, 2022.
[12] Yair Bartal, Stefano Leonardi, Alberto Marchetii-Spaceanedt Jiri Sgall, and Leen Stougie. Multiprocessor scheduling with rejection. SIAM Journal on Discrete Mathematics, 13(1):64-78, 2000.
[13] Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit. Logarithmic regret from sublinear hints. Advances in Neural Information Processing Systems, 34:28222-2888 28232, 2021.
[14] Allan Borodin and Ran El- Yaniv. Online computation and competitive analysis. cambridge university press, 2005.
[15] Justin Chen, Sandeep Silwal, Ali Vakilian, and Fred Zhang, Faster fundamental graph algorithms via learned predictions. In International Conference on Machine Learning, pages 3583-3602. PMLR, 2022.
[16] TCE Cheng and CCS Sin. A state-of-the-as review of parallel-machine scheduling research. European Journal of Operational Research, ((33)27712222 1990.
[17] Y.S. Chow, H.E. Robbins, H. Robbins, and D. Siegmund. Great Expectations: The Theory of Optimal Stopping. Houghton Mifflin, 1971. ISBN 9780395053140. https://tt boooss google google.fr/bobtee fr/books Pit.bboooeePddaaaEELeeyeVvVAC
[18] Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Ali Vakilian, and Nikos Zarifis. Learning online algorithms with distributional advice. In International Conference on Machine Learning, pages 2687-2696. PMLR, 2021.
[19] Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Algorithms with prediction portfolios. arXiv preprint arXiv:2210.124:.2 2022.
11

---

[20] Marina Drygala, Sai Ganesh Nagarajan, and Ola Svensson. Online algorithms with costly predictions. In International Conference on Artificial Intelligence and Statisties, pages 8078- 8101. PMLR, 2023.
[21] Elbert Du, Franklyn Wang, and Michael Mitzenmacher. Putting the "learning" into learning- augmented algorithms for frequency estimation. In International Conference on Machine Learning, pages 2860-2869. PMLR, 2021.
[22] Paul Dütting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii. Secretaries with ad- vice. In Proceedings of the 22nd ACM Conference Economics and Computation, EC '21, page 409-429, New York, NY. USA. 2021. Association for Computing Machinery. ISBN 9754455385 doi: 10.1 00.1145/44645563446666666 URL https://doi. heaeddi...ggg/// org/10...... 10.11 1145/ 3465456 3467623
[23] Paolo Ferragina, Fabrizio Lillo, and Giorgio Vinciguerra. On the performance of learned data structures. Theoretical Computer Science, 871:107-120, 2021.
[24] Rudolf Fleischer. On the bahncard problem. Theoretical Computer Science, 268(1):
2001.
[25] Martin Gardner. Mathematical games. Scientific american, 222(6):132-140)) 1970.
[26] John P. Gilbert and Frederick Mosteller. Recognizing the Maximum of Sequence, pages 355-398, Springer New York, New York, NY, 2006. ISBN 978-0-387-44956-2. doi: 10.1007/ 278-0-387-44956-2 2_.622222222222222222222 htthhtts:://do org/ 1007 3-7-88--------445---------------
[27] Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or-buy with expert advice. In International Conference on Machine Learning, pages 2319-2322 PMLR, 2019.
(28) Anupam Gupta, Debmalya Panigrahi, Bernardo Subercaseaux, and Kevin Sun. Augmenting online algorithms with c-accurate predictions. Advances in neural information processing systems, 2022.
[29] Mor Harchol-Balter and Allen B Downey. Exploiting process lifetime distributions for dynamic load balancing. ACM Transactions on Computer Systems (TOCS), 15(3):253-285, 1997.
[30] Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. On- line knapsack with frequency predictions. In Mare' Aurelio Ranzato, Alina Beygelz- imer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Ad- vances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 2733 2743, 2021. URL
httpo/cediiinnnnnuiip....... cc/ httpppssccpppp////pppppppp httpp/pppe/22//aaaaaeea 2021/hash/ Abt-:o0--bsttee Abstract. htmll html
[31] Sungjin Im, Ravi Kumar, Aditya Petety, and Manish Purohit. Parsimonious learning- learning-augmenttee augmented caching. In International Conference on Machine Learning, pages 9588-9601. PMLR, 2022.
[32] Anna Karlin, Mark S Manasse, Larry Rudolph, and Daniel D Sleator. Competitive snoopy caching. Algorithmica, 3:79-119, 1988.
[33] Anna R. Karlin, Mark S. Manasse, Lyle A. McGeoch, and Susan Owicki. Competitive random- ized algorithms for nonuniform problems. Algorithmica, 1166):542-571, 1994.
[34] Misha Khodak, Maria-Flonin FaorinFloriiaa F Balcan, Ameet Talwalkar, and Sergei Vassilvitskii. Learning predictions for algorithms with predictions. Advances in Neural Information Processing Systems, 11:3542-35555 2022.
[35] Rohan Kodialam. Optimal algorithms for ski rental with soft machine-learned predictions. arXiv preprint arXiv: 000920 2019.
[36] Tim Kraska, Alex Beutel, Ed H Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Proceedings of the 2018 international conference on management of data, pages 489-504, 2018.
12

---

[37] Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online schedul- ing via learned weights. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithmss, pages 1859-1877. SIAM, 2020.
[38] Jan Karel Lenstra and AHG Rinnooy Kan. Complexity of scheduling under precedence constraints. Operations Research, 26(1):22-33 1978.
[39] Honghao Lin, Tian Luo, and David Woodruff. Learning augmented binary search trees. In International Conference Machine Learning, pages 13431-13448 PMLR, 2022.
[40] Pinyan Lu, Xuandi Ren, Enze Sun, and Yubo Zhang. Generalized sorting with predictions. In Symposium on Simplicity in Algorithms (SOSA), pages 111-117. SIAM, 2021.
[41] Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM (JACM), 68(4):1-255 2021.
[42] Charles Martel. Preemptive scheduling with release times, deadlines, and due times. Journal of the ACM (JACM), 29(3):812 -19-899.128 1982.
[43] Tomomi Matsui and Katsunori Ano. Lower bounds for bruss' odds problem with multiple stoppings. Mathematics of Operations Research, 41(2):700 -144 2016.
[44] Adam Meyerson. The parking permit problem. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 05), pages 274-282. IEEE, 2005.
[45] Michael Mitzenmacher. Queues with small advice. In SIAM Conference on Applied and Computational Discrete Algorithms (ACDA2/), pages 1-12. SIAM, 2021.
[46] Rajeev Motwani, Steven Phillips, and Eric Torng Nonclairvoyant scheduling. Theoretical computer science, 130(1):17-47, 1994.
[47] Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML pre- dictions. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Sys- lems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 9684-9693, 2018.
[48] Alexander Wei and Fred Zhang. Optimal robustness-consiiteneg trade-offs for learning- augmented online algorithms. Advances Neural Information Processing Systems, 33:8042- 8053, 2020.
[49] Ali Zeynali, Bo Sun, Mohammad Hajiesmaili, and Adam Wierman. Data-driven competitive algorithms for online knapsack and set cover. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 10833-10841, 2021.
13

---

Advice Querying under Budget Constraint for Online Algorithms
Omitted proofs
A Ski-rental with time-dependent guarantees the prediction
A.1 Proof of Lemma 2.1
Proof. In all the following, We denote AT) the output of algorithm A when given an input instance
I. We will prove the claim of the lemma by treating separately the cases where 2 b and x b. Let us first observe that, if x 2 i, then the cost of ALG, is + ALG( cost was paid during the first days, and then ALG called provided with prediction Q.. The number of remaining snow days at that time is x - L. We remind that, since we are in a minimization problem, C(ALG, Pt) is at least 1. Consider the case where I b. thus OPT b) z. If S then ALG, (z, b) = x OPT(x, b). and if >> then
b, Q.), because unit
E|ALG, (I. b)] L E|ALG(x 1, Q.).
I + C(ALG, p.P - t,
+ C(ALG, Pt) -)
=C(ALG, Pa ) (C(ALG, pt) 1)1
S C(ALG, Px) xr - (C(ALG, pt) - t
-17
(1 (1 (1- C pi) OPT(x;;b)
C(ALG. pi) OPT(x,)).
Consider now that x > b, thus OPT(x, b) = b. If S then
(z, = x S1S j CC(AG..)))) OPT(,.
On the other hand, if L. then
E|ALG, b)] + C(ALG,p,)OPTC t,
I t C(ALG,
= (6 + CCAAG. OPT(2, b).
In all the cases we have (z, b)] S (t/b ((/D+C((AG..p.))) P.)) b), which gives the result.
A.2 Proof of Lemma 2.2
Proof. Let denote ALG (xr b, Q) the output of Algorithm given an instance x, and a prediction Q, and OPT(r, b) min(x. vr b} the cost of the optimal offline algorithm. Purohit et al. 47 prove that, if the algorithm given instead prediction y x, then sets Q 1(y 2 b) and behaves as we described, then its competitive ratio is upper bounded by min {1+ 1 (1+ + (- But in fact, it suffices to have and both larger or both smaller than b for the algorithm to behave exactly as = y. therefore we retrieve the bound This happens with probability Otherwise, when the prediction is incorrect, we always have that
the prediction Q is accurate.

---

ALG b, Q) S (1+1/AJOPT) Therefore
E[ALGizz x. b, 21 OPT (2,
S + 1) (1-p) (1 (1+ 1
=1+p1+ 1 1-p p
the latter expression is minimized for X V 1-p
p which gives
E[ALG x. b, 21
< 1 + 2/ p(1 p)-
OPT (I. b)
A.3 Proof of Lemma 2.3
Proof. Let X E (1/6, It is shown in 447 that Algorithm is
consistent and (--
(1--0--1555 -robust. Even though the upper bound shown in 47 suggests that the consistency bound is achieved only when given exactly accurate prediction y of the number of snow days, i.e. y - x, it suffices to have Q = ((x 2 b) for the algorithm to behave just the same. Therefore, with probability p we have that the cost of the algorithm is at most ( OPT b), and with
probability - p at most 1x-- OPT(2, b). With a simple function analysis, we have
that T-c S 1 e + 1 for any u E (0, 1). Therefore
E/ALG( b, 211 < -
pd
P
c-x
c- 11-b
1
1
S spt
+
p)
1
X
c e-
X 11/b/
pd
1-p p
1
-1 1-
c 1 )² p
+ X 1/b
+
c-1
e-1
p(> - 1/b) 1 1-p p
1
(1
1- 1- 1/b
e-1
(A-1/b)
c p.
The previous expression is minimized when À satisfies p(A-1/b)
1-p i.e. for x = t +
c-1
V(e- 2) However, we are restrained to choose À E (1/b, 1). thus the optimal choice of is min We have that
p(1 1/b)
1-
1 31
e-1
(A 1/b)
1 1-p P < 1 -
1
(e - 1)
p
b
(1 - 1/b)2
<
1-1
p> 1+ (1 1/6)2 -1
e-1 1
Therefore, p 2 11+ (1-1/8)²) e-1
-1
then with \= X we have
p(1 p)
p(1 p) e e-1 1
1 1- 11- 1/b
E/ALG( b, 2)] S
+ + e 1
+
p
e
p(1 - p)
+ (1 1- 1-1/b
2/
p.
c-1 1
c-1 1
c 1
2

---

and p (1 [ー1/1
then with À
1 obtain
E|ALG(z, b, 21
p
p
(1-e-1)
1
1
1/b
6
c
c
1
1/6)
1
+
+
1
1/b
1 - 1/b)
1
b
b-
1
b b-p p
b-1
B Secretary problem with predictions
B.1 Proof of Theorem 3.1
Proof. Since the secretary problem is purely ordinal, and since the applicants arrive in a uniformly random order, the success probability of ADATHRESH does not depend the values Ti...... TN. but only on B and N. Therefore, we denote QN.B the success probability of ADATHRESH with a budget B and input sequence of size N, 1 the position of the best applicant, Fsst (fs:....,20) for any 8 S 1, (TT:N, B) the event that ADATHRESH with budget B succeeds on the input T1:N. and Rg NB... We define the random variable
min { 2 NraN] +1: > (1.,
We will prove the claim of the theorem by induction on B.
For B = 0, is established that for ro L/e,, we have success probability of at least go 1/e. Let
B 2 1, and assume that the result is true for 1, we have
IN = P(S(ZEN, B)) = Σ
P(S(ELN: B) and T = t).
(3)
t= Ra
For any i, since the oracle Q is error-free, then under t, we have that Q(x,) 0 is equivalent to t and Q(x+)) = equivalent to 1* I, thus we have
P(S(EIN, B) and and ((x.) 0) P(r and 1ot = P(r P(r=t
(4)
N
1
P (max F1: > max 2 T
(5)
N
1
Rg RB/N
(6)
N
1-1
where true because the event S(1I.N, B) is implied by T- = 1", the second equality because / uniform random variable in {I,...,NK N). and because. conditionally to t" t, the event 7 = t is equivalent to not selecting any candidate in x 1. i. all those candidates have smaller values than max Rg. which is equivalent to saying that the maximum element in 114-1 is among the first Rg ones, and this is independent of the event = t* On the other hand, we have that
P(S(ZEN, B) and and (zx,) 1) P(S(FEI., B) | x P(T = t and t" > t).
Q(x,) =
Conditionally to {T = 1,, 2(x+)) = 1}. da the best candidate up to step f, and ADATHRESH used a prediction observe that t* t, The algorithm is therefore restarted with input I1+1 and budget B, and 5(11:N, B) = S(1+41NN, B 1), which is independent of the history up to step f, hence
P(S(NEN B) = I, ((x,) 1) = P(S(I++IN: 1))
4N B-1 2 48-1
3

---

by the induction hypothesis. Secondly, we have that the two following events are equivalent f = t and t" > t {max > max 21:8a > max +1:-11
and since the applicants are shuffled uniformly at random, the relative ranks inside any subset of {i1..... ..,, ,N. are independent of how max Y compares applicants outside Y, therefore
p and 1* 1) (mmax I:+1:N It maxTI: > max (
P(maxII:N E F:+I:N P(maxT = It ((mxxTia- E I1:
N
RB
- 1-1'
N
which gives
P(S(#EN B) and and 2(x+) = =1) (1
Rg
U(L 98-1.
(7)
N
Using and we deduce that
P(S(ILN, B) and T = Rp/N
1 t
R
+
t(t QB-1
t-
RB RB/N N
QB-1Rg
(1
q8-1)
1-1
1(1 1)
and substituting into gives that
QN.B 2 (1 9B-1)
RB
Σ
1
+ Q8
RB
Σ
1
N
t(t
Rn
Rn
RB
du
N
1)
2 (1 - QB-1 1)
+ QB
RBBBBB
N
ng
1
I=Rn
RB
N
RB
RB
Q
N
log
RB -1 1 Q8-1
RB
N
since RB < <TBN N+ + 1, we have that (og(N/(RB - 1)) 2 (0g(1/rB): and
RB
RB
RB - (TB
1
TB.
RB
N
It follows that The left term of this incquality maximal for rB = exp 1-an-- ) and obtain that
BNB 2 (1 - (B-1)r log( log((//B) + q--1 TB)
(8)
1
QN,B 2 (1 qn- qn-1)rn X 1 Q8-1
4 ra)
= + 1B-1 rn)
98-1 (1 -1-923 1BB-B1r2 9B
which concludes the proof.
B.2
Proof of Theorem 3.2
The algorithm Consider a simple adaptation of ADATHRESH, where the predictions are not always blindly trusted. If the conditions t 2 TgN and z, > max(21....... probability - X the algorithm chooses query prediction and trust and with probability À chooses to select the candidate I, without querying a prediction.
are met, then with
We will prove Theorem 3.2 using two lemmas. In the first one, show the lower bound the success probability of the algorithm we presented, and in the second one, we compute the limit of this lower bound when B oc. We define the function ʃ j0, (0, oo) by f(1) and for x E (0, 1)
1
f(x) = x + -1- x) exp
- Ø

---

Lemma B.1. The adapted ADATHRESH with budget B has success probability at least qp(p),
where (p(p) 1/e and for any B 2
(B(P) max
Moreover, P S (ef(1/e))- then for any B we have (D(P) 1/c, and otherwise qB(P) pf(qn-1(p)) for any B 2 1.
and assume that the success probability of this algorithm given budget B - 1 is lower bounded by some constant QB-1 (p) that is independent of N, the algorithm chooses to trust the prediction, then it inaccurate the algorithm fails with probability 1, and if it is accurate, which happens with probability p, then similarly to in the proof of Theorem 3.1 the success probability is lower bounded by
Proof. The success probability when B is lower bounded by 1/c. Let
(1 (p)) log(1/rB) qB)1 -B)
On the other hand, if the algorithm chooses not to trust the prediction. then its success probability is lower bounded by 1/c. Therefore, if we denote qN, (p, X) the success probability of the algorithm on an instance of size N, given a budget B of predictions that are each accurate with an independent probability p. then we have
(N, 2 + p(1-111) (11-
1---BBB-11-))))) log(1/rB) qB-1(p)(1 -1rB))
The left term is maximized for TB exp (-I-pu-1w)) and it gives
4N (N A) + (1 - A)p (B- + (1 1 (B) exp (- 1-100-- (-1-8-1(0)) 1
this is linear function of and is maximized for
A x= 1-1(1/e PTB-1(P) + p(1 -DB--(p)) exp (-I-qa-1(0) (x-(()))xp((--1111000
With this choice of X, we have that the success probability (N. A) is lower bounded by the constant (p) defined by
P(R-i(w) p(1 - ( (-I-98-10)
(p) = max
(f(()=1(()))
max
Before showing the second claim of the lemma, let us first prove that f increasing. We do this simply by computing its derivative
((x) =1 1
(111-11=+1) +1) exp (-T-
which is positive because exp(u) > u+ for any 1, in particular for 1/(1 - zr).
(1+ (e (e- 11) ex)p)p((==_))))) exp(-=_t)) since f is increasing, we have by induction for any B 2 0 that (p(p) = 1/e. In fact, it is true for B = 0, and QB-1 (p) = 1/e then pfp (p)) = pl(/ee S 1/e, thus (p(p) l/e.
Now, if (1(/e) < 1/e, i.. S (ef(1/e))
the other hand, if (1/e) > 1/e, then for any > we have that (((()1(()) > 1/e and thus 4 (p) pf (f( (p)). In fact, the property is true for B 1, and if it is true for some B > 1 then qB (p) = pf (p) > 1/e, thus (p)) 2 p1/e/) 1/e, the property remains true for B + 1, which concludes the induction.
Lemma B.2. 1fp (ef(1/e)) then the sequence qa (p) is increasing and
lim gn(p) B
1 W (((T-)))
where W is the inverse of ue" [0, oc), called the W-Lambert function.
5

---

Proof. Assume that p (ef(1/e)) // let prove by induction over B 2 that (B(p) > (p). For B we have that (p) pf(//e) 1/e = go(p) by the assumption on p. Now, let 2 1 and assume that (p(p) > (p). Since f is an increasing function on [0, 1]. we have that
g (p) - pf(gs(()) > pf((8-1())) = qz())
The sequence (p)) a20 is therefore increasing and it is upper bounded by since it is lower bound on a probability. We deduce that it converges to some limit that depends on p. Since f is continuous we have that L = pf()), solving this equation gives
8 8 pf(() = i = pl + p(1 exp
T
8
1
+ (1 p)
1-8
pexp
P exp
1
(1 p)
1-6
e
1 exp
e(1 - p)
P
W
c(1 - p)
1
1+ W
c((1p)
Thereofore p (p(p)
1+W c(I-p)
Observe that the algorithm we presented can also be adapted to the case where the accuracy of the oracle is constant and might depend the time or even the input sequence. In fact, long as the accuracy of the oracle is known to the algorithm, it can trust the oracle if it is correct with probability larger than (ef(1/e)) and ignore if otherwise. This gives a success probability always lower bounded by 1/e, with better guarantees depending on the accuracy of the oracle at times when is queried.
B.3 ADATHRESH with memory
We present now an improved version of ADATHRESH that keeps in memory the best observed value so far, and that rejects all applicants below this value.
Algorithm 5: ADATHRESH with memory
Input: Budget B, sequence of applicants (Iz, IN), largest previously observed value M
Reject the first NrgN] applicants;
for t [r + 1, ......,... do
xe > M and 2, > max( (I then
if B 0 then
5
query a prediction Q(xrx): if Q(x;) 0 then Return: f: else Return ADATHRESH(B - 1, (xx)),,,,,,,)))
else Return: t;
Initially, the algorithm is launched with M = -oo While we do not give theoretical guarantees on success probability of Algorithm 5 Section 5
we show experimentally how it compares to Algorithm in

---

C Preemptive B-clairvoyant job scheduling
C.1 Proof of Theorem 4.1
Proof. Let ALG be any non-clairvoyant algorithm that can query up to B job sizes for instances of N jobs. It is shown in Theorem 2.8 in 466 that by choosing input instance en of n job sizes sampled independently from the exponential distribution, any algorithm A verifies
E(A(E,)) 2 (2 - 4/n)E[OPT(E...
with E())T(E,)) = + n(n + 1)/4. Let consider in particular the algorithm An which, when given an instance J of S N jobs, samples N n positive numbers 21..... 2N-n from the exponential distribution, then runs ALG with the input J {( Let us denote (x N--) the output of Av conditionally to {=i Now, let & be an instance of N job sizes chosen from the exponential distribution be given as input for ALG. During execution, ALG will query number b < B of sizes for johs in some subset I of (1....,N) N). Denoting J = {1,..., N) T, we have by Equation that
ALG(E)
Σ D
Σ (DALG (i. + DALG (j.
IEJ
KCjEJ
Av (faybee/laaaeel)
In expectation, using that []] 2 B N ((N) with probability 1, we obtain
E[ALG(E)]
2 E B|Ax B (f=)hee)/mmabb) n n= [V]]]
2 E /
22
O(N).
Using again that E[)) N N(N 1)/4 N2/4+ O(N), we deduce that E|ALG(E) E(
2 + (1), which shows that the competitive ratio of ALG at least 2.
C.2 Intermediate Lemma and notation
Notations In all the following, we fix an instance J of job sizes 21 S... S IN. and we denote
a a uniformly random permutation of {1,..., NJ, /= (i)) =1 and J { B+B-- This equivalent to choosing set 7 of B jobs uniformly at random without replacement. We also denote I and J, respectively the sets of unfinished jobs in and time of a run of PAR.
The next lemma gives a simple computational result that we will use in further proofs.
Lemma C.1. For any + j we have E E(min( Eooiil
MM- Ex= (N - k)
Proof. Since is a random permutation, we only need to demonstrate the result for i, = 1, Since we assume that 21 S ...,.yp N. then for any ie < N we have
((min(2o(1) (o(2) xx) ((min(o(L)) (()) k)
(1)(a( 1 and o(2) k)
=2P(a(1) = k) ())) > k [1((1) =
2(N ----) k)
N(N - 1)
follows that
N
E(min(2o(1)) 22
P (xo(() = I
km 1
2
(N k)
N(N 1)

---

C.3 Proof of Lemma 4.2
Proof. Let us fix some update rule for a. In the execution of PAR, OPT run on I and RR on
J. and both sets are disjoint, therefore we have DPAR(i,) (i.j) = DOPT (i,j) for any i * j E I, and
T)AAR (i, = (RR (i, for any i + j E J, we can write
N
PAR(J)
Σ
(1. + (L. + D PAR + (J, + D
(J,1)
ri
i=1
N
Σ
zz + DOPT (I,1) DRR (J. DPAR PPAR (J,1).
(9)
Using Equation and Lemma
CA
we have that
Σ
E Bimin(2o()) Fo(
ISiCJEB
N
Σ
2
(N - k))=
N(N
KiKjEB
k=1
B(B 1)
N(N 1) Σ (N - -k)0k
and in the same way
EIDRR (J,])
Σ
2E 2E|min (ion
BEiejEN
2(N (N B - 1)
(N k)æz
N(N 1)
k=1
2B(2N B - 1)
(N k)
N(N 1)
Summing these two equations gives
N
2 B(B - -BBNN B 1)
E[D (J.
Σ (N k)
N(N -1)
k=1
B
B B-1
2
3
(N k)
N
N
1=1
and taking the expectation in Equation 9 concludes the proof.
C.4 Proof of Theorem 4.3
We here the same notations in Section 4.3 Before demonstrating the theorem, let us justify why (a )2 can be computed online, i.e for any 1 > 0, ofR can be computed knowing only the events that occurred up time t.
For any subset K of [I....,N' J. we denote RR(K) the algorithm that runs RR on {x, and ignores the other jobs. Running RR on all the input instance is equivalent to running concurrently
RR(T) and RR(J) with respective rates (a. RR )2 and (1 - a AR ).. In fact, for any > O, the processing rate any unfinished job in is 7
P and we have the same for jobs in J.
Consider running RR on { J. We denote jR the completion time job <is N. For any > 0, the amount of RR(T) executed until time is f . Therefore if we denote (.R
the completion time of job i I when running RR()), then we have
T:RR(T) =
RR du.
8

---

Knowing the sizes of jobs in I, (T)
(I) can be computed as
FRR (T) = I; +
RR (j, (j, = Zi Σ
Σ
Ij +
Tz-
JEL
JEI Sin
JEI 2.t
We deduce that PAR with SRR update rule can be implemented running concurrentyy OPT(1) and AR, RR(J) with respective rates a RR and 1 - -R where the processing rate updates as follows: initialize
c(f) B, c(J) N B and R [[+{[( N
d())
B and for any >> 0,
(i) if job in terminates, then c(J) t c()-
iii if R (I) Jo R du for some I, then c(I) c(I) 1,
and in both cases update a AR e())+()))
c())
Using the processing rate (a. ).20, the delays generated by on J are exactly the same if RR was running, and the delays by on / are smaller than RR's, because OPT(T) runs with the same processing rate as RR(7) but all the jobs finish earlier, thus using Lemma deduce that
Proof of Theorem 4.3
RR
B
N
(|DDAR(T,))) PAR (J,T)]
Σ
Σ
(oo)
1=1
B+1=
4B(N B)
Σ
(N - k)zK.
N(N - 1) k=1
Using Lemma 4.2
then Equation 2 we obtain
N
N
E[PAR(J)] <
2;
+ (2 1 (4
- + 4B
N(N
(N k)
i=1
A=1
+ (2
B(B-1)
N k)L
N(N-1)
1=1
k=1
(2
N(N-1)
Σ 24 Σ (N 1))z
B(B-1) N(N-I)
OPT(J).
Which proves the theorem.


Reviews:
[{"review_id": "4tso1c8iJb", "reviewer": "Reviewer_gTsH", "summary": "In this paper the authors re-consider classic online optimization problems in the area of learning-augmented algorithms, under the setting where the algorithms that have access to a limited number of predictions. Additionally, the setting that is considered assumes that as the algorithm progresses the predictions become more accurate. Three problems are studied under this model: 1) the ski-rental problem, 2) secretary problem, and 3) job scheduling problem. Each of these problems considers problem-specific advice, and the authors show that given correct advice they can significantly outperform the worst-case bounds from the non-learning-augmented model.\n\nThe main motivation for this work is that the advice can be very costly, and one cannot always assume access to unlimited calls to the learned advice. Hence, it becomes relevant to ask what are the best-possible bounds that one can obtain under this limited budget setting. \n\nWhile the paper is mainly interesting for its theoretical contributions, the authors additionally ran simulations showing that the algorithms behave according to the theoretical results. Also for the secretary problem the authors show a heuristic variation of the suggested algorithm that performs better than the theoretical lower bound.", "questions": "\n- For the Secretary problem, it is not clear what it means that \"assuming that the predictions are error-free, the problem is equivalent to the multiple-choice secretary problem\". In the setting of the paper, the algorithm has to additionally choose whether to select the secretary or keep searching.\n\n- The algorithm for the ski-rental problem assumes the knowledge of the success probability. Is this something realistic?\n\n- L226: \"The previous theorem shows that, with well-chosen thresholds for querying the predictions, strong theoretical guarantees on ADATHRESH can be obtained\". This is not obvious and should be explained.\n\n- Explain how the memorization variant of the algorithm for the secretary problem works.\n\n- No discussion on the experiment for the ski-rental problem. \n\n- Don't know how to read figure 4. Please explain.\n\n- Report standard deviation for the plot with the scheduling problem.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "+ Considers an interesting setting where the algorithm has a limited access to an oracle, and in one where the probability of correct advice increases over time. Although, it is not clear how to motivate the very restricted access (why would it be restricted if it comes from a model). \n\n+ A nice set of results for each of the three problems considered.", "weaknesses": "- Some advice and assumptions seem a bit unrealistic. Specifically, the advice on the size of the jobs in the job scheduling problem assumes that the advice is always correct but it is not clearly justified. Additionally, to tune the algorithms for the ski-rental problem, one needs to have knowledge of the probability of a correct prediction over time. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for the time and effort spent on our submission and for the positive evaluation of our work. We address below the weaknesses and questions that you raised.\n\n## Weaknesses\nSee the common answer.\n\n## Questions\n\n- In the secretary problem with perfect advice, as you explained in your comment, the algorithm has to additionally choose whether to select the secretary or keep searching. However, **after the perfect advice is given, the decision to make is trivial**: stop if the secretary is the best overall, and keep searching otherwise. \nWe can formally prove this equivalence as follows: \n     -  If $A$ is an algorithm for the multi-choice secretary problem with $B+1$ choices, then for a given instance $x_1,\\ldots, x_N$, we can define an algorithm $\\bar{A}$ for the secretary problem with $B$ perfect hints such that, at any step $t$ where $A$ selects a secretary, if $\\bar{A}$ has a null budget, then it accepts the secretary, and otherwise it queries a hint telling if $x_t$ is the best overall and if it is the case then $\\bar{A}$ accepts it and stops. Both $A$ and $\\bar{A}$ succeed if one of the secretaries selected by $A$ is the best overall.\n     - On the other hand, if $\\bar{A}$ is an algorithm for the secretary problem with $B$ perfect hints. Let $A$ the algorithm for the $B+1$-choice secretary problem defined as follows: if $\\bar{A}$ queries advice for some candidate $x_t$, then select them, but since $A$ cannot have immediate access to the feedback, it assumes that $\\bar{A}$ was advised to reject the candidate and continues. Finally, when $\\bar{A}$ exhausts all its budget, $B$ candidates will have been selected by $A$, and the last one selected is also the last candidate that $\\bar{A}$ selects without asking for advice since it has no more budget. With this, $A$ succeeds on a given instance if and only if $\\bar{A}$ succeeds on the same instance. \n\n- See the common answer\n\n- The sequence $q_B$ is increasing and upper bounded by $1$, thus it converges to some limit $\\ell$. Using the recurrence defining $q_B$ we find that $\\ell = 1$. This can be seen as an extension of the limit in Theorem 3.2 when $p$ goes to $1$. However, we agree that it should be mentioned right after Theorem 3.1.\n\n- ADATHRESH is defined recursively. If it is called at step $t$, then it runs on the instance $(x_{t+1},\\ldots,x_N)$, losing the information of $m = \\max(x_1,\\ldots,x_t)$. The memorization variant keeps this information in memory when restarted, and it skips all the candidates that have values below $m$. For candidates having a value larger than $m$, it behaves as ADATHRESH without memorization.\n\n- We present and discuss experiments for the ski rental problem in Appendix D. We will add them to the camera-ready version as an additional content page is allowed.\n\n- Figure 4 compares a run of RR (round-robin) and PAR with SRR update rule on the same instance. Let us ignore the yellow color for now. We consider an instance of 5 jobs indexed as 1,2,3,4,5. **Time is represented on the X-axis, and the Y-axis indicates the processing power allocated to each job**. In the left figure, we show a run of RR on this instance: initially, all 5 jobs run with a processing power 1/5 each. the first vertical line indicates the time when job 1 terminates. After that, the remaining jobs (2,3,4,5) run each with a processing power of 1/4 until job 2 is terminated, and so on. Now the yellow color is used to show the set $I = \\{1,2,3\\}$, which are the jobs with known sizes in this example.\nThe yellow area in the right figure is identical to that of the left figure, and at any time, its height indicates the total processing power allocated to $I$ by SRR. \nThank you for your remark on this Figure. We already updated it by indicating that the X-axis represents time and that the Y-axis indicates the processing power.\n- We will report standard deviations in Figure 6 for the camera-ready version."}, {"review_id": "9PqF8XQ00N", "reviewer": "Reviewer_rY4H", "summary": "Authors consider ML-augmented algorithms with a limited number of predictions.\nThey consider three problems: ski rental, secretary, and non-clairvoyant\nscheduling. Their result on non-clairvoyant scheduling assumes perfect\npredictions, while for ski rental and secretary problems they assume\nknowledge of the predictors success probability in advance.\nThis implicitly assumes that the input has a particular structure or comes from\na distribution where the predictors achieve the declared success probability.\nIn case of the secretary problem, they also discuss the case when an incorrect\nvalue of p is provided to the algorithm. I have not noticed such a discussion\nin the case of ski rental.\nIt is not clear whether the performance bounds achieved by their algorithms\nare tight.\n", "questions": "* there is a paper by Antoniadis et al. Learning-Augmented  Dynamic Power Management with Multiple States via New Ski Rental Bounds (NeurIPS 2021) which, as a special case, solves a sequence of ski rental instances, learning the precision of the predictor online. Can you relate somehow to their results?\n* I appreciate Figure 2 showing your competitive ratio in a natural setting. However, it looks like your ratio is never better than e/(e-1). What precision do you need to achieve meaningful improvement?\n* There is a paper by Im et al. Parsimonious Learning-Augmented Caching (ICML 2022) -- might be also worth mentioning in your related work.", "limitations": "theorems state their assumptions clearly", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "technically sound results", "weaknesses": "* absence of lower bounds for ski rental and secretary\n* only perfect predictions for scheduling\n* not clear how should we know the success probability of the predictor", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for reviewing our submission and for your feedback. Below, we address the weaknesses and questions that you raised.\n\n## Weaknesses\nSee the common answer.\n\n## Questions\n- The paper by Antoniadis et al. studies the problem of dynamic power management (DPM), which is a generalization of the ski-rental problem. They introduce a notion of $(\\rho,\\mu)$-competitiveness, where $\\rho$ indicates the consistency of the algorithm and $\\mu$ describes the dependence on the prediction error. Then, they design a near-optimal algorithm in the sense of this definition. The setting we study and our results are different from theirs, and we do not see how to relate or compare both papers. However, since the learning-augmented DPM problem involves multiple unknown variables, requiring a prediction for each, it would be very interesting to investigate it when the number of predictions is limited.\n\n\n- The blue curves represent the competitive ratio of the algorithm that queries a prediction at time $t$ and then runs the deterministic Algorithm 1. If the prediction is queried at $t=0$ then we find the optimal deterministic algorithm without prediction, which has a competitive ratio of $2$. The figure shows that a competitive ratio better than $2$ can be achieved by optimally choosing the time of querying the prediction.\nThe orange curves represent the competitive ratio achieved by querying a prediction at time $t$ and then running the randomized Algorithm 2, and these are the ones that should be compared to $e/(e-1) \\approx 1.58$. More precisely, in the setting without predictions, the competitive ratio of any algorithm is at least $\\frac{1}{1-(1-1/b)^b}$, which is very close to $e/(e-1)$ for $b = 50$ and $b=100$.  **The dashed curve ($b=100$) goes indeed below** $e/(e-1)$, beating the worst-case without prediction, while **the continuous one ($b=50$) always stays above it**, and equals the worst-case competitive ratio without prediction only when the prediction is queried at $t=0$. We chose the values of $b$ and the function $t \\to p_t$ on purpose to illustrate that, depending on the problem's parameters, it can be optimal to query the prediction at $t=0$ instead of querying it at an ulterior time. \n\n\n- Yes indeed, this paper is closely related to ours, as they study the caching problem with a limited budget of predictions. We include it in the related work.\n\n"}, {"review_id": "MFh0cPY2Hv", "reviewer": "Reviewer_imY3", "summary": "The paper studies learning-augmented algorithms in a setting where predictions are a scarce resource and algorithms need to decide when to request them. The framework is instantiated over (i) ski-rental with a single prediction, (ii) the secretary problem with B predictions, (iii) preemptive non-clairvoyant scheduling with B perfectly accurate predictions. The article mainly presents upper bounds for these problems.", "questions": "For the ski-rental problem, did you consider what happens if one has B predictions that are independent? An interesting thing that might happen is that two general strategies appear to be in conflict: (1) Spend the B predictions at the beginning to have as good as possible an initial prediction, due to the independence assumption. (2) Wait until predictions unfold (i.e., are confirmed or refuted by reality) and when the season continues spend more predictions to sort of recursively reset the state imagining the season just started.\n\n", "limitations": "They're not really addressed, although I don't see an issue in the particular case of this paper as there doesn't seem to be much to address anyway.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper is really well-written\n- The framework is well-motivated and likely to inspire further work\n- The results are nice and non-trivial\n- Proofs (as far as I checked) in the supplementary material seem to be correct\n- Experimental figures help understanding the parameters in the results (e.g., roles of $b$ or $p$)", "weaknesses": "No major weaknesses, so I'll point some relatively minor ones.\n\n1) It's unclear how novel the setting is and I think the paper could be more straightforward about this; the authors provide a section on related work, but while they mention the setting is relatively unexplored, there are examples of the setting that they provide as well as others they don't seem to cite like \"Parsimonious Learning-Augmented Caching\" by Im et al. The abstract of the paper, as well the introduction page, give me the feeling that the authors are presenting the setting itself as a contribution, whereas it seems that setting is not itself novel and the contribution is about the specific results for specific problems presented (which is not minor).\n\n2) On Algorithm 2 I think it would be nicer to write \"buy on the start of day $d \\in ...$ with probability proportional to $(1-1/b)^{\\lfloor \\lambda b \\rfloor - d}$.\n\n3) The results (i.e., theorem statements) could be phrased in terms of consistency/robustness more explicitly.\n\n4) As usual I printed the paper on black-and-white, and the figures are not great in this respect -- consider for example Figure 1, where the lines only differ by color. I suggest using either some pattern (dashed, dotted, etc, (Figure 2 does a bit of this, but it can still be improved)). Granted this is not an issue on a computer screen, but it's worth considering too for accessibility reasons (colorblind readers, etc.)\n\n5) The scheduling problem setting is a bit weird as the predictions are assumed to be perfect, and thus said problem doesn't really fit the learning-augmented framework, only the budget-constrained aspect. It would be more solid if the paper considered predictions with a parametric quality.\n\n6) It seems that the predictions considered are always in terms of their probability of being correct rather than on a notion of error (as in Lykouris and Vassilvitskii), which fits the framework of (https://openreview.net/forum?id=HFkxZ_V0sBQ), and seems appropriate to cite.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for reviewing our paper, and for your positive evaluation of our work. We are very happy that you appreciated the paper and enjoyed reading it. Below we address the weaknesses and questions you raised.\n\n\n## Weaknesses\n**1.** Regarding the paper by Im et al., it is indeed a closely related paper to our work, as they consider the caching problem with a limited budget of predictions. We will update the related work section to include it, and we will try to better explain the contribution in the introduction.\n\n**2.** Yes this indeed is a nicer way to write the algorithm. Thank you for the suggestion.\n\n**3.** We will be more explicit about them in the results statements.\n\n**4.** We completely agree, we will update the figure and take this into account in the other figures also.\n\n**5.** See the common answer.\n\n**6.** The predictions in the problems we studied are indeed considered in terms of their probability of being true. We will cite the work of Gupta et al. in the related work. It is also worth mentioning that Lemmas 2.2 and 2.3 in our paper make a transition (in the particular case of binary predictions) between the framework of Vassilvitskii and that of Gupta et al.\n\n\n## Questions\nEven more generally, consider having access to a group of $B$ experts, each of whom can only be consulted once during the algorithm's execution. Each expert $b \\in \\{1,\\ldots,B\\}$ has an independent probability $p^b_t$ of being correct, which varies with time.\nAs you mentioned, several strategies can be used. The first approach is to select a specific time to query all the experts' predictions simultaneously, hence obtaining a more accurate recommendation. Alternatively, a second strategy involves using the predictions in a sparse manner. Lastly, there are intermediate strategies where a few predictions are used at the beginning (instead of just one), then a few others at some ulterior step, and so forth. Given the experts' different accuracy $p^b_t$ for $1 \\leq b \\leq B$, the order in which the algorithm queries their advice becomes crucial.\nThis is an intriguing problem that we are exploring and plan to include in the journal version of the paper."}, {"review_id": "NRvH3RhUzn", "reviewer": "Reviewer_HbqC", "summary": "This paper considers learning augmented online algorithms where there is a bound on the number of predictions that can be queried.  Three problems are considered within this framework: Ski-rental, Secretary Problem, and Non-clairvoyant scheduling.\n\nFor the ski-rental problem, they consider a model where the algorithm can make noisy queries of the form \"$x-t  > b$?\", where $t$ is the current day.  The output of the query is a binary value which is correct independently with probability $p_t$, and the sequence $p_t$ is known up front to the algorithm.  Modifying ideas from Purohit et al. NeurIPS 2018, they give deterministic and randomized algorithms whose competitive ratio improve as the probability of correctness approaches 1 and are never worse than 2 and $e/(e-1)$, respectively.\n\nFor the secretary problem, they again consider predictions which are correct with probability $p$, but the algorithm can only query the predictions at most $B$ times.  Here the prediction is a binary prediction of whether or not the current item has the highest value in the sequence.  They give an algorithm which selects the best item with probability $1/e$ and improves as the probability $p$ increases.\n\nFor non-clairvoyant scheduling, the paper defines the problem of $B$-clairvoyant scheduling, in which the scheduler can query the exact sizes of $B \\leq N$ jobs.  For this they show that $B = \\Omega(N)$ queries are necessary to improve the competitive ratio below 2 which is met by the round robin algorithm in the non-clairvoyant setting.  To complement this they give an algorithm with competitive ratio $2-B(B-1)/(N(N-1))$, which gives an interpolation between the non-clairvoyant and fully-clairvoyant settings.\n\nFinally, a short experiment section which tests the proposed algorithms on synthetic data is provided.", "questions": " - Concerning the lower bound for B-clairvoyant scheduling (Theorem 4.1), I think one of the references at the beginning of the proof is wrong.  For the lower bound of any possibly randomized algorithm against jobs independently sampled from an exponential distribution, the reference should be for Theorem 2.8 in [44] (not [45]).\n\n- There is other recent work which considers learning-augmented online algorithms with limited querying.  See the following:\n     - Im, S., Kumar, R., Petety, A., Purohit, M.. (2022). Parsimonious Learning-Augmented Caching. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:9588-9601 Available from https://proceedings.mlr.press/v162/im22a.html.\n\n- For ski-rental and the secretary problem, this paper considers predictions which are correct independently with some probability $p$.  A similar model has also been considered recently for caching and online covering problems.  See the following:\n    - Gupta, Anupam and Panigrahi, Debmalya and Subercaseaux, Bernardo and Sun, Kevin.   Augmenting Online Algorithms $\\varepsilon$-Accurate Predictions.  Advances in Neural Information Processing Systems 2022.\n\n- For the experiments on $B$-clairvoyant scheduling, it seems it would be natural to consider exponentially distributed job sizes, since those witness the lower bound for Theorem 4.1.\n\n- For the ski-rental and secretary problem results, is it possible to give any general lower bounds for the competitive ratio of any algorithm?  For the ski-rental result this could help to alleviate the concerns the authors raise with using the simpler strategy over the optimal strategy which is difficult to analyze.\n\n- Please use proper capitalization for the title and section titles.", "limitations": "This paper is mostly theoretical in nature, so any possible limitations are inherent in the assumptions and theorem statements which have been stated clearly (and thus addressed by the authors).", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "With the recent interest in learning-augmented algorithms/algorithms with predictions there has been recent interest in studying the extent to which such algorithms need to access to many predictions in order to achieve better than worst case results, so the considered problems are well motivated.\n\nThe results on the secretary problem and non-clairvoyant job scheduling are interesting.  In particular, the lower bound (Theorem 4.1) holds even in the case where the predictions match the ground truth.  The overall result presents a clean interpolation between the clairvoyant and completely non-clairvoyant settings.\n\n", "weaknesses": "\n- For the ski-rental result, the authors claim that they give an algorithm which chooses the best time to query the prediction based on the sequence $p_t$ (lines 79-80).  From what is presented in Section 2. it is not at all clear that they do this.  At best, there is an example for a specific sequence of $p_t$'s, but I don't see a general argument.\n\n - In terms of novelty, the techniques for ski-rental and non-clairvoyant scheduling can be viewed as extensions of the ideas presented in Purohit et al. NeurIPS 2018.  \n\n- There is a disconnect between the first two sections (ski-rental, secretary) and the third (scheduling).  For the first two the predictions are only correct with some probability while for the scheduling result the queries return exact job size values.  A more unified framework would make the paper significantly cleaner.\n\n - Aside from the scheduling result, the authors do not give evidence for the tightness of their results.\n\n- The experiments mostly confirm what is predicted by the theory and don't seem to say much else.  Experiments on real data would alleviate this and also provide more evidence for the assumption that predictions are correct independently with some known probability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for reviewing our submission and for your feedback. Below, we address the weaknesses and questions that you raised.\n\n## Weaknesses\n- We explain how to choose the time of querying the prediction in the discussion following Lemma 2.1 (paragraph starting in Line 165). Given a learning-augmented algorithm with a competitive ratio $C(p)$ that depends on the accuracy $p$ of the predictor, Lemma 2.1 shows how to deduce an algorithm with a competitive ratio of $t/b + C(p_t)$ for any $t\\geq 0$. The best time to query the prediction is, therefore, $t^\\star$ minimizing the function $t \\mapsto t/b + C(p_t)$. It depends on the functions $p\\to C(p)$ and $t \\to p_t$.\n\n\n- We respectfully disagree with this statement:\n    - Regarding the ski-rental problem, it is true that **we use as an example the algorithms introduced by Purohit et al.,** however, the techniques we used in the proofs are different, and the main idea we presented is how to estimate the competitive ratio of these algorithms when the accuracy of the predictor is known, how to adjust $\\lambda$ in such case, and how to choose the time of querying the prediction. This is a general idea that can also be used with any other learning-augmented algorithm taking a binary prediction as input. \n    -  Secondly, regarding the scheduling problem, **the setting we investigate, results, and proofs are independent of those in the paper of Purohit et al.** The only resemblance is that we run the jobs in parallel with appropriate processing power each, and this is a core idea in all preemptive scheduling algorithms (for example RR algorithm). In the problem we proposed, the difficulty is not to deal with inaccurate predictions, but instead to find a way to make good use of a limited number of perfect hints, which is not trivial.\n\n- See the common answer.\n\n- See the common answer.\n\n- The experiments indeed confirm the theoretical results [as expected], but they also provide additional insights. For the secretary problem, we only showed a theoretical lower bound on the success probability of ADATHRESH, while Figure 5 shows that this lower bound is actually tight when $N$ is large. Also, the same figure shows that the heuristic ADATHRESH with memory has a better success probability. On the other hand, Figure 6 shows that with many natural and benchmark instances, the algorithm we proposed has a competitive ratio $2-B/N$, which is better than the theoretical bound $2-B(B-1)/(N(N-1))$.\n\n## Questions\n- Yes, thank you for noticing it. We will correct the reference.\n\n- We agree, it is a closely related paper, as they consider the caching problem with a limited budget of predictions. We will include it in the related work.\n\n- Their model is indeed similar to the one studied here in spirit. We will cite them in the related work section.\n\n- We considered exponentially distributed job sizes in Figure 6 (orange curve, (ii) in the discussion on the figure).\n\n- See the common answer.\n\n- Thank you for the remark, we will address any errors related to capitalization in the title and section titles."}]

Author rebuttal:

We would like to thank the reviewers for their feedback and thoughtful comments toward improving our paper. We address below some general comments and weaknesses that were raised by the reviewers.

### Ski-rental: Tightness of the results
We do not provide tightness results for the ski-rental problem, but we plan on working on them for the journal version of the paper. The study of tightness and trade-offs between consistency and robustness in learning-augmented algorithms can be a difficult task, for instance it is the main topic of many papers such as "Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms" (NeurIPS 2020). 


### Secretary: Tightness of the results
We did not prove an upper bound because the main focus of the paper, in the section on the secretary problem, is to design an algorithm taking advantage of the predictions, even if inaccurate, to have a success probability better than $1/e$. Moreover, as we discuss in the paragraph starting in Line 252, if the predictions are accurate, then the problem we described is equivalent to the multi-choice secretary problem (Gilbert and Mosteller, 1966), and we are not aware of any upper bounds for the problem that we can try to extend in the case of inaccurate predictions. 

### Ski-rental: How to know the accuracy of the oracle?
For the settings modeled as variants of the ski rental problem, it is possible in many cases to have a good estimate of the accuracy of the predictions. Take for example weather forecasts, the newsletter "forecast performance 2021" of ECMWF (European Centre for Medium-Range Weather Forecasts) shows that the quality of predictions, as a function of the lead time before the day concerned by the prediction, can be estimated very precisely. 
On the other hand, the bounds we provide hold also if the accuracy of the predictions is at least $p_t$, which is a weaker condition.


### Secretary: How to know the accuracy of the oracle?
This assumption might be easier to understand with an "ordinal decision maker" and a "cardinal oracle". More precisely, consider a decision-maker that has an imperfect interviewing process, and thus can only compare the applicants with each other, i.e. observe their relative ranks, but lacks access to their true value. On the other hand, an expert who, due to extensive experience, knows how to better interview the applicants and extract their true value, and also knows the distribution of their values [like in a prophet setting].
The decision-maker can ask the expert to interview some candidates for a cost. After that, the expert does not disclose the precise value of the applicant - that is irrelevant to the decision maker-, but they provide a recommendation (accept or reject) and accompany it with a confidence level, which is the probability that this recommendation is accurate. 


### Why is the advice considered to be perfect for the scheduling problem?
The clairvoyant and non-clairvoyant scheduling problems both have many real-life applications. It is therefore easy to imagine applications for the $B$-scheduling problem, which is an in-between setting. In opposite to the ski rental or the secretary problem, where the advice is a forecast/prediction, the advice provided in the scheduling problem can be perfect in many cases. 
Moreover,  we demonstrate by studying this problem that 1) even using perfect advice can be non-trivial, 2) and also that the decision-maker cannot always take advantage of the ability to choose the time to query advice instead of having it as input, as the optimal time to query it, in this problem, is at the beginning.

Meta-review: This paper was generally liked by the reviewers. The framework was viewed as motivated and could be of use in the future. The results were viewed as a complete story and expanded the current literature. The authors are encouraged to improve the writing and comparison to prior work as pointed out by the reviewers.
Decision: Accept (poster)