The Secretary Problem with Predicted Additive Gap

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.

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.

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.

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.

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.

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.