The Secretary Problem with Predicted Additive Gap
Authors: Alexander Braun
Sherry Sarkar
Venue: NeurIPS 2024 poster (2024)
Keywords: Secretary Problem
Competitive Analysis
Online Algorithms
Predictions
Robustness
Consistency
Primary area: optimization
TL;DR: The paper studies the secretary problem with a weak piece of information: a single additive gap between weights. Given this, we derive improved guarantees for the secretary problem, beating previously tight bounds.

Abstract: The secretary problem is one of the fundamental problems in online decision making; a tight competitive ratio for this problem of $1/e \approx 0.368$ has been known since the 1960s. Much more recently, the study of algorithms with predictions was introduced: The algorithm is equipped with a (possibly erroneous) additional piece of information upfront which can be used to improve the algorithm's performance. Complementing previous work on secretary problems with prior knowledge, we tackle the following question: 

_What is the weakest piece of information that allows us to break the $1/e$ barrier?_

To this end, we introduce the secretary problem with predicted additive gap. As in the classical problem, weights are fixed by an adversary and elements appear in random order. In contrast to previous variants of predictions, our algorithm only has access to a much weaker piece of information: an _additive gap_ $c$. This gap is the difference between the highest and $k$-th highest weight in the sequence.
Unlike previous pieces of advice, knowing an exact additive gap does not make the problem trivial. 

Our contribution is twofold. First, we show that for any index $k$ and any gap $c$, we can obtain a competitive ratio of $0.4$ when knowing the exact gap (even if we do not know $k$), hence beating the prevalent bound for the classical problem by a constant. Second, a slightly modified version of our algorithm allows to prove standard robustness-consistency properties as well as improved guarantees when knowing a range for the error of the prediction.

The Secretary Problem with Predicted Additive Gap
Alexander Braun
Sherry Sarkar
Abstract
The secretary problem is one of the fundamental problems in online decision making; a tight competitive ratio for this problem of 1/c R 0.368 has been known since the 1960s. Much more recently, the study of algorithms with predictions was introduced: The algorithm is equipped with a (possibly erroneous) additional piece of information upfront which can be used to improve the algorithm's 's performance. Complementing previous work on secretary problems with prior knowledge, we tackle the following question:
What is the weakest piece of information that allows to break the 1/c barrier? To this end, we introduce the secretary problem with predicted additive gap. As in the classical problem, weights are fixed by an adversary and elements appear in random order. In contrast to previous variants of predictions, our algorithm only has access to much weaker piece of information: an additive gap This gap the difference between the highest and k-th highest weight in the sequence. Unlike previous pieces of advice, knowing an exact additive gap does not make the problem trivial. Our contribution is twofold. First, we show that for any index k and any gap c, can obtain competitive ratio of 0.4 when knowing the exact gap (even if we do not know k), hence beating the prevalent bound for the classical problem by constant. Second, slightly modified version of algorithm allows to prove standard robustness-consistenng consistency properties as well as improved guarantees when knowing range for the error of the prediction.
The full version with proofs can be found at hhtps:://aat org.abs/////////eeee
aa//ab//2244 2409
20460 Braun and Sarkar 2024]
Introduction
The secretary problem fundamental problem in online decision making: An adversary fixes non-negative, real-valued weights w1 2 W2 2 .... 2 w, which are revealed online in random order. The decision maker is allowed accept (at most) one element. At the time of arrival of element, the decision maker is required to make an immediate and irrevocable acceptance decision. The goal is maximize the weight of the selected element. A tight guarantec" of 3/e known since the seminal work of Lindley [1961] and Dynkin [1963) (also see Ferguson 1989 or Freeman (183]) and can be achieved with very simple threshold policy.
In the modern era, the assumption having no prior information on the weights is highly pessimistic. To go beyond worst analysis, researchers have recently considered the setting where have some sort of learned prediction that our algorithm may use up front. This setting spawned the recent and very successful field of algorithms with predictions, Antoniadis et al. [2020) and Dütting et al. [202T] studied the secretary problem with prediction of the largest weight in the sequence, and
IIntiittte of Computer Science, University of Bonn. Email: alexander. @ weeeunn-oonn bonn.de
t CCarnegie Mellon University. Email: sherrys @ andrew.cmu.edu
'In the literature, there are two variants of the secretary problem: mmbabblity-maxiiizatte (maximize the probability of selecting wx) and middmm-mximizzttion (maximize selected weight). Throughout the paper, we consider the latter of the two variants.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

resolve this setting with an algorithm which yields nice robusiness-consistenyy consistency trade-off. Fujii and Yoshida [023] consider the secretary problem with an even stronger prediction: prediction for every weight in the sequence.
However, predicting the largest element weight sometimes be difficult or unfavorable. For example in retail, past data may only contain information about prices and not the true values of buyers Kleinberg and Leighton| 2003 Leme et al. 2023]; or for data privacy reasons (see e.g. Asi et al. (023 only surrogates for largest weights are revealed in history data. This motivates to advance our understanding of the following question:
What is the weakest piece of information we can predict that still allows us to break the a/e barrier?
Stated another way, is there a different parameter we can predict, one that does not require us to learn the best value, but still strong enough to beat 1/e? This brings us to the idea of predicting the gap between the highest and k-tt highest weight, or in other words, predicting how valuable wi is with respect to w1- Coming back to data privacy for example, such a parameter does successfully anonymize the largest weight in the sequence.
From theoretical perspective, for some special cases of gaps, previous work directly implies improved algorithms. For example, if we know Wi and wy have the same weight, using an algorithm for the two-best secretary problem [Gilbert and Mosteller 1966 directly leads a better guarantee. More generally, if we know the multipicaative gap wi/ws, we observe that we can generalize the optimal algorithm for W1 = W2 (see e.g. [Gilbert and Mosteller (9666). Buchbinder et al. (0014). However, if we instead only know wn/mi O, this does not help at all. The only insight is that
W/ = 0; we have no insight on the range of values taken. This essentially boils down to the classical secretary problem and the best competitive ratio again is 1/c. So while the multiplicative gap advises about the relative values without needing to know Wi entirely, it is not strong enough in general to beat 1/e. In this paper, we consider instead predicting an additive gap w Wkk
The additive gap between Wi and wy can be viewed as interpolating between two previously studied setups: when Ww wi gets small, we get closer towards the k- b-best secretary problem, and when w1 - Wig is very large, the additive gap acts as surrogate prediction of W1. the prediction setting in Antoniadis et al. [2020) and Dütting et al. [202T]. As we will see, even though the additive gap is much weaker than a direct prediction for wh. it strikes the perfect middle ground:
strong enough to beat l/c by a constant for any possible value of the gap wi - wy (and even if we do not know what is upfront). In addition, in contrast to pieces of advice studied in the literature so far, knowing an
exact additive gap does not make the problem trivial to solve.
1.1 Our Results and Techniques
Our contribution is threefold. First, in Section we show the aforementioned result: knowing an exact additive gap allows us to beat the competitive ratio of 1/2 by a constant.
Theorem 1 (Theorem 4 simplified form). There exists a deterministic online algorithm which achieves an expected weight of E [ALG] 2 0.4 W1 given access to a single additive gap Ck for C W1 Wy and some k.
Still, getting an exact gap might be too much expect. Hence, in Section we introduce slight modification in the algorithm to make it robust with respect to errors in the predicted gap while simultaneously outperforming the prevalent competitive ratio of 1/o by constant for accurate gaps. Theorem 2 (Theorem 5 simplified form). There exists a deterministic online algorithun which uses a predicted additive gap and is simultaneously (1/c O(1) -consscct and (11)-robust.
The previous Theorem 2 does not assume any bounds on the error of the predicted additive gap used by our algorithm. In particular, the error of the prediction might be unbounded and our algorithm is still constant competitive. However, if we know that the error is bounded, we can do much better. Theorem 3 (Theorem 6 simplified form). There exists a deterministic online algorithm which achieves an expected weight [ALG] 2 0.4 wi 2e given access to a bound e on the error of the predicted gap.
Our algorithms are inspired by the one for classical secretary, but additionally incorporate the gap: Wait for some time to get a flavor for the weights in the sequence, set a threshold based on the past observations and the gap, pick the first element exceeding the threshold.

---

At first glance, this might not sound promising: In cases when the gap is small, incorporating the gap in the threshold does not really affect the best-so-far term. Hence, may seem that beating 1/e is still hard. However, in these cases, even though the threshold will be dominated by the bost-so-far term most of the time, the gap reveals the information that the best value and all other values up to w/ are not too far off. That is, even accepting weight which is at least Wy ensures sufficient contribution.
Our analyses use this fact consider many elements in the sequence for acceptance at all. Or the gap is small which implies that accepting any of the highest elements is reasonably good. For each of the cases we derive lower bounds on the weight achieved by the algorithm.
foundational way: Either the gap is large in which case we do not
Since we do not know upfront which case the instance belongs to, optimize our initial waiting time for the worse of the two cases. In other words, the waiting time cannot be tailored to the respective case but rather needs to be able deal with both cases simultaneously. This introduces some sort of tension: For instances which have a large gap, we would like the waiting time to be small. By this, we could minimize the loss which we incur by waiting instead of accepting high weighted elements at the beginning of the sequence. For instances which have a small gap, the contribution of the gap to the algorithm's 's threshold can be negligible. This results in the need of longer waiting time the beginning to learn the magnitude of weights reasonably well. We solve this issue by using a waiting time which balances between these two extremes: It is (for most cases) shorter than the waiting time of 1/e from the classical secretary algorithm. Still, it is large enough to gain some information on the instance with reasonable probability.
As a corollary of our main theorem, we show that we can beat the competitive ratio of 1/e even if we only know the gap W1 we but do not get to know the index k. In particular, this proves that even an information like "There is gap of c in the instance" is helpful to beat 1/e, no matter which weights are in the sequence and which value attains.
Complementing theoretical results, we run simulations in Section 6 which strengthen our theoretical findings. First, we show that for instances in which the classical secretary algorithm achieves nearly tight guarantee of 3/e, our algorithm can almost always select the highest weight. In addition, we further investigate the out, underestimating is not as much of an issue as overestimating the exact gap.
trade-off of our algorithm. In particular, as it will turn
1.2 Additional Related Work
Implications of related results on the additive gap. In the two-best secretary problem, we can pick at most one element but win when selecting either the best or second best element. For this problem. the competitive ratio is upper bounded by approximately 0.5736 (Buchbinder et al. 2014 Chan et al., 2015) (the authors provide algorithm which matches this bound, so the guarantee is tight). As our setting with wi - w22 = 0 can be viewed as a special case, this yields a hardness result; the best any algorithm can perform with the exact additive gap provided upfront is approximately 0.5736.
A non-exhaustive list of related work on secretary problems. Since the introduction of the secretary problem in the 1960s, there have been a lot of extensions and generalizations of this problem with
beautiful algorithmic ideas to solve them Kleinberg] 2005), Babaioff et al. [0007] 2018 Feldman
et al. (2018) Korula and Pál (009). Mahdian and Yan [201] Kesselheim et al. [2018] Rubinstein
[2016]. Beyond classical setups, recent work by Kaplan et al. (2020) and Correa et al. [2021] studies
the secretary problem with sampled information upfront. Here, some elements are revealed upfront
to the algorithm which then tries to pick the best of the remaining weights. Guarantees are achieved
with respect to the best remaining element in the sequence. In addition, there are also papers bridging
between the secretary problem and the prophet incquality world, e.g. Cooreaa et al. [2020] or Correa
et al. | and many more [Bradac et al. 2020 Kesselheim and Molinaro] 2020 Argue et al.
2022
Algorithms with machine learned advice. In the introduction, we already scratched the surface of the field on algorithms with predictions. Here, the algorithm has access to some machine learned advice upfront and may use this information to adapt decisions. Initiated by the work of Lykouris and Vassilvitskii (022] and Purohit et al. (2018), there have been many new and interesting results in completely classical problems within the last years, including ski rental Wei and Zhang (2020). J online bipartite matching Lavastida et al. [ [202T], load balancing Ahmadian et al. [203]] and many more
(see e.g. Im et al. 202 Zeynali et al. [202]] Almanza al. [2021)). Since this area is developing
3

---

very fast, we refer the reader to the excellent website Algorithms with wredictteeiiiiosss/ for references of literature.
As mentioned before, also the secretary problem itself has been studied in this framework, Antoniadis al. 2020) consider the secretary problem when the machine learned advice predicts the weight of the largest element w1. Their algorithm's 's performance depends on the error of the prediction as well as some confidence parameter by how much the decision maker trusts the advice. In complementary Dutting et al. [021]] give a bigger picture for secretary problems with machine learned advice. Their approach is LP based and can capture a variety of settings. They assume that the prediction is one variable for each weight (e.g. -al-vaii indicating if the current element is the best overall
or not). Fujii and Yoshida (2023] assume an even stronger prediction: Their algorithm is given prediction for every weight in the sequence. In contrast, we go into the opposite direction and deal with less informative piece of information.
Our work also fits into the body of literature studying weak prediction models, previously studied for e.g. paging [Antoniadis al. [202), online search [Angelopoulos] [202]], just mention a few. In these, several different directions for weak prediction models were considered. For example, the setting in scheduling caching where the number of predictions is smaller than the input size 2022
(Im
et al.
Benomar and Perchet 2024).
2 Preliminaries
In the secretary problem, adversary fixes non-negative, real-valued weights, denoted wi 2 W2 2 ... 2 Wn. For each of the elements, there is an arrival time t, E Unif(0, 1]. Weight wy is revealed at time and we immediately and irrevocably need to decide if we want to accept reject this element. Overall, we are allowed to accept at most one element with the objective of maximizing the selected weight. We say that algorithm is a-competitive or achieves competitive ratio of if E [ALG]] 2 a W1 = a max; Wi, where the expectation taken over the random arrival times of elements (and possible internal randomness of the algorithm).
In addition to the random arrival order, we assume to have access to a single prediction é. for one additive gap together with its index k. The additive gap for some index 2 < k S is CY W1 Wk- We say that an algorithm has access to an exact or accurate gap if & C (as in Section algorithm gets a predicted additive gap èy which might not accurate (as in Section 4 or Section 5 we say that čg has error 17 = [&g cx|. We call an algorithm p-robust if the algorithm is p-competitive regardless of error 17 and we say the algorithm ci-consistent if the algorithm is co-oompetitive when 7) O. To fix notation, for any time E [0, 1]. we denote by BSF((T (read best-so-far at time r) the highest weight which did appear up to time r. In other words, BSF(T) = max Wy Also, when clear from the context, we drop the index & at the gap and only call it c or è respectively.
When the
Knowing an Exact Gap
Before diving into the cases where the predicted gap may be inaccurate in Section and Section S we start with the setup of getting a precise prediction for the gap. That is, we are given the exact gap CK W1 Wi for some 2 < k < n. We assume that we get to know the index is as well as the value of ck. but neither wi nor wk.
Our algorithm takes input the gap e as well as waiting time This gives the freedom to potentially choose r independent of if required. As a consequence, we could make the algorithm oblivious the index i: of the element to which the gap is revealed. We will use this in Corollary [
Algorithm 1 Secretary with Exact Additive Gap
Input: Additive gap e, time 7 E [0, 1] Before time r: Observe weights wi At time 7:
Compute BSF(T) = max Wy
After time T:
Accept first element with w, 2 (T)))
'Note that this setting is equivalent to drawing a random permutation of the n elements and revealing elements in this order one by one.

---

This algorithm beats the prevalent competitive ratio of 1/e = 0.368 by constant.
Theorem 4. Given any additive gap ck w1 whe for (4/++)*** Algorithm achieves competitive ratio of max (0.4, 1/2 (2/++1)V*)
Note that as tends towards n and both become large, the competitive ratio approaches 1/2.
We split the proof of Theorem in the following two lemmas. Each of them gives a suitable bound on the performance of our algorithm for general waiting times 7 in settings when wy, is small or large. The first lemma gives a lower bound in cases when wk is small in comparison to wi
Lemma 1. If wk 2 W1, then [ALG]] 2 (1 -
2(=1)) w1-
The second lemma will be used to give a bound when wa is large compared to W).
Lemma 2. If wk W1, then the following two bounds hold:
(i) E [ALG]] Z k+1 (1 T (1 -))++))) w and
(i) E [ALG]
Z (n (+) 21 (1 -)) W1
As a consequence, E [ALG] is also least as large as the maximum of the two bounds.
The proofs of the lemmas as well as their combination to prove Theorem be found in the full version [Braun and Sarkar 2024]. From high level perspective, the two lemmas give reasonable bound depending of we either exclude a lot of elements in the algorithm (Lemma [ or if the largest elements ensure sufficient contribution (Lemma 2).
As corollary of the proof of Theorem we also get a lower bound on the weight achieved by the algorithm if we are only given the gap, but not the element which obtains this gap. That is, we are given Eg but not the index k.
Corollary 1. If the algorithm only knows cj. but not k, setting r = 0.2 achieves E [ALG] 2 0.4 w1-
The full version (Braun and Sarkar 2024 contains proof of Corollary 1 as well. It mainly relies on the fact that some lower bound we obtained in the proof of Theorem 4 holdd for any choice 7 E [o, 1]. Also, the algorithm itself only uses the gap contribute the threshold. The index 1: is only used to compute т. As consequence, when choosing т 0.2 independent of k, the algorithm is oblivious to the exact value of k. but only depends on the gap ca- For this choice of r, we can show that Z 0.4.
As consequence, very surprisingly, even if we only get to know some additive gap Oj and not even the index k the exact value that Cş attains and holds for any small or large gaps.
outperform the prevalent bound of l/e. Also, observe that this is independent of
As mentioned before, Algorithm 1 is required to get the exact gap as input. In particular, once the gap we use in the algorithm is a tiny bit larger than the actual gap Ck. we might end up selecting no element at all.
Example 1. We get to know the gap to the smallest weight e, W1 - wn and the smallest weight in the sequence satisfies w,, = (. Let the gap which we use in Algorithm be only some tiny 8 >> 0 too large. In other words, we use e, + 8 as a gap in the algorithm. Still, this implies that our threshold max(BBF(())ccc cn + 5) after the waiting time satisfies
max(BSF(T)) en 8) 2 On + = wi + 8 >
2 22 2 ... 2 wx
As consequence, we end up selecting no weight at all and have E [ALG]] = 0.
This naturally motivates the need introduce robust deterministic algorithms in this setting. In Section 4 we will show that a slight modification in the algorithm and its analysis allows to obtain robustness to errors in the predictions while simultaneously outperforing 1/e for accurate gaps.
4 Robustness-Consistenn Trade-offs
Next, we show how to slightly modify our algorithm in order to still beat 1/o when getting the correct gap as input, but still be constant competitive in case the predicted gap is inaccurate. The modification
5

---

leads to Algorithm 2 Initially, we run the same algorithm as before. After some time 1 7, we will lower our threshold order hedge against an iecrrect prediction.
Algorithm 2 Robust-Consistent Algorithm
Input: Predicted gap é, times E [0, 1), v E [0, 1 Before time 7:
Observe weights we
At time T: Between time 7 and time 7 After time 1 7-7
Compute BSF(() = ma
Accept first element with wy (T),
Accept first element with 2 BSF
Note that by 7 E [0,1- we ensure that T < 1 - i.e. the waiting time is not after time 1 and hence, the algorithm well-defined. Now, we can state the following theorem which gives guarantees the consistency and the robustness of Algorithm 2 We will discuss afterwards how to choose T and y in order to outperform the classical bound of 1/e by a constant for accurate predictions while ensuring to be constant-robus at the same time.
Theorem 5. Given a prediction č for the additive gap ck2 define
01 = 7 In (1-7) and
022 (1 71 7) In (+) + In (
2h (1 (1 +)*+ and a4 = 3 (+) (1-
03
Then, Algorithm is (i) min (min (a1, max (a3, a=o)-ccosistent and (ii) (7 In 1-
robust.
Observe that we do not trust the prediction at all, we could set r = 1/c and 1 1-7 -y 1/8. Doing so, do not use the prediction in algorithm. Still, for these choices, recover the guarantee from classical secretary of 2/c. In other words, we can interpret as a trust parameter for the prediction which also mirrors our risk appetite. If we do not trust the prediction all or if we highly risk averse, we can set 1 1-7- y R If we are willing to suffer lot in case of an inaccurate prediction (or if we have high trust in the prediction),
will set 7
Theorem yields a trade-off between robustness and consistency. In particular, for a fixed level of robustness, can choose the optimal values for and y for the bounds in Theorem 5 to obtain the plot in Figure Observe that when not focusing on robustness (i.e. choosing robustness being achieve consistency approximately matching the upper bound of 0.5736
equal to zero), described in Section 1.2
Pareto frontier of robustness vs. consistency
0.55
0.50
Consistency
0.40
0.35
0.30
0.5
0.00
0.05
0.10
0.15
0.20
0.25
0.30
0.35
Robustness
Figure 1: Choosing the optimal parameters T and 1 for our analysis in Theorem 5 For a given level of robustness, what is the best consistency we can obtain with our analysis.

---

The proof of Theorem 5 can be found in the full version [Braun and Sarkar 2024]. Concerning robustness, we can only obtain a reasonable contribution by accepting the best weight. Therefore, we derive a lower bound on the probability of accepting the highest weight via Algorithm 2 Concerning consistency, we can perform case distinction whether wi is small or large. Crucially, one is required to take the drop in the threshold after time 1 7 into account.
For example, when using a waiting time т 0.2 in Corollary independent of the index and a value of y = 0.6, i.c. 1 -- 7 0.4, we get the following: Algorithm is approximately 0.383 consssenstt and 0.183-robust (also see Figure 2
Consistency
Pobustness
0.5
0.4
Competitive Ratio
0.1
0.0
0.2
0.4
0.6
0.8
1.0
Choice of 1-y
Figure 2: Trade-off between robustness and consistency as a function of the time 7 for fixed choice of r = 0.2.
In particular, we can outperform the prevalent bound of 1/c by constant if the predicted gap is accurate while ensuring to be constant competitive even if our predicted gap is horribly off. Of course, when being more risk averse, one could also increase the robustness guarantee for the cost of decreasing the competitive ratio for consistent predictions
We highlight that these guarantees as well as Theorem 5 hold independent of any bounds on the егror of the predicted gap. However, it is reasonable to assume that we have some bounds on how inaccurate our predicted gap is (for example, our predicted gap is learned from independent random samples). We show in Section 5 that we can achieve much better competitive ratios when we know a range for the error.
Improved Guarantees for Bounded Errors
Complementing the previous sections where we had either access the exact gap (Section 3 or no information on a possible error in the prediction (Section 4 we now assume that the error is bounded 6 That is, we get to know some čj E [ck - E; Ck + <] which is ensured to be at most an e off. Also, the bound on the eтror is revealed to us. Still, the true gap remains unknown.
Our algorithm follows the template which we discussed before. Still, slightly perturb č ensure that the threshold is not exceeding W1- This algorithm allows to state an approximate version of Theorem 4 for the same lower bounds of in the exact gap case.
*We can also slightly improve the trade-off by allowing randomization: Flip (biased) coin and either choose our algorithm from Section 3 or the classical secretary algorithm which achieves a guarantee of 1/s. Our deterministic approach is approximately as good as this randomized variant if we use an unbiased coin and even better compared to biasing the coin towards the algorithm using the prediction. When using bias towards the classical algorithm, the randomized algorithm has better trade-off than our deterministic approach.
"In order to distinguish a bounded error from a possibly unbounded one, we use č instead of é for the predicted gap in this section.
7

---

Algorithm 3 Secretary with Bounded Prediction Error
Input: Approximate gap time T E [0, 1J. error bound
Before time T: Observe weights W/ At time 7: After time T.
Compute (TF = max W;
Accept first element with w, 2 2
Theorem 6. Given any prediction of the gap Th E [ch
6 + where Cp WK, Algorithm
3
1/k
1/k
satisfies E [ALG] 2 a w1 - 2e. For T = 1- K+1
a 2 max 0.4, 2
and for
K+1
-02.2 0.4.
As consequence, the guarantees from the exact gap case in Section 3 carry over with an additional loss of 2e. Also, the results when not knowing the index it carry over. In particular, this nicely complements the robustness result from Theorem reasonable range, even not knowing the gap exactly does not cause too much an issue. The proof of Theorem 6 can be found in the full version [Braun and Sarkar 2024
follows: Once we can bound the error in
6 Simulations
In order to gain more fine-gra fine-grained understanding of the underlying habits, we run experiments with simulated weights and compare our algorithms among each other and the classical secretary algorithm [
In Section 1 compare our Algorithm to the classical secretary algorithm. To this end, we draw weights i.i.d. from distributions and execute our algorithm and the classical one. As it will turn out, instances which are hard in the normal secretary setting (i.e. when not knowing any additive gap) become sigmificantly easier with additive gap; we can select the best candidate with much higher probability. We also demonstrate that for some instances, knowing the gap has a smaller impact, though our Algorithm still outperforms the classical one.
Second, in Section 6.2 turn towards inaccurate gaps and compare Algorithm I developed in Section 3 to the robust and consistent variant of Algorithm 2 from Section As matter of fact, we will see that underestimating the exact gap underestimating the gap implies a smooth decay in the competitive ratio while overestimating can immediately lead to huge drop.
much of issue as an overestimation. In partieular,
6.1
The Impact of Knowing the Gap
We compare our algorithm with additive gap to the classical secretary algorithm (see e.g. [Dynkin 1963)) with a waiting time of 1/e.
6.1.1
Experimental Setup
We the comparison three different classes of instances:
Pareto: We first draw some 0 ~ Pareto(5/n, 1). Afterwards, each weight w; is determined
follows: Draw Y; Unif[0, 0] i.i.d. and set w, Y (n).9) (for more details on Pareto distributions and secretary problems, see e.g. Ferguson 1989
(ii) Exponential: Here, all w; Exp(1).
(iii) Chi- Uhi-Squaee:: Draw (10). That is, each ws is drawn from a chi-squared distribution which sums over ten squared i.i.d. standard normal random variables.
'All experiments were implemented in Python 3.9 and executed on machine with Apple MI and 8 GB Memory.
As the piece of information we use as a prediction fairly different to the pieces which were used in the literature before, we will not compare our algorithms to other algorithus from the secretary problem with predictions literature.

---

For each class of instances, we average over 5000 iterations. In each iteration, we draw n = 200 weights i.i.d from the respective distribution together with 200 arrival times which are drawn i...d. from Unif(0, 1]. The benchmark is the classical secretary algorithm with a waiting time of r 1/e: Set the largest weight up to time 7 as threshold and accepts the first element afterwards exceeding this threshold. Algorithm is executed with waiting times T = 0.2 as well as = - (/++1)** 1/2.
6.1.2 Experimental Results
When weights are sampled based on the procedure explained in (i), we observe an inter- esting phenomenon (see Figure B) For the classical secretary algorithm, we achieve ap- proximately the tight guarantee of 1/c. Our algorithm, however, achieves a competitive ra- tio of approximately 0.8 for we improve the competitive ratio for large k while suffering a worse ratio for small
0.2. When having waiting time depending k,
This can be explained follows. Weights which are distributed according to (i) almost always have a very large gap between the highest and second highest weight. Hence, no matter which gap we observe, it will always be sufficiently large exclude all ele- ments except the best one. Therefore, we only incur loss if we do not accept anything (which happens if
Competition naht
and only if the best element arrives before the waiting
time). As a consequence, for T 0.2, we observe the ratio of 0.8 (which is the probability of the highest weight arriving after time 7). For the waiting times depending on k, the waiting time turns out to be larger for smaller & and vice versa. The improvement in the competitive ratio for large k comes from the reduced waiting time and hence smaller probability of facing an arrival of during the waiting period.
0.
Addlivv uus -
Addition gep with 1- leby!"
Benchmark without gop
100
125
250
Figure 3: Competitive ratios for weights
Interestingly, this shows that there instances for which the classical secretary algorithm almost obtains its tight guarantee of 1/e while these instances become easy when knowing an additive gap. As a side remark: One might wonder if is always true that the index
based on (i). On the r-axis, we have the index k from 2 to n. The y-axis shows the competi- tive ratios.
k does not play pivotal role when using constant waiting time т = 0.2. In the full version Braun and Sarkar 2024). we show that this is not the case for exponentially distributed weights in (ii) or Chi-Squared distributed ones as in (iii).
6.2 Dealing with Inaccurate Gaps
In order to get better understanding concerning inaccuracies in the gap, we run simulation with different errors.
6.2.1 Experimental Setup
Again, we average over 5000 iterations. In each iteration, we set n = 200, draw arrival times as before and weights as follows:
(iv) Exponential: Here, all wo Exp(1).
(v) Exponential with superstar: Here, w; Exp(1) for weights and we add superstar element with weight 100 max; wi
We compare Algorithm to Algorithm both with waiting time r = 0.2. In addition, Algorithm will drop the gap from the threshold after a time of -7 0.95. in other words y = 0.05.
The comparison is done for three different gaps: small one where largest and second largest element, Ao = n/2 and k multiplication factor a for the error, we feed our algorithm with a predicted gap és a C₁ for a
2, i.e. the gap between the i.e. the gap to the smallest element. Given
going from zero to three in step size of 0.1. In other words, for 1, we get accurate gap, for

---

< 1, we underestimate the gap, for a > we overestimate the gap and for o = 0, the algorithms are equivalent the classical secretary algorithms with waiting time T.
6.2.2 Experimental Results
For exponentially distributed weights (see Figure we can observe that underestimat- ing the gap does not cause too many issues. particular, when highly underestimat- ing the gap (i.e. a < 0.5), both algorithms achieve a competitive ratio of approxi- mately 0.65, similar to an algorithm not knowing any gap. For an accurate gap. a 1. larger gaps
more helpful Still, a > I introduces a transition. For a > and gaps between the best and small element (e.g. = 100 or = 200), overestimating the gap re- duces the selection probability of any weight of Al- gorithm to zero: The predicted gap simply too large and exceeds w1. Still, Algorithm i ro-
they block more elements from being considered.
Comperiee nato
bust in a sense that we still achieve a competitive ratio of approximately 0.15. This constant depends on our choice of y. As mentioned before, there the natural trade-off:: Increasing ? for improved robustness and suffer a decrease in the competitive ratio for =
0.4
K-2
0.05
0.2
L-100 ym
k-100
0.0
k-200
Interestingly, for the gap between the best and second best element, both algorithms much more robust. This can be explained as the gap is small this case anyway, overestimating by factor of three does not cause too much issues yet. One would require to overestimate by much larger factor here to a significant difference in the performance of both algorithms.
gap
Figure 4: Competitive ratios for weights
based on (iv). The æ-axis shows a, where the predicted gap â used by the algorithms satisfies é Cj for 3).
the full version [Braun and Sarkar 2024 we show
what happens when shifting our perspective towards the more adversarial setting of exponential weights with one additional superstar as listed in (v). Here, the drop when overestimating is even more significant. Still, Algorithm 2 achieves the desired constant competitive ratio even if gaps fairly inaccurate. However, the trade-off between consistency and robustness plays a much more important role in the choices of and here.
7 Conclusion and Future Directions
As we have seen, single simple piece of information of the form "There is a gap of e in the instance" helps improve the competitive ratio for the secretary problem. In addition, our algorithm can be made robust against inaccurate predictions without sacrificing too much in the competitive ratio.
Our results directly impose some open questions for future research. First, guarantees seem be not tight. Can we achieve a better competitive ratio for any gap? Or is there a matching hardness result? As second open question, the gaps that consider a generalization, one could consider arbitrary gaps w: Wy for some < i < < n. Can we do something in this regime? (as sketched in the full version [Braun and Sarkar 2024
of the form wi wy for some k. As
for e.g.
W3 0).
Also, going beyond the single selection problem is interesting, for example by considering the multi-selection variant. For this, we give a reasonable starting point in the full version [Braun and
Sarkar 2024
10

---

Acknowledgments and Disclosure of Funding
The authors would like to thank Thomas Kesselheim for very helpful discussions on the secretary problem as well as suggestions on different models of advice. Also, many thanks to the anonymous reviewers for helpful feedback and remarks concerning previous versions of this paper. This work was done in part while the authors were visiting the Simons Institute for the Theory of Computing. Alexander Braun has been funded by the Deutsche Forschungsgemeinschatt (DFG, German Research Foundation), Project No. 437739576.
References
S. Ahmadian, H. Esfandiari, V. Mirrokni, and B. Peng. Robust load balancing with machine learned advice. J. Mach. Learn. Res., 24:44:1 14:46,, 2023. URL http:///jar..org/ppperss. 92-0629.html
Agorithns-with-Peeciccion Website with list of papers on algorithms with predictions. URL https://algorithmms with hetcc--preicciooss. git.ub..bi.o.
M. Almanza, F. Chicrichetti, S. Lattanzi, A. Panconesi, and G. Re. Online facility location with multiple advice. In M. Ranzato, A. Beygelzimer, Y. Dauphin, Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 4661-4673. Curran As- sociates, Inc., 2021. htLL/attpp:/procceddiig neurid file/250477494b2455 20a7 www0aaae88822e61111---------- www..pp..ccpppprreeeee..... forrrffleee pwwes//apeee///11..
neurips
pdf
S. Angelopoulos. Online search with hint. In J. R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, Jamuary 6-8, 2021, Virtual Conference, volume 185 of L.Plcs, pages 51:1-51:16. Schloss Dagstuhl Leibnniz-ZZntruu für Informatik, 2021. doi: 4230/LIPIcs. ITCS 2021.51
10.4230/LIPICS.ITTO ITCS .1.. URL
A. Antoniadis, T. Gouleakis, P. Kleer, and P. Kolev. Secretary and online matching problems with machine learned advice. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 7933-7944 Curran As- sociates, Inc., 2020. URL URRLattsps://rrrcceeing.. www.:gs..eerip.....o wwwp:ppp.ccppppp..cpp http://ewwp.pccpppeeeeeeeeeeeeee http:ppprr..iilleeepeeee///
pdf
A. Antoniadis, J. Boyar, M. Eliás, I., M. Favrholdt, R. Hoeksma, K. S. Larsen, A. Polak, and B. Simon. Paging with succinct predictions. In A. Krause. E. Brunskill, K. Cho, Engelhardt, Sabato, and J. Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 952- 968. PMLR, 2023. URL htttps://proceeee/ee mww.iiiinnnmmm.......mmmmm.mmmrm www.eppeesss2.... hwtp222/antonaaiiii.o antoniadis23a: html
C. Argue, A. Gupta, M. Molinaro, and S. Singla. Robust Secretary and Prophet Algorithms for Packing Integer Programs, pages 1273-1297, 2022. doi: 10. 1111177777.788111117777573355 URL https://epubs.. si am. org/ doi. abs/ 1117/111777711111111
H. Asi, V. Feldman, T. Koren, and K. Talwar. Private online prediction from experts: Separations and faster rates. In G. Neu and L. Rosasco, editors, The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12-15 July 2023. Bangalore, India, volume 195 of Proceedings of Machine Learning Research, pages 674-699. PMLR. 2023. URL htt.ttps//prcccedingge www.m / v195/as 23a. html
M. Babaioff, N. Immorlica, D. Kempe, and R. Kleinberg. A knapsack secretary problem with applications. M. Charikar, Jansen, O. Reingold, and J. D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 10th International Workshop, APPROX 2007, and Iith International Workshop, RANDOM 2007, Princeton, NJ, USA, August 20-22, 2007, Proceedings, volume 4627 of Lecture Notes in Computer Science, pages 16-28. 28. Springer, 2007. doi: 10. 10.10007/78-335440 74208--0-7----81 2 978 3- 540--8888777
M. Babaioff, N. Immorlica, D. Kempe, and R. Kleinberg. Matroid secretary problems. J. ACM, 65 (6), nov 2018. ISSN 0004-5411, doi: 10.1 15.222/222251.. URL. 3212512

---

Z. Benomar and V. Perchet. Non-clairvoyant scheduling with partial predictions. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024. URR.htttps://ppeneeees
net/forumm'd=;
D. Bradac, A. Gupta, S. Singla, and G. Zuzic. Robust Algorithms for the Secretary Problem. In T. Vidick, editor, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151 of Leibniz International Proceedings in Informatics (LIPles), pages 32:1-32:26, Dagstuhl, Germany, 2020. Schloss Baastuhl-Leiiniz-ZZenn 95977-134-4, doi: (0-4230/..PIcs..TCS3.2000 volltexxte/222/1177
fuer Informatik. ISBN 978-3-
URIhtttps /tittps:/ddros...o dagstuhl. .eeiiihlde//pppuu de/opus/
A. Braun and Sarkar. The secretary problem with predicted additive gap, 2024. URL https
//arxiv. org/ 2409 20460
N. Buchbinder, K. Jain, and M. Singh. Secretary problems via linear programming. Math. Oper. Res., 39())190-2066, 2014. doi: 10. 20.188/m00r.2013.0044.. URL httLhttt:////ii.rrrg 1287 /mo0//morr 2013.
T. H. Chan, F. Chen, and S. H. Jiang. Revealing optimal thresholds for generalized secretary problem via continuous LP: impacts on online K-item auction and bipartite K K-matching with random arrival order. In P. Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms,, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1169- 1188. SIAM, 2015. doi: 011133/1.788111197777777 9781611973730.777
UtLpttps::
org 10. 1137/1 3rg/1..1137/1
Correa, P. Dütting, F. Fischer, and Schewior. Prophet inequalities for w..d. random variables from an unknown distribution. In Proceedings of the 2019 ACM Conference on Economics and Computation, EC '19, page 3-17, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 978 1499369929. doi: 10. 10.1145/3328526.3329662 10. 1i.1145/33282666 2222322222266362277777 3329627
https:/:::///o org/
R. Correa, A. Cristi, B. Epstein, and J. A. Soto. Sample-driven optimal stopping: From the secretary problem to the i.idd prophet inequality. CoRR, abs/2011.06511 2020. URL https //arxiv. org/ htt.s///11.00.....
J. R. Correa, A. Cristi, L. Feuilloley, T. Oosterwijk, and A. Tsigonias-Dimitriati The secretary problem with independent sampling. In D. Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 13, 2021, pages 2047-2058. SIAM. 2021. doi:
URL https:///os http:///oooooo///////
L137/1.97816119766
122
Dütting, S. Lattanzi, R. Paes Leme, and S. Vassilvitskii. Secretaries with advice. In Proceedings of the 22nd ACM Conference on Economics and Computation, EC '21, page 409-429, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 978145038554 doi: 011453465456.34676666
URL htthhtps:: //doi. org /00 1145/3465456..... 3467623
E. B. Dynkin. The optimum choice of the instant for stopping a markov process. Soviet Math. Dokl, 4:627-629, 1963.
M. Feldman, O. Svensson, and R. Zenklusen. A simple Ollo comprinn algorithm for the matroid secretary problem. Math. Oper. Res., 43(2))638-650, 2018. doi: 10.12887moor.22117.88 URL httph:ttt//ooott ottp//...rg/1... 2287/moor 2017 0876
T. S. Ferguson. Who solved the secretary problem? Statistical Science, 4(3):282-289, 1989. ISSN 08834237.
R. Freeman. The secretary problem and its extensions: A review. International Statistical Review / Revue Internationale de Statistiquee, (1(2):189-2)2 8968809999660090 1983. ISSN 03067734, 17515823.
K. Fujii and Y. Yoshida. The secretary problem with predictions. CoRR, abs/2300.0822000 2023. doi: (0.48550/ARXI..2306.000 08340. URL http:/tttt//oooorrgr 40te//00.4450///00 arr.i..iiiv.v..... 2306 08340
Gilbert and Mosteller. Recognizing the maximum of sequence. Journal of the American
Statistical Association, 61(3133)35-73, 1966. ISSN 01621459.
12

---

S. Im. R. Kumar, M. Montazer Qaem, and M. Purohit. Online knapsack with frequency pre- dictions. In M. Ranzato, A. Beygelzimer. Y. Dauphin, P. Liang, and W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 2733-2743. Curran As- sociates, Inc., 2021. URL StsLlattts//proccddingge wtwprreeeednnnnn..u.eererere neurips wwwpcc/pppppp....c..e httpppppprrreeeeeeee/e files/ (ttpeerffiless/ape//0000 paper/2021/ file/161c5c5ad55 c5874477555 http:/990055111000-0-0------- pdf
S. Im, R. Kumar, A. Petety, and M. Purohit. Parsimonious learning-augmenter caching. In K. Chaud- huri, S. Jegelka, L. Song, C. Szepesvári, G. Niu, and Sabato, editors, International Confer- ence on Machine Learning. ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages httpps///proceedinggs mlr prress/v12//mm226 httpa//........eerrr///////aaaaa html
PMLR, 2022. URL
H. Kaplan, D. Naori, and D. Raz. Competitive Analysis with a Sample and the Secretary Problem. pages 2082-2082000000022 2095. 2020. doi: 10.1137/1.978111 197599444 URL https://epubs siam. org/ doi/abs 10. 1137/ 1 9781611975999 128
T. Kesselheim and M. Molinaro. Knapsack Secretary with Bursty Adversary. In A. Czumaj. A. Dawar, and Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 of Leibniz International Proceedings in Informatics für URL https
(LIPlcs), pages 72:1-72:15, Dagstuhl, Germany, 2020. Schloss Dagstuhl Informatik. ISBN 978 978-3-95977-138-2 /drross.dggstun http://aasstaaaooooo////oo//oo//
doi: 12479
T. Kesselheim, K. Radke, A. Tönnis, and B. Vöcking. Primal beats dual on online packing lps in the random-orde order model. SIAM Journal on Computing, 47(5); 1939-1964, 2018. doi: 10.1137/ 15M1033708. URL httpps://oii..... org/ 10. 11e1111371550 1
R. Kleinberg. A multiple-choice secretary algorithm with applications online auctions. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '05 page 630-631, USA, 2005. Society for Industrial and Applied Mathematics. ISBN 08987 15857.
R. D. Kleinberg and F. T. Leighton. The value of knowing a demand curve: Bounds regret for online posted-price auctions. In 44th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 2003, Cambridge, MA, USA, Proceedings, pages 594 IEEE Computer Society, 2003. doi: 10.1109/SFCS 2003. 1238232. URL https: htt/////...o//...00/////////// 2003. 1238232
N. Korula and M. Pál. Algorithms for secretary problems on graphs and hypergraphs. In Proceedings of the 36th Internatiional Collogquium on Automata, Languages and Programming: Part I1, ICALP '09, page 508-520. 520. Berlin, Heidelberg, 2009. Springer- Verlag. ISBN 9783642029295. doi: 10. 1007/978- 042-02930--111111 42.. URL https: org
10. 100gg///.....
T. Lavastida, B. Moseley, R. Ravi, and C. Xu. Learnable and Instance-Robuue Predictions for Online Matching, Flows and Load Balancing. In P. Mutzel, R. Pagh, and G. Herman, editors, 29th Anmual European Symposium on Algorithms (ESA 2021), volume 204 of Leibniz International Proceedings in Informatics (L/Plcs). pages 59: 1-59:17, Dagstuhl, Germany, 2021. Schloss Dagstuhl Leibniz- Zentrum für Informatik. ISBN 978-3-95977-20444, doi: 1Pt.s//IPPcssSSSSS...
URL
https://drron dagstuhl de
http:/000.4433// 4230/LIPICs ESA. 2021. .59
R. P. Leme, B. Sivan, Y. Teng, and P. Worah. Pricing query complexity of revenue maximization. In N. Bansal and V. Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 399 415. SIAM, 2023. doi: 10.1 10.1137/1.788161197755.8
10. 1137/1 978161197755 URL htllhtts::/ddd //do: 0ttg//.0..1971.991111177777...
ch17
D. V. Lindley. Dynamic programming and decision theory. Journal of The Royal Statistical Society Series C-applied Statistics, 10:39-51, 1961.
Lykouris and S. Vassilvitskii. Competitive caching with machine learned advice. ACM, 68(4): 24:1-24:25, 2021. doi: 10. 10.1145/344779. URL htttps://d/l org/oog////o httg//...1/////0... 1145/3447779
13

---

M. Mahdian and Q. Yan. Online bipartite matching with random arrivals: An approach based on strongly factor-revealing Ips. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC *11, page 597-606, New York, NY, USA, 2011. 1. Association for Computing Machinery. ISBN 7781450330911. doi:
1tt15//1193336.1999977 URL.
https://doi. org/10. 10. 114469999666... 1993716
M. Purohit, Z. Svitkina, and R. Kumar. Improving online algorithms via ML predictions. In S. Bengio, H. M. Wallach, H. Larochelle, K. Grauman. N. Cesa-Bianchi, and R. Garnett, ed- itors, Advances in Neural Information Processing Systems 31: Annual Conference ral Information Processing Systems 2018, NewrIPS 2018, December 3-8, 2018, Montréal, Canada, pages 0684-9695 2018. URL UtL.ittps://ppoceddnn http://oooooddnn....neerr....ppp cc/ http//ppperr/22/ haap://622222a666022222222211113
Neu-
html
A. Rubinstein. Beyond matroids: Secretary problem and prophet inequality with general constraints. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC '16, page 324-332, New York. NY, USA, 2016. Association for Computing Machinery. ISBN 9781450341325. doi: 10.1145/2897518888877888 28875400 [tttpss::://d/ org/10 10. 1145/2897518 2897540
A. Wei and F. Zhang. Optimal robustness-consistene trade-offs for algorithms. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS'20 20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 978171382999
online
A. Zeynali, B. Sun, M. Hajiesmaili, and A. Wierman. Data-driven competitive algorithms for online knapsack and set cover. Proceedings of the AAAI Conference on Artificial Intelligence, 35(12): 10833-10841, May 2021. doi: 10. 11t1///aa...3.............. index.
URL https://oo]: .wa.s.aaaaa........ org/
14

---

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

---

Answer: [Yes]
Justification: Assumptions are mentioned clearly with the respective statements. Proofs are provided mainly in the appendix due space constraints.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: The paper provides all information such that the simulations can easily be
reproduced. Algorithms should be easily implementable within a few lines, sample sizes and distributions are stated.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
16

---

reproducible, they 5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [No]
Justification:
We will make the code and data publicly available after the review process.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nnis.co cc/
public/guides
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
7/nips cc/ wtc/ppbliic// cobollccggiddsss gww.///ieee//eee// Codeeoomiiieeeee /ec//e/uuuS//oouubniiiii SanSSuubissss solbbmmsssioo ssiosoolicyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: There was no training, neither a testing phase. Simulations only contain samples from distributions and the performance of our algorithms.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[NA]
Justification: See answer of Question 6.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
17

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Hardware settings are provided as a footnote in the main body the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:///wwuurrre.cccc//aaa//c/aa
Answer: [Yes]
Justification:
The research conforms with the Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The goal of our paper is gain a better understanding of different kinds of predictions compared to the ones studied in the literature before. There are no further societal consequences beyond those for algorithms with predictions.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
18

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper does not pose any risks. There further consequences beyond those for theoretical results on algorithms with predictions.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use any code or data from previous work.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
19

---

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

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
21


Reviews:
[{"review_id": "X4RIAWbQpJ", "reviewer": "Reviewer_QX7w", "summary": "This paper considers the value maximization version of the secretary problem with additional information of the gap between the best and second best values. The first main contribution of this paper is that this additional information makes it possible to design a $0.4$-competitive algorithm. The second main contribution is a robustness-consistency trade-off; if the predicted gap is correct, then the algorithm achieves better than $1/e$-competitiveness and otherwise, it achieves a constant-factor competitiveness. The authors also provide empirical results that show the effectiveness and error-robustness of the proposed algorithm.", "questions": "Is it possible to plot the robustness-consistency trade-off (x-axis: robustness, y-axis: consistency) obtained when you choose optimal $\\tau$ and $\\gamma$?", "limitations": "This paper has no ethical issue.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "While the existing studies on learning-augmented secretary problems assume predictions of the maximum value or all values, this paper's setting considers only a smaller piece of predictions. This paper provides an interesting new result of learning-augmented secretary algorithms. The main idea of the proof is simple and clean. This paper is well-organized and easy to follow.", "weaknesses": "- The main idea of the proof is elementary. I do not think it is trivial, but the proof technique itself is not so surprising. \n- Since the main difficulty of the secretary problem lies in uncertainty of the scale of values, it is not surprising that the additive gap improves the competitive ratio.\n- The result on bounded errors (Section 5) seems to be obtained just by replacing a predicted gap with its erroneous version in the main proof.\n- I do not know any realistic scenario in which the predicted additive gap is obtained but not the predicted maximum value.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Please find a plot for the Pareto frontier of the robustness-consistency trade-off in the attached document. When being (close to) zero-robust, we obtain a consistency which is close to the mentioned $0.5736$ upper bound. On the other hand, we obtain guarantees of $\\approx 1/e$ robustness and consistency as expected.\n\nOf course, we are happy to add/exchange the plot in the final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yAT7GNHQAW", "reviewer": "Reviewer_wmbT", "summary": "This work considers the classical secretary problem in an online decision making with hints setting, where the objective is to select the element with highest weight from an online, random-order stream of elements with adversarially chosen weights, where the decision to select or reject elements is irrevocable. This is a well studied problem, and there is a simple threshold based algorithm that achieves a tight competitive ratio of $1/e$. This paper considers this problem in a learning with hints setting, where the learner is given access to an additional piece of information, which in this paper is assumed to be the gap between the weight of the highest weight item and the $k^{th}$ highest weight item for some $k$. The authors show that this additional piece of information suffices to design an algorithm that breaks the classical $1/e$ competitive ratio barrier (in the no-hints setting) by a constant factor. \n\nIn particular, their algorithm achieves a competitive ratio of $\\max(0.4, 0.5(k+1)^{-k^{-1}})$ when the exact gap between the weights of the best and $k^{th}$ best item are known exactly, along with the value of the index $k$, and a competitive ratio of $0.4$ when only the exact gap is known, but not the index $k$. In the case where the provided gap may be erroneous, they given an algorithm with fairly non-trivial robustness vs consistency tradeoffs. Lastly, in the case of bounded errors with a known error bound $\\epsilon$, they give an algorithm that achieves a competitive ratio that is nearly $0.4$, with a small additive loss of $2\\epsilon$. All algorithms are deterministic, and basically simple variants of the classical threshold based strategy that achieves the $1/e$ competitive ratio in the classical no-hints setting.", "questions": "What is the broader impact of this work to the online learning with hints literature? Does it have any implications beyond this particular problem studied in this paper? Are the algorithmic ideas or proof techniques more generally applicable to other online learning with hints problems?", "limitations": "I do not have any major concerns about the negative impact of this work. My only concern is its broader applicability. See weaknesses.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is very well written and easy to follow. All proofs, to the best of my understanding, are correct, and the algorithms are very simple and intuitive. They are basically simple variants of the threshold based strategy for the classical no-hints setting.", "weaknesses": "While I find the theoretical contributions of this paper to be sound, I am not entirely certain about its novelty or impact to this space of online learning/ learning with hints. However, I must say that while I am quite familiar with research in the online learning space, as well as the secretary problem and its variants, I am not quite up to date with very recent research in this learning with hints space.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Our main contributions are twofold: From a conceptual point of view, our work emphasizes and justifies to study weak prediction models. This question can of course also be asked for other online (learning) problems. For example, it is easy to see that the canonical $1/2$-tightness instance in Prophet Inequalities can easily be solved with additive gaps. \n\nSecond, from a technical contribution, the underlying algorithmic ideas (e.g., incorporating a gap in the algorithm) can also be applied to other classes of online selection problems (in addition to the mentioned Prophet Inequalities also to Pandora's Box,... ).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vhdje6rfne", "reviewer": "Reviewer_rRpH", "summary": "This paper studies the famous secretary problem under the setting with predictions: some extra advice (presumably generated by some machine learning algorithm) that enables the algorithm to do well when this advice is accurate (consistency), but will not force the algorithm to do poorly if it is inaccurate (robustness).  There have been quite a few previous papers on the secretary problem with predictions, which have studied a variety of different predictions and settings.  However, essentially all of these previous papers have used \"strong\" predictions, e.g., some extra information about every secretary.  This paper asks a slightly different question: what is the \"weakest\" piece of information that still allows us to do better than the classical $1/e$ bound?  They propose the \"predicted additive gap\": the difference between the largest weight and the $k$'th largest weight for some $k$.  They give a few results about this prediction:\n- If we are given such a gap, then even if we do not know $k$, we can get competitive ratio at least $0.4$ (notably better than $1/e$).\n- If we are given an incorrect gap but also an upper bound $\\epsilon$ on its (additive) distance from a true gap, then we can get $0.4 OPT - 2\\epsilon$ in expectation.  \n- If we are given an incorrect gap and do not have a bound on its error, we can design an algorithm that gets $1/e + O(1)$ if the gap is correct and $\\Theta(1)$ if it is not.", "questions": "- Do any of your algorithms have bounds that are a function of the (unknown) error?\n- Why is it reasonable to think that we might have a good prediction for the additive gap?", "limitations": "This is fine.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall, I like this paper and think that it should be accepted, although it has a few weaknesses.  Its strengths include the following.\n- The question of \"are there very weak pieces of information that still allow for nontrivial improvement?\" seems quite interesting to me and pretty novel.  There is a line of work on \"advice complexity\" for a variety of problems, which asks for the minimum number of bits necessary to get useful information, but \"# bits\" is not always the right metric for strong or weak.  For example, knowing precisely the max weight is a small number of bits, but is a much stronger piece of information that an additive gap.  I completely agree with the authors that an additive gap seems like a weak piece of information, and it is somewhat surprising (though not hard in retrospect) that an additive gap is sufficient to do better than $1/e$.\n- The algorithms are reasonably natural, which is always a plus.  \n- The secretary is so fundamental, and the predictions setting is so popular, that anything interesting about secretaries with predictions is a good contribution.", "weaknesses": "- I am somewhat unimpressed by the \"consistency vs robustness\" phrasing.  In particular, it is extremely binary: either the prediction is perfectly accurate or it is not.  Instead, the more modern way of analyzing algorithms with predictions is to analyze the quality of the algorithm as a function of the prediction error.  So then \"robustness\" would just correspond to the behavior when the error tends to infinity.  This paper only provides such an analysis when we know an upper bound on the error, and then use that upper bound in the algorithm.  It would have been much more interesting (and stronger) to give an algorithm which does not have such an upper bound, but where the behavior is still a function of the error.  \n- While the motivation for this paper is to give the weakest prediction that is useful, when doing algorithms with predictions there is usually some discussion of why the prediction is \"reasonable\".  Why is it reasonable to think that we might know (or have a good guess for) the additive gap?  I don't see any discussion about this in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The additive gap is a useful piece of advice when we are concerned about data privacy; for example, when we only have access to a translation of previous instances: instead of seeing $w_i$, we see $w_i - X$ where $X$ is some random shift of all the values. In this way, the maximum weight element is hidden; however, we present an algorithm which can still use this data. More generally, algorithms which are still able to perform with weak pieces of advice have the advantage of being amenable to obfuscated data.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "thPYitGtt3", "reviewer": "Reviewer_jGey", "summary": "The paper examines the value maximization secretary problem, where values $w_1 \\geq \\ldots \\geq w_n$ are observed in a uniformly random order, and investigates how the optimal competitive ratio of $1/e$ can be improved in a learning-augmented setting with predictions about an additive gap. Specifically, the authors demonstrate that, given the value of any additive gap $c_k = w_1 - w_k$, even with $k$ unknown, the competitive ratio can be improved to $0.4$. Furthermore, if $k$ is known along with $c_k$, an even better competitive ratio, dependent on $k$, can be achieved. When only a prediction of $c_k$ is provided, the authors adapt the algorithm to ensure robustness against potentially erroneous predictions. Finally, they conduct simulations that confirm their theoretical findings and validate the effectiveness of the proposed algorithms in practice.", "questions": "See the weaknesses.", "limitations": "The assumptions of the theorems are clearly stated.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* The paper is well-written, with a good balance between technical results and intuitive explanations of the problem.\n* The theoretical results are interesting\n* The new type of advice presented is well-motivated from both theoretical and practical perspectives.\n* The appendices present interesting follow-up research directions", "weaknesses": "* The paper does not provide any tightness results proving the optimality of the presented algorithms.\n* The bounds that depend on the error in Section 5 assume that the algorithm knows the prediction error is at most $\\epsilon$. The results would be stronger if the performance of the algorithms, without any information on the prediction quality, could be expressed as a function of the prediction error. This is a more typical criterion sought in learning-augmented algorithms: smoothness.\n\nMinor Weaknesses:\n* A major argument justifying the study of additive gaps is to explore weaker types of advice. In that sense, the paper maybe should cite previous works exploring weak types of advice. For example, \"Online Search With a Hint\" studies different types of advice and provides Pareto-optimal algorithms for each. \"Paging with Succinct Predictions\" examines advice of limited size. Other papers consider a limited number of predictions in problems with many unknown variables: \"Parsimonious Learning-Augmented Caching\", \"Advice Querying under Budget Constraint for Online Algorithms\", \"Non-clairvoyant Scheduling with Partial Predictions\", ...\n* In figures, I suggest using different line styles (for colorblind readers, black and white prints, etc.) and saving them in PDF format for better quality.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Concerning tightness of our results: the mentioned implication of the two-best secretary yields an upper bound on $0.5736$ for exact additive gaps. \n\nIn addition, we will of course address your minor weaknesses in the final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank all four reviewers for their highly valuable feedback and appreciate the positive spirit concerning the comments and remarks.

Concerning the question on guarantees as a function of an unknown error from reviewers rRpH and jGey: 
When underestimating the gap, Algorithm 1 has a smooth decay with respect to the error which is a direct consequence of our analysis. 
Still, trying to derive guarantees in general is hopeless when the error is unknown, as overestimating the gap indeed implies a huge drop in the competitive ratio (as we show in Example E.1 and in our simulations, see Figure 3 and its interpretation).
As a consequence, we restrict ourselves to the 'sharp/binary' robustness-consistency trade-off and complement this with the results for a known bound on the error.

Meta-review: This paper studies the secretary problem in the algorithms with predictions framework. In particular, it asks what is a "weak" prediction that can be used to still achieve an improved guarantee. The authors show that given only a predicted gap between the highest and k^th highest weight, it is possible to achieve a competitive ratio of 0.4, improving over the classical 1/e competitive ratio for the secretary problem. The question of identifying the weakest piece of information that allows beating the classical 1/e bound is interesting and is a different perspective from the standard approach in algorithms with predictions. The results are interesting and novel, and they are for a fundamental problem.
Decision: Accept (poster)