The Secretary Problem with Predicted Additive Gap

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.

Strengths

* The paper is well-written, with a good balance between technical results and intuitive explanations of the problem. * The theoretical results are interesting * The new type of advice presented is well-motivated from both theoretical and practical perspectives. * The appendices present interesting follow-up research directions

Weaknesses

* The paper does not provide any tightness results proving the optimality of the presented algorithms. * 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. Minor Weaknesses: * 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", ... * 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.

Questions

See the weaknesses.

Rating

6

Confidence

4

Soundness

4

Presentation

3

Contribution

3

Limitations

The assumptions of the theorems are clearly stated.

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: - 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$). - 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. - 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.

Strengths

Overall, I like this paper and think that it should be accepted, although it has a few weaknesses. Its strengths include the following. - 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$. - The algorithms are reasonably natural, which is always a plus. - 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. - 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.

Questions

- Do any of your algorithms have bounds that are a function of the (unknown) error? - Why is it reasonable to think that we might have a good prediction for the additive gap?

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

This is fine.

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. In 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.

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.

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?

Rating

6

Confidence

3

Soundness

4

Presentation

4

Contribution

3

Limitations

I do not have any major concerns about the negative impact of this work. My only concern is its broader applicability. See weaknesses.

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.

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. - 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. - 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. - I do not know any realistic scenario in which the predicted additive gap is obtained but not the predicted maximum value.

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$?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

This paper has no ethical issue.