acceptodds
Under review as a conference paper at ICLR 2027

The Secretary Problem with a Stochastic Signal

Abstract

Learning-augmented approaches to the secretary problem typically use value estimates, rank predictions, or explicit recommendations. We study advice conveyed solely through timing: a content-free stochastic signal that arrives no later than the best of items. Under uniformly random arrival order, we characterize the exact finite- optimal policy and success probability for arbitrary known signal distributions, assuming independence of the signal and relative order conditional on the best item's position. For the -power family, where increasing shifts the signal towards the best item's arrival, we derive optimal threshold policies and closed-form asymptotics. Specifically, the limiting success probability exceeds the classic benchmark for every , equals for the uniform case , and approaches as . We quantify robustness to misspecifying by showing that conservative estimates preserve the classic benchmark asymptotically. Under adversarial arrival order, we determine the exact worst-case guarantees for the -power family, including constant success probabilities when .

Primary area:
optimization
Keywords:
secretary, online, uncertainty, learning-augmented, predictions, stochastic

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_iQXMOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies a secretary problem in which the decision maker receives a content-free stochastic signal that arrives no later than the best item, so the information is provided in the timing. The paper characterizes optimal policies and success probabilities under both random and adversarial arrival orders.

Critical strengths

Their model is a special case of the framework of Dütting et al. (2024), whose structural results already apply. The paper’s contribution is an explicit recursion and a closed-form analysis under the additional assumption that the side information signal comes from the α\alpha-power distribution family.

I find the paper well written, with a clear problem formulation and a systematic theoretical treatment. The results are presented carefully, and the paper gives a useful characterization of how the timing of a content-free signal can improve the performance of online selection algorithms. Overall, I find the paper a solid theoretical contribution to online algorithms and optimal stopping, and I support its acceptance.

Critical weaknesses

Their model is a special case of the framework of Dütting et al. (2024), whose structural results already apply.

Questions for authors

None

1 comment
AuthorsOpenReview ↗

Reply to Reviewer iQXM

Thank you for supporting acceptance.

We agree (see updated Section 1.1) that our random-order model is a special case of the framework of Dütting et al., which assumes random order and a known distribution. Several of our results lie outside it:

  • Exact optimal worst-case guarantees under adversarial order for every nn and α\alpha (Theorems 5, 7). They vanish for α=o(n)\alpha=o(n) and tend to 1−e−c1-e^{-c} for α/n→c\alpha/n\to c.
  • The full-history separation (Section 5). Observing all mm signals cannot help randomized policies but can strictly help deterministic ones, by a factor 3/23/2 asymptotically for m=2m=2.
  • Guarantees under misspecification and learning (Theorems 3 and 17 and the new family-free result in Appendix B.1).

Within the framework, their LP computes the optimal value for each instance. The α\alpha-specific structure and closed forms require our analysis, just as their own closed forms for samples and noisy binary advice did. The revision makes this explicit.

If this addresses your concern, we would be grateful if you would consider it in your assessment.

Reviewer_JfxLOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper investigates a variant of the classical secretary problem augmented with a content-free stochastic signal. This temporal signal carries no explicit value or rank prediction but is guaranteed to arrive no later than the best item (SI). For random arrival orders, the authors provide an exact O(n2) optimal policy characterization for arbitrary known signal distributions. They further analyze an -power family of signals, deriving exact closed-form asymptotics and proving that the success probability always exceeds the classic 1/e benchmark for any >0. The paper also extends these results to adversarial arrival orders, providing exact worst-case randomized and deterministic guarantees.

Critical strengths
  • The theoretical execution is highly disciplined and mathematically tight. The derivation of the O(n2) Bellman recursion for arbitrary signal distributions is flawless and provides a strong foundation for the subsequent proofs.

  • The closed-form asymptotics derived for the -power family are elegant, cleanly demonstrating how temporal concentration shifts the success probabilities.

  • Moving beyond random-order arrivals to analyze adversarial sequences significantly elevates the theoretical contribution. Establishing the exact randomized optimum OPTnrand() and detailing the linear scaling regime =(n) provides a complete and satisfying theoretical picture.

Critical weaknesses
  • The structural novelty of the proposed algorithm is somewhat limited. The random-order signaling model functions essentially as a specialized case within the existing joint rank/signal framework introduced by Dütting et al.. Consequently, the paper reads more as a specialized, closed-form mathematical refinement rather than a breakthrough in learning-augmented algorithms.

  • The core framework relies heavily on the extremely strong oracle condition that the signal is strictly reliable (SI). From an algorithmic governance and systems design perspective, the lack of proper explainability frameworks makes this difficult to translate into deployed environments. While the theoretical robustness guarantees are sound, deploying such temporal decision-making requires deeper qualitative error analysis when real-world, asynchronous signals inevitably violate the strict theoretical assumptions.

Questions for authors

1- Can you elaborate on specific, real-world applied scenarios where the strict SI assumption is naturally guaranteed without requiring a separate, perfect oracle?

2- While the theoretical proofs are robust to parameter misspecification within the -power family, how might this framework be adapted to provide explainable failure bounds when the distribution family itself is entirely misspecified?

1 comment
AuthorsOpenReview ↗

Reply to Reviewer JfxL

Thank you for the review.

Dütting et al. Our random-order model, including the new unreliable variant, fits their framework as we describe in Section 1.1. Their LP computes the optimal value for each fixed instance. The structure and closed forms require our analysis: the switch at α=1\alpha=1, the threshold fraction (1−α)1/α(1-\alpha)^{1/\alpha}, OPT(α)\mathrm{OPT}(\alpha), and Corollary 18. Their own closed forms for samples and noisy binary advice likewise required separate analysis. The framework assumes random order and a known distribution. Hence, our adversarial-order optima (Section 4), the full-history separation (Section 5), and the misspecification and learning guarantees (Section 3) lie outside it.

Reliability. The new Theorem 4 gives the exact optimal policy for any known distribution with late, missing, or false signals. Corollary 18 makes the degradation from OPT(α)\mathrm{OPT}(\alpha) to 1/e1/e explicit for late or missing α\alpha-power signals. For any reliable signal, even with rank dependence, A(max⁡{S,kncl})\mathcal A(\max\{S,k_n^{\mathrm{cl}}\}) never does worse than the classic policy.

Q1. The assumption S≤IS\le I holds by construction when the signal is triggered by the best item at an earlier pipeline stage. For example, a platform sends an anonymous alert when its top applicant enters final processing, before that applicant is presented. No separate timing oracle is needed. We agree that in other applications this assumption can be too strong. We therefore extended our results to late, missing, or false signals (see Reliability above).

Q2. A new result (Appendix B.1) assumes only S≤IS\le I and that the signal is independent of the relative ranks given II. Then, for any signal family, A(max⁡{S,k})\mathcal A(\max\{S,k\}) succeeds with probability

1n(1{k=1}+∑i≥max⁡{k,2}E[max⁡{S,k}∣I=i]−1i−1),\frac1n\Big(\mathbf 1\{k=1\}+\sum_{i\ge\max\{k,2\}}\frac{\mathbb E[\max\{S,k\}\mid I=i]-1}{i-1}\Big),

that is, the average fraction of items before the best one that the policy skips. With probability ≥1−δ\ge1-\delta, choosing kk to maximize an unbiased estimate from mm historical pairs (I,S)(I,S) of episodes of the same length nn loses at most 2log⁡(2n/δ)/(2m)2\sqrt{\log(2n/\delta)/(2m)} against the best threshold policy.

If this addresses your concerns, we would be grateful if you would consider it in your assessment.

Reviewer_kUpWOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the secretary problem with one extra observation. Besides the item sequence, the algorithm sees a "precursor" event at time before the arrival time of the best item. Under a condition for the arrival time distribution of the precursor, the paper characterizes optimal policies and success probabilities in both random-order and adversarial-order settings.

Critical strengths

The model is simple and clean. The paper provides optimal policies in explicit form, along with matching success probabilities across random-order and adversarial-order models. The corresponding value of "precursor" information is easy to understand, which also nicely reduces to the classic setting in the limit.

Critical weaknesses

Overall, I like the analysis as a technical contribution/extension. My main question is how/why this "precursor" setting is relevant in practice. Note that this piece information is arguably strong: this is perfectly reliable that the precursor arrives before the true best item almost surely, and at least in the main model, even the probability distribution is known.

Another thing to flag is that the model primitives have been assumed as known to the DM. Hence the "information/learning" aspect is only reflected in the following way: (i) the DM can depend its action on a precursor-augmented history path and (ii) model misspecification is considered.

Questions for authors
  1. What are the practical scenarios that this specific model can be used?
  2. What if "precursor" may actually accidentally arrive later that the true best item?
2 comments
AuthorsOpenReview ↗

Reply to Reviewer kUpW

Thank you for the review.

Q1 (practice). Like the classic secretary problem, our model is deliberately stylized. The assumption S≤IS\le I holds by construction when the signal is triggered by the best item at an earlier pipeline stage. For example, a platform sends an anonymous alert when its top-scored applicant enters final processing, before that applicant is presented. We agree that in other applications this assumption can be too strong. We therefore extended our results to late, missing, or false signals (see Q2).

Q2 (late signals). Your question led to a new result (Theorem 4). For any known distribution with late, missing, or false signals that are independent of the relative ranks given II, an O(n2)O(n^2) DP recursion still gives the optimal policy. If the signal is late or missing with a fixed probability ε\varepsilon, this policy waits for the signal, but accepts records after a computable fallback time if none has arrived. For α\alpha-power signals, the limiting optimal success probability has a closed form (Corollary 18). It is nonincreasing in ε\varepsilon, goes from OPT(α)\mathrm{OPT}(\alpha) to 1/e1/e, and stays above 1/e1/e for every ε<1\varepsilon<1.

Known primitives. For any reliable signal, A(max⁡{S,kncl})\mathcal A(\max\{S,k_n^{\mathrm{cl}}\}) needs no distributional knowledge and never does worse than the classic policy. A(S)\mathcal A(S) is optimal for every α≥1\alpha\ge1 without knowing α\alpha. Theorem 17 learns α\alpha with finite-sample guarantees, and a new result (Appendix B.1) learns thresholds without a parametric family.

If this addresses your concerns, we would be grateful if you would consider it in your assessment.

I thank the authors for their response and the new results, which I believe further strengthen the paper. My concerns have been partially addressed. (I would recommend a score of 3.5 if such an option were available.)

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Rebuttal Comments

We thank the reviewers for their positive reviews. We uploaded a revision that uses the additional page. It addresses the following shared questions:

  • Unreliable signals (new Theorem 4, Corollary 18). Our exact O(n2)O(n^2) recursion extends to any known signal distribution with late, missing, or false signals, as long as the signal stays independent of the relative ranks given II. For α\alpha-power signals that are late or missing with probability ε\varepsilon, we give a closed form for the limiting optimal success probability. It is nonincreasing in ε\varepsilon, goes from OPT(α)\mathrm{OPT}(\alpha) at ε=0\varepsilon=0 to 1/e1/e at ε=1\varepsilon=1, and stays above 1/e1/e for every ε<1\varepsilon<1.
  • Family-free learning (new, Appendix B.1). Thresholds can be learned from data without assuming a signal family.
  • Scope relative to Dütting et al. and motivation are stated more precisely (see Section 1 and Appendix A).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.